Whither binary search?

[Neil Cerutti]

I can't find the mystic search glob that will find a binary
search function in the Python documentation.

Am I searching in vain, or do I need better search-fu?

--
Neil Cerutti

[skip@pobox.com]

Re: Whither binary search?

bisect...

Skip

[Neil Cerutti]

Re: Whither binary search?

On 2006-09-26, skip@pobox.com <skip@pobox.com wrote:

bisect...

That doesn't tell me if an item doesn't exist in the sequence
though, does it? Maybe I'm being dense.

My guess nobody keeps their sequences sorted in Python. ;)

--
Neil Cerutti

[Fredrik Lundh]

Re: Whither binary search?

Neil Cerutti wrote:

>bisect...

>
That doesn't tell me if an item doesn't exist in the sequence
though, does it? Maybe I'm being dense.

I guess you could use something like

import bisect

def check(list, item):
try:
return list[bisect.bisect_l eft(list, item)] == item
except IndexError:
return False

but unless your lists are really large, or your objects are expensive to
compare, you could probably just use "in" instead.

My guess nobody keeps their sequences sorted in Python.

well, people tend to use dictionaries when they need to look things up
quickly...

</F>

[skip@pobox.com]

Re: Whither binary search?


NeilOn 2006-09-26, skip@pobox.com <skip@pobox.com wrote:

>bisect...

NeilThat doesn't tell me if an item doesn't exist in the sequence
Neilthough, does it? Maybe I'm being dense.

NeilMy guess nobody keeps their sequences sorted in Python. ;)

Sorry, I was on the phone as I replied, and was only typing with my left
hand, so my response was intentionally very brief. ;-)

If you use bisect to do your insertions, your lists remain sorted. And as
for searching, all you have to do is look to the left or the right of the
insertion point (depending on which search method you call) to determine if
the item you're searching for is in the list.

Skip

[John Machin]

Re: Whither binary search?


Fredrik Lundh wrote:

Neil Cerutti wrote:
>

bisect...

That doesn't tell me if an item doesn't exist in the sequence
though, does it? Maybe I'm being dense.

>
I guess you could use something like
>
import bisect
>
def check(list, item):
try:
return list[bisect.bisect_l eft(list, item)] == item
except IndexError:
return False
>
but unless your lists are really large, or your objects are expensive to
compare, you could probably just use "in" instead.
>

My guess nobody keeps their sequences sorted in Python.

>
well, people tend to use dictionaries when they need to look things up
quickly...

.... like those paper dictionaries with the words in alphabetical order
:-)

A common use case for looking things up in a sorted list is an
in-memory table of dates and rates (interest rates, insurance premium
rates, fee rates). In a big batch job, this sure beats doing "select
rate from table where ? between low_date and high_date" each time you
need a rate.

Cheers,
John

[Sion Arrowsmith]

Re: Whither binary search?

John Machin <sjmachin@lexic on.netwrote:

>Fredrik Lundh wrote:

>well, people tend to use dictionaries when they need to look things up
>quickly...

>... like those paper dictionaries with the words in alphabetical order
>:-)

.... where you'll notice that the really big ones are divided up into
buckets (which just happen to be keyed on initial letter).

Truth is that humans are lot better than computers at general
insertion sort, and its lookup equivalent, whereas computers are much
better at calculating hashes. So we each use a dictionary
implementation that plays to our strengths.

--
\S -- siona@chiark.gr eenend.org.uk -- http://www.chaos.org.uk/~sion/
___ | "Frankly I have no feelings towards penguins one way or the other"
\X/ | -- Arthur C. Clarke
her nu becomeþ se bera eadward ofdun hlæddre heafdes bæce bump bump bump

[Neil Cerutti]

Re: Whither binary search?

On 2006-09-28, Sion Arrowsmith <siona@chiark.g reenend.org.ukw rote:

John Machin <sjmachin@lexic on.netwrote:

>>Fredrik Lundh wrote:

>>well, people tend to use dictionaries when they need to look things up
>>quickly...

>>... like those paper dictionaries with the words in alphabetical order
>>:-)

>
... where you'll notice that the really big ones are divided up
into buckets (which just happen to be keyed on initial letter).
>
Truth is that humans are lot better than computers at general
insertion sort, and its lookup equivalent, whereas computers
are much better at calculating hashes. So we each use a
dictionary implementation that plays to our strengths.

Thanks all, for the help.

In the end, perhaps prophetically, it turned out my data wasn't
really fully sorted after all. I put together a short function to
translate my raw data into a dictionary, and that was the end of
my problem.

--
Neil Cerutti

[John Machin]

Re: Whither binary search?


Sion Arrowsmith wrote:

John Machin <sjmachin@lexic on.netwrote:

Fredrik Lundh wrote:

well, people tend to use dictionaries when they need to look things up
quickly...

... like those paper dictionaries with the words in alphabetical order
:-)

>
... where you'll notice that the really big ones are divided up into
buckets (which just happen to be keyed on initial letter).

And languages whose scripts don't have letters use other bucket keys
like pronunciation or (radical, stroke_count). In any case, the
buckets are printed in key order. The bucket index, if printed, is
itself sorted.

>
Truth is that humans are lot better than computers at general
insertion sort, and its lookup equivalent, whereas computers are much
better at calculating hashes. So we each use a dictionary
implementation that plays to our strengths.

Hashes are fine for simplistic applications.
| >>hash('initial ise') == hash('initializ e')
| False
but those two are not very far apart in a sorted list.

Cheers,
John