Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number
 
PerlMonks  

Comment on

( #3333=superdoc: 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_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


In reply to Re^3: Tracking minimum of values in an array over time by Limbic~Region
in thread Tracking minimum of values in an array over time by tj_thompson

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • Outside of code tags, you may need to use entities for some characters:
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others studying the Monastery: (11)
    As of 2014-08-27 21:11 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      The best computer themed movie is:











      Results (253 votes), past polls