On 04/24/10 23:39, Robert Berman wrote: >> -----Original Message----- >> From: tutor-bounces+bermanrl=cfl.rr....@python.org [mailto:tutor- >> bounces+bermanrl=cfl.rr....@python.org] On Behalf Of Alan Gauld >> Sent: Friday, April 23, 2010 7:41 PM >> To: tutor@python.org >> Subject: Re: [Tutor] Binary search question >> >> "Emile van Sebille" <em...@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. _______________________________________________ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
