develooper Front page | perl.perl5.porters | Postings from March 2010

Re: Another optimization question: bsearch()

Thread Previous | Thread Next
David Nicol
March 5, 2010 10:55
Re: Another optimization question: bsearch()
Message ID:
On Wed, Mar 3, 2010 at 9:16 AM, karl williamson <> wrote:
> His point was that there's no gain in having a bsearch, as someone
> writing in Perl will just use a hash.  But then he started thinking about it
> some more, and sent me privately a possible reason to have a bsearch exposed
> to the Perl programmer, as in some cases it makes more sense to keep things
> in an array instead of a hash.

an exposed POSIX::bsearch would use the same kind of comparator
functions that C<sort> uses. The memory savings one could get from
using a sorted array of object pointers instead of saving the
temporary table from a Schwarzian transform would not be worth it in
my (or Karl's) estimation.

On the other hand, you can get a range of consecutive elements with a
bsearch, which you can't do with a hash table without a more complex
data structure and advance indexing on partial keys.

So I've just published POSIX::bsearch to CPAN, which provides POSIX
bsearch semantics (any matching element) in scalar context or extended
semantics (the range of elements, and by the way, what index they
started at and how many there were are available in documented package
vars) in array context.

question doubt

Thread Previous | Thread Next Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at | Group listing | About