[Tutor] Binary search question

[Dave Angel]

Lie Ryan wrote:
> On 04/24/10 23:39, Robert Berman wrote:
>   
>>> -----Original Message-----
>>> From: tutor-bounces+bermanrl=cfl.rr.com at python.org [mailto:tutor-
>>> bounces+bermanrl=cfl.rr.com at python.org] On Behalf Of Alan Gauld
>>> Sent: Friday, April 23, 2010 7:41 PM
>>> To: tutor at python.org
>>> Subject: Re: [Tutor] Binary search question
>>>
>>> "Emile van Sebille" <emile at fenx.com> wrote
>>>
>>>       
>>>>    BIG SNIP
>>>>         
>>> And even at 10000000 entries, the list creation slowed right
>>> down - about 10 seconds, but the searches even for "-5" were
>>> still around a second.
>>>
>>> So 'in' looks pretty effective to me!
>>>       
>> Now that is most impressive.
>>
>>     
>
> But that is with the assumption that comparison is very cheap. If you're
> searching inside an object with more complex comparison, say, 0.01
> second per comparison, then with a list of 10 000 000 items, with 'in'
> you will need on *average* 5 000 000 comparisons which is 50 000 seconds
> compared to *worst-case* 24 comparisons with bisect which is 0.24 seconds.
>
> Now, I say that's 208333 times difference, most impressive indeed.
>
>
>   

The ratio doesn't change with a slow comparison, only the magnitude.

And if you have ten million objects that are complex enough to take .01 
secs per comparison, chances are it took a day or two to load them up 
into your list.  Most likely you won't be using a list anyway, but a 
database, so you don't have to reload them each time you start the program.


It's easy to come up with situations in which each of these solutions is 
better than the other.

DaveA