comment on

I took that as a challenge ;-). I didn't test my binary search with multiple identical values, thus I don't count it as a full implementation. But see the speed differences as a function of the array size:

100 items
           Rate brutal binary
brutal 186657/s     --   -16%
binary 223418/s    20%     --

1000 items
           Rate brutal binary
brutal  20574/s     --   -87%
binary 156038/s   658%     --

10000 items
           Rate brutal binary
brutal   2167/s     --   -98%
binary 129102/s  5859%     --

100000 items
          Rate brutal binary
brutal   169/s     --  -100%
binary 91542/s 54205%     --
[download]

And this is the code I used:

#!/usr/bin/perl
use strict;
use warnings;
use Benchmark qw(cmpthese);

my $limit = shift @ARGV || 1e4;
my @a = sort {$a <=> $b } map { rand(2**20) } 0..($limit+1);
print "Done generating list\n";

my $search_for = $a[int($limit / 3)];

sub brutal {
    for (0 .. $limit){
        return $_ if $a[$_] > $search_for;
    }
}

sub binary {
    my ($left, $right) = (0, $limit);
    while ($right - $left > 10){
        my $tmp = ($right+$left) / 2;
        if ($a[$tmp] > $search_for){
            $right = $tmp;
        } else {
            $left = $tmp;
        }
    }
    for ($left .. $right){
        return $_ if $a[$_] > $search_for;
    }
}
my $brutal = brutal();
my $binary = binary();
print $brutal, ' ', $binary, "\n";

cmpthese(-2, {
        binary  => \&binary,
        brutal  => \&brutal,
    });
[download]

The index of $limit / 3 to search for actually favors the "brutal" search, since it means the search terminates earlier than in random conditions.

In reply to Re^2: find closest element of array without going over by moritz
in thread find closest element of array without going over by sadfaceman

Are you posting in the right place? Check out Where do I post X? to know for sure.
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
Want more info? How to link or How to display code and escape characters are good places to start.


"be consistent"
	PerlMonks