### Re^2: Modified Binary Search

by ikegami (Pope)
 on Jan 13, 2010 at 22:02 UTC ( #817290=note: print w/replies, xml ) Need Help??

in reply to Re: Modified Binary Search

That makes an O(log N) algorithm into O(N). Were 10 checks were made, you'd now make 1,000,000.

Replies are listed 'Best First'.
Re^3: Modified Binary Search
by salva (Canon) on Jan 14, 2010 at 09:05 UTC
That makes an O(log N) algorithm into O(N).

Obviously it does not!

As for any binary search algorithm you have a previous step where you build the array, sorting something, loading it from disk, whatever. This operation is O(N) in the best case and usually O(NlogN) because of the sorting.

Once that array is build you can perform binary searches over it with cost O(logN). In order to amortize the cost of building the array the number of binary searches has to be high (otherwise, there are better algorithms).

The algorithm I have proposed increments the cost of the setup step but does not change its complexity because it already was O(N) at best.

Also, if the number of repeated strings is high, @start would be considerably smaller than @a and so less operations will be performed per binary search. That means that if the number of binary searches to be carried out is high enough, my algorithm will actually be faster than any other one attacking @a directly.

Re^3: Modified Binary Search
by salva (Canon) on Jan 14, 2010 at 14:32 UTC
... and some benchmarking code just to probe it is not worse:
```#!/usr/bin/perl

use strict;
use warnings;

use File::Slurp qw(slurp);
use Benchmark qw(cmpthese);

sub binary_search {
my (\$str, \$a) = @_;
my \$l = 0;
my \$h = @\$a;
while (\$l < \$h) {
my \$p = int ((\$l + \$h) / 2);
if (\$a->[\$p] lt \$str) {
\$l = \$p + 1;
}
else {
\$h = \$p;
}
}
\$l
}

sub make_start {
my \$a = shift;
my \$last = \$a->[0];
my @start = (0);
for my \$ix (1..\$#\$a) {
my \$current = \$a->[\$ix];
if (\$current ne \$last) {
push @start, \$ix;
\$last = \$current;
}
}
return \@start;
}

chomp (my @words = slurp '/usr/share/dict/words');
@words = grep /^\w+\$/, @words;

for my \$size (100, 1000, 100_000, 1_000_000) {
for my \$dups (3, 10, 100) {
next unless \$size > \$dups;
for my \$reps (100, 100_000, 1_000_000) {
print "size: \$size, dups: \$dups, reps: \$reps\n";
# generate data:
my @a = map \$words[rand @words], 1..1+(\$size/\$dups);
push @a, \$a[rand @a] while @a < \$size;
@a = sort @a;
cmpthese(-30, {
naive => sub {
my \$ix;
\$ix = binary_search(\$a[rand @a], \@a) for
+ (1..\$reps);
},
salva => sub {
my \$ix;
my \$start = make_start(\@a);
my @a_start = @a[@\$start];
\$ix = \$start->[binary_search(\$a[rand @a],
+ \@a_start)] for (1..\$reps);
}
});
print "\n";
}
}
}
The parameters in the benchmarks are:
• \$size: the size of the array
• \$dups: average number of times any string is repeated in the array
• \$reps: number of binary searchs to perform over one given array.

Note also than this code only looks for the lowest index where some given string is found. Handling the case described by the OP where he also needs to find the highest index is trivially handled in my algorithm without increasing its computation cost but will require an additional binary search when using the naive algorithm.

Here are the results I have gotten on my machine:

Of course the array construction won't add to the time if you don't include it in the code that's timed.

You assume the same list is always searched.

I suppose a more precise analysis is O(log(N) + N/M) where M is the number of searched performed between modifications of the list. The number of such searches have to be proportional to the size of the list to get less than O(N).

Create A New User
Node Status?
node history
Node Type: note [id://817290]
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: (5)
As of 2021-06-20 01:09 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
What does the "s" stand for in "perls"? (Whence perls)

Results (93 votes). Check out past polls.

Notices?