in reply to My Binary Search Perl code takes forever

blokhead's analysis sounds true. When dealing with millions of values, Perl uses up all available memory.

Since you're only using integers, one method to reduce memory usage considerably is to use a string of packed integers. Tie::IntegerArray makes this transparent for you. (It's suppose to, at least. Untested.) Use it in conjunction with blokhead's change to use a reference. 

my @integer_array;
tie @integer_array, 'Tie::IntegerArray',
    bits   => 32,
    signed => 1,
    size   => 1_000_000;  # Pre-allocate this many

[download]

By the way, why do you switch from a binary search to a linear search to find the beginning of a match?

Replies are listed 'Best First'.
Re^2: My Binary Search Perl code takes forever
by Anonymous Monk on Dec 15, 2007 at 19:00 UTC
    "By the way, why do you switch from a binary search to a linear search to find the beginning of a match?" Since the array could contain duplicate entries, I just want to find the first (if begin = 1) or last (if begin=0) of the entries. Is there a better way to do it that to search linearly after I find my query?
[reply]

      Yes, stick with the binary search. Just change the terminating condition from 

      $query == $array->[$center]

      [download]

      to 

      $query == $array->[$center] && ($begin
   ? ($center == 0        || $query != $array->[$center-1])
   : ($center == $#$array || $query != $array->[$center+1])
)

      [download]

      You check the condition a second and third time later down, so you need to fix those too.

      All together: 

      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) = (0, $#$array, -1);

  while(1) {
    my $center = int (($left + $right)/2);

    my $cmp =  $query <=> $array->[$center]
            || ($begin
                 ? ($center == 0        || $query != $array->[$center-
+1] ? 0 : -1)
                 : ($center == $#$array || $query != $array->[$center+
+1] ? 0 : +1)
               );

    return $center if $cmp == 0;
    if ($center == $prevCenter) {
      return $right   if $begin == 1;
      return $right-1 if $begin == 0;
    }
    $right = $center if $cmp < 0;
    $left  = $center if $cmp > 0;
    $prevCenter = $center;
  }
}

      [download]

      Update: Added code.

[reply]
[d/l]
[select]

In Section Seekers of Perl Wisdom