Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl-Sensitive Sunglasses
 
PerlMonks  

Re: bit-vector > global minimum

by choroba (Abbot)
on Oct 03, 2011 at 16:44 UTC ( #929378=note: print w/ replies, xml ) Need Help??


in reply to bit-vector > global minimum

Just an idea: If a zero follows a 1, it cannot be the minimum. So you can ommit all the zeros preceded by ones (remove them also), recursively. At the end, there are just zeros followed by ones. The last zero is the minimum (or the first 1 if there are no zeros). Does it help?
Update: re-worded (underscored).


Comment on Re: bit-vector > global minimum
Re^2: bit-vector > global minimum
by dwm042 (Priest) on Oct 03, 2011 at 17:17 UTC
    Choroba,

    This algorithm you suggest would fail on a bit vector of 15 1s followed by 5 zeroes.

    David.
      I updated the algorithm, an important part was missing from the post (silly me). It should work now:
      1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 - - 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 - - - - 0 0 0 1 1 1 1 1 1 1 1 1 1 1 - - - - - - 0 0 1 1 1 1 1 1 1 1 1 1 - - - - - - - - 0 1 1 1 1 1 1 1 1 1 - - - - - - - - - - ^ minimum
Re^2: bit-vector > global minimum
by baxy77bax (Chaplain) on Oct 03, 2011 at 17:20 UTC
    but this implies that i would need to do this for every given pair of indexes which would lead to a:

    If X = |A[i,j]|, O(X) time algorithm which is higher then my tree solution that runs in O(logX) if i understood you correctly

    But never the less, this is a nice trick that didn't cross my mind. Thank you !!!!

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (13)
As of 2014-09-23 18:00 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

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











    Results (234 votes), past polls