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

Re: Another optimization question: bsearch()

Thread Previous | Thread Next
karl williamson
March 3, 2010 07:16
Re: Another optimization question: bsearch()
Message ID:
Nicholas Clark wrote:
> On Tue, Mar 02, 2010 at 09:50:51AM -0600, David Nicol wrote:
>> On Mon, Mar 1, 2010 at 12:43 PM, karl williamson
>> <> wrote:
>>> Inversion lists can be searched binarily.  bsearch() is a standard C library
>>> routine, but the only mention of it in Perl is in the POSIX module where it
>>> says it is not furnished.  This makes me think there must be a problem with
>>> using the library routine.  Is there?
>> the problem is that you need to keep your data sorted, which is not
>> perly. The perly thing to do is to keep data in a hash table instead
>> of a sorted array. So not furnishing a perl interface to bsearch a
>> perl array makes sense, because You Should Be Using A Hash Table Silly
>> Rabbit.
> You're not understanding the problem here.
> What you say is appropriate for the general case in perl, but not for the
> specific area that Karl is describing.
> Nicholas Clark
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.

mktables uses a binary search written in Perl, but it needs extra 
functionality beyond that which bsearch provides.

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