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