Beefy Boxes and Bandwidth Generously Provided by pair Networks
Keep It Simple, Stupid
 
PerlMonks  

Re^3: Tracking minimum of values in an array over time

by Limbic~Region (Chancellor)
on Oct 06, 2011 at 18:27 UTC ( #930041=note: print w/ replies, xml ) Need Help??


in reply to Re^2: Tracking minimum of values in an array over time
in thread Tracking minimum of values in an array over time

liverpole,
I haven't read your code but in thinking about the problem, you should never need to scan the array. The following is completely untested but it explains why I believe it is unnecessary.

my @array = ((0) x 100); my $inc_array = gen_min_tracker(0, 100, \@array); my $floor = 27; my $new_min = inc_array(42, 7); # increment the 43rd element by 7 if ($new_min >= $floor) { print "The floor has been reached\n"; } sub gen_min_tracker { my ($curr_min, $curr_cnt, $aref) = @_; my ($next_min, $next_cnt); return sub { my ($idx, $inc) = @_; my $val = $aref->[$idx]; my $add = $val + $inc; if ($val == $curr_min) { $curr_cnt--; if (! defined $next_min || $add <= $next_min) { $next_min = $add; $next_cnt++; } if (! $curr_cnt) { ($curr_val, $curr_cnt, $next_val, $next_cnt) = ($next_ +val, $next_cnt, undef, undef); } } $aref->[$idx] += $inc; # let's not forget to actually increme +nt return $curr_min; }; }
Update: Due to some unknown copy/paste error, the code above has been altered slightly from its original form to hopefully be correct despite still not being tested.

Warning: In the CB, ambrus points out that this approach is flawed. It is not safe to reset $next_val and $next_cnt to undef. The assumption was that anytime one of the $curr_min values was incremented, it would be incremented to the $next_min and that no other value in the array could possibly be smaller. The solution is simple - put in the O(N) low water mark algorithm keeping track of the min value and count.

Consideration: While you can't keep track of the minimum value without periodically scanning, you can still achieve the OP's goal as suaveant points out.

Cheers - L~R


Comment on Re^3: Tracking minimum of values in an array over time
Download Code
Re^4: Tracking minimum of values in an array over time
by suaveant (Parson) on Oct 06, 2011 at 20:15 UTC
    The array scan was in there to allow comparison of "slow" vs "fast" I believe.

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

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://930041]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others scrutinizing the Monastery: (8)
As of 2014-09-19 08:23 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (133 votes), past polls