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:
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.my @arr = (1 .. 1_000_000); my $x = 425983; printf "search for $x? found at position: %s\n", binarySearch(0,$x,\@a +rr);
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)
This should save a lot of memory. It now takes about 10 seconds running on 5 million ints for me.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; } }
blokhead
|
---|
Replies are listed 'Best First'. | |
---|---|
Re^2: My Binary Search Perl code takes forever
by Anonymous Monk on Dec 15, 2007 at 16:07 UTC | |
by Anonymous Monk on Dec 15, 2007 at 16:29 UTC |
In Section
Seekers of Perl Wisdom