[Tutor] Binary search question

Lie Ryan lie.1296 at gmail.com
Sat Apr 24 18:21:15 CEST 2010


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.



More information about the Tutor mailing list