Perl: the Markov chain saw PerlMonks

### Re^3: Modified Binary Search

by BrowserUk (Pope)
 on Jan 14, 2010 at 18:14 UTC ( #817454=note: print w/replies, xml ) Need Help??

in reply to Re^2: Modified Binary Search

This was a 1 time activity...

Seems a simple linear search would have been sufficient then.

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.

Replies are listed 'Best First'.
Re^4: Modified Binary Search
by Limbic~Region (Chancellor) on Jan 14, 2010 at 23:32 UTC
BrowserUk,
That's the way I had it coded originally but when it wasn't complete when I came back from lunch - I wasn't happy to continue waiting. Performing a linear search through 5 million records 600,000 times still takes longer than I wanted.

Cheers - L~R

Hm. You have a big list and a small list of dates, both sorted (or readily sortable).

And for each date in the small list, you want to find the subset of the big list that are 1 year either side.

And you search anew for each item in the small list?

Here's a one-pass algorithm:

```my @bigSorted = ...;
my @smallSorted = ...;
my %ranges;
my( \$lo, \$hi ) = ( 0, 0 );
for ( @smallSorted ) {
my( \$early, \$late ) = calcBoundaryDates( \$_ );
++\$lo while \$bigList[ \$lo ] lt \$early;
\$hi //= \$lo;
++\$hi while \$bigList[ \$hi ] le \$late;
\$ranges{ \$_ } = \$hi - \$lo;
}

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.

That works fine if you're doing it as a one-time deal for all elements of Tbl_B. LR's problem description seems to say that the search needs to be done for the modified elements each time Tbl_B is modified. Since the above technique does linear search, it's not going to be optimal.

Create A New User
Node Status?
node history
Node Type: note [id://817454]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (2)
As of 2021-06-14 04:43 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
What does the "s" stand for in "perls"? (Whence perls)

Results (60 votes). Check out past polls.

Notices?