[Tutor] Binary search question
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