Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw
 
PerlMonks  

Re: My Binary Search Perl code takes forever

by blokhead (Monsignor)
on Dec 15, 2007 at 15:49 UTC ( #657201=note: print w/ replies, xml ) Need Help??


in reply to My Binary Search Perl code takes forever

On my computer, it takes about 2 seconds to run on an array with 1 million ints:

my @arr = (1 .. 1_000_000); my $x = 425983; printf "search for $x? found at position: %s\n", binarySearch(0,$x,\@a +rr);
However, if I go to 5 million, my operating system starts thrashing. Maybe that's what's happening to you too (memory usage starts becoming an issue). It's also quite possible that python has lower overhead for integer scalars than Perl, but I have no idea.

One thing I noticed is that you pass in the array by reference (good idea), but the first thing you do is copy it entirely into a local variable. Why not keep accessing it by reference, like this: (I changed some other things around too)

sub binarySearch { my ($begin, $query, $array) = @_; return 0 if $query < $array->[0] and $begin == 1; return $#$array if $query > $array->[$#$array] and $begin == 0; my ($left,$right,$prevCenter, $center) = (0, $#$array, -1); while(1) { $center = int (($left + $right)/2); if ($query == $array->[$center]) { if ($begin == 1) { $center-- until $center == 0 or $array->[$center] != $array->[$center-1]; } else { $center++ until $center == $#$array or $array->[$center] != $array[$center+1]; } return $center; } if ($center == $prevCenter) { return $right if $begin == 1; return $right-1 if $begin == 0; } $right = $center if $query < $array->[$center]; $left = $center if $query > $array->[$center]; $prevCenter = $center; } }
This should save a lot of memory. It now takes about 10 seconds running on 5 million ints for me.

blokhead


Comment on Re: My Binary Search Perl code takes forever
Select or Download Code
Re^2: My Binary Search Perl code takes forever
by Anonymous Monk on Dec 15, 2007 at 16:07 UTC
    Did you try one query (2seconds) or ~500 queries. For about ~500 queries, it takes about 5-7 minuetes. I think this is way too slow. Because, I need to make about 100,000 queries, which takes 1000 minutes (16 hours)....
      "One thing I noticed is that you pass in the array by reference (good idea), but the first thing you do is copy it entirely into a local variable. Why not keep accessing it by reference, like this: (I changed some other things around too)"


      Wow! I keep accessing it by reference, it runs in no time. Fantastic. Thanks a lot.

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others surveying the Monastery: (14)
As of 2014-07-31 17:53 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite superfluous repetitious redundant duplicative phrase is:









    Results (250 votes), past polls