Beefy Boxes and Bandwidth Generously Provided by pair Networks
"be consistent"

Tracking minimum of values in an array over time

by tj_thompson (Monk)
on Oct 05, 2011 at 18:45 UTC ( #929852=perlquestion: print w/ replies, xml ) Need Help??
tj_thompson has asked for the wisdom of the Perl Monks concerning the following question:

Hello monks. I have a fairly simple algorithmic question. It seems to me there should be a good way to do this, but I haven't come up with anything yet and figured I'd toss it to you folks.

Assume I have an array with some arbitrary number of values in it all initialized to zero.

@a = (0, 0, 0, 0, 0);

After initialization, the values in this array are only incremented (never decremented). I never add or remove elements to or from the array.

# some time down the road after some number of increments @a = (3, 1, 8, 12, 2);

However, I am not really interested in the actual value of each element, but in the minimum value of the set of elements at any one time. Once a minimum floor value is reached, I'm ready to move on.

The array I'm dealing with will be very large with many increment operations. Is there a way to track the minimum value currently in the array without having to resort to a linear search through it after each increment?

Comment on Tracking minimum of values in an array over time
Select or Download Code
Re: Tracking minimum of values in an array over time
by davido (Archbishop) on Oct 05, 2011 at 19:05 UTC

    If it's impractical to keep track of all the possible ways elements may be incremented (which may be indicative of a design flaw), perhaps tieing it to a class that keeps track of updates behind the scenes through an accumulator would work for (or rescue) you. By taking this approach, and keeping track of updates as they happen, you trade O(n) tests for O(1) tests. The tradeoff is that a tied array itself carries with it more computational overhead than a simple array.

    The class would need one accessor for the minimum value, so when your array is tied you would need to keep a copy of the object reference so that $o->get_min(); would work.

    Be aware that you will have to guard against The untie Gotcha if you are using both the tied variable's primary interface (the array) and its object interface( $o->whatever() ).


Re: Tracking minimum of values in an array over time
by keszler (Priest) on Oct 05, 2011 at 19:07 UTC

    List::Util has a min function, and being XS-based it's quick.

Re: Tracking minimum of values in an array over time
by suaveant (Parson) on Oct 05, 2011 at 19:23 UTC

                    - Ant
                    - Some of my best work - (1 2 3)

      What ++suaveant said.






        Great idea from both of you, many thanks!




        Cheers - L~R

Re: Tracking minimum of values in an array over time
by ambrus (Abbot) on Oct 06, 2011 at 15:47 UTC

    You can use a priority queue, such as a binary heap (Not necessarily that implementation, just something similar.) You keep the indices and values of your array in this priority queue, with lowest values down. Whenever you change a number in the array, you delete the corresponding entry from the priority queue and then reinsert a new one. The priority queue will then keep track of the element with the lowest value for you.

      A min heap would be an excellent way to determine the min value of the set at any time. Good call. For my particular problem, since I'm actually interested in making certain that all elements have crossed the floor value (as pointed out by Ant above), I think counting the number of values that cross the floor as they are incremented is the smartest solution.

      Good thoughts Ambrus, thanks!

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://929852]
Approved by davido
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others contemplating the Monastery: (5)
As of 2014-12-29 04:23 GMT
Find Nodes?
    Voting Booth?

    Is guessing a good strategy for surviving in the IT business?

    Results (184 votes), past polls