Stories
Slash Boxes
Comments
NOTE: use Perl; is on undef hiatus. You can read content, but you can't post it. More info will be forthcoming forthcomingly.

All the Perl that's Practical to Extract and Report

use Perl Log In

Log In

[ Create a new account ]

koschei (147)

koschei
  useperl@dellah.org
http://eh.org/~koschei/

Um. Me. Iain Truskett. Can be found as either Spoon or Koschei around the place, and as Braxiatel in rare circumstances. Um. Cool. Ta.

My perl svn repository [dellah.org] if you want bits of code by me. Also see dellah.org [dellah.org] for most of them in action.

My friends [perl.org], foes [perl.org], fans [perl.org], and freaks [perl.org]. And you can see what my friends are journalling [perl.org].

And everybody's journals [perl.org] (in order of updating).

Journal of koschei (147)

Sunday March 23, 2003
08:29 PM

tbray's java bsearch - ruby and then perl?

[ #11189 ]

It's surprising how easily and quickly Java code can be turned into Ruby code.

class Array
  def bsearch ( target )
    high = self.length
    low = -1
    while high - low > 1
      probe = (high + low) / 2
      if self[probe] > target
    high = probe
      else
    low = probe
      end
    end
    if low == -1 || self[low] != target
      return -1
    else
      return low
    end
  end

  def bsearch_dups ( target )
    high = self.length
    low = -1
    while high - low > 1
      probe = (high + low) / 2
      if self[probe] < target
    low = probe
      else
    high = probe
      end
    end
    if high == self.length || self[high] != target
      return -1
    else
      return high
    end
  end

  def range ( floor, ceiling )

    answer = []

    # work on floor
    high = self.length
    low = -1
    while high - low > 1
      probe = (high + low) / 2
      if self[probe] < floor
    low = probe
      else
    high = probe
      end
    end
    answer[0] = low

    # work on ceiling
    high = self.length
    low = -1
    while high - low > 1
      probe = (high + low) / 2
      if self[probe] > ceiling
    high = probe
      else
    low = probe
      end
    end
    answer[1] = high

    return answer
  end

end

No doubt it could be written more clearly, but even with the basic translation it's nicer than the Java version. For a start, the routines are now methods on Arrays. Damn sensible place to keep them, although I'm sure several of the 4 readers of this post will disagree (including myself depending on the phase of the moon).

Secondly, it's type free.[1] This is a good thing.

Thirdly, think about this code in Perl. What would be written differently? Would you be tempted to have another parameter, a comparator? What would you do about the difference between comparing strings and numbers?

Enough of this for now.

[1] I'm sure there's a better, or more correct, term ('independent', 'agnostic', something), but I don't know it. Feel free to comment it.

The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
 Full
 Abbreviated
 Hidden
More | Login | Reply
Loading... please wait.
  • Changing the core (Score:3, Insightful)

    by acme (189) on 2003.03.23 21:37 (#18233) Homepage Journal
    Some of the neatest Ruby examples I've seen add methods or modify methods of the core classes. It's certainly neat and pretty clean. But what happens when multiple authors of the modules you happen to be using all muck about with the core in different, slightly incompatible ways?
    • It all goes to hell =)

      Generally, if you're modifying a class that isn't yours then you
      should only be adding stuff that's really generic. For example,
      a binary search to Array.

      Otherwise, you should be making your own Array subclass.

      I wouldn't be surprised if someone's already implemented
      a bsearch (in fact, I think Hal Fulton has one in "The Ruby Way").
      Ideally someone would be collecting these useful generics into
      a package, somewhere. Think List::Util =)

      But, yeah, it can go to hell.
      --
        ---ict / Spoon
  • I think it's going to be possible to create multimethods in Perl 6 that'll allow you to write smart comparators along the lines of the smart match operator, which should in turn allow for you to write a nicely generic binary search method on Array.

    Doesn't help with Perl 5 though.