[Tutor] "bisect" vs "in"
__peter__ at web.de
Thu Sep 20 14:58:49 CEST 2012
Albert-Jan Roskam wrote:
> I want to repeatedly search a list to test whether that list contains a
> given element X. Of course, I can use membership testing using "in"
> (list._contains__). But how is this method implemented? It seems to just
> walk through the whole list from beginning to end (see timeit code below).
> Is it faster to do a binary search on a sorted list, given that this task
> has to be done repeatedly?
Much faster. You don't see that in your timings because you include the
creation of the range(10**7) list in your measurement.
If you used a set instead of a list you could use "in", and it would be even
faster than bisect.
> Can such a program be scaled to lists that do
> not fit into memory (maybe using shelve?)?
That would slowdown things a lot. Disk access is *much* slower than RAM.
More information about the Tutor