Your skill will accomplishwhat the force of many cannot 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??

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_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
Replies are listed 'Best First'.
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)

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 pondering the Monastery: (14)
As of 2015-11-25 13:03 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?