The fastest search

[Steven D'Aprano]

On Sat, 21 Oct 2006 17:41:04 +0800, Fulvio wrote:

> I'm poor in knoweledge of python, sorry. What's the fastest result between :
> 
> if item in alist:
>          do_something
> 
> or
> 
> if adictionay has_key(item):
>          do_something

Let's find out.

Searches that succeed:

>>> import timeit
>>> search_list_setup = "L = range(10000)"
>>> search_list = "L.index(7500)"
>>> timeit.Timer(search_list, search_list_setup).timeit(10000)
8.0721840858459473

>>> search_dict_setup = """D = {}
... for i in range(10000):
...     D[i] = None
... """
>>> search_dict = "D.has_key(7500)"
>>> timeit.Timer(search_dict, search_dict_setup).timeit(10000)
0.0079340934753417969

So for searches that succeed, dicts are much faster than lists.

How about searches that fail?


>>> search_dict_fail = "D.has_key(-7500)"
>>> timeit.Timer(search_dict_fail, search_dict_setup).timeit(10000)
0.0060589313507080078

>>> search_list_fail = """try:
...     L.index(-7500)
... except ValueError:
...     pass
... """
>>> timeit.Timer(search_list_fail, search_list_setup).timeit(10000)
11.371721982955933

Again, dicts are much faster.

But what if you know the list is sorted, and you can do a binary search?

>>> binary_search_setup = """import bisect
... L = range(10000)
... """
>>> binary_search = "bisect.bisect(L, 7500)"
>>> timeit.Timer(binary_search, binary_search_setup).timeit(10000)
0.04595494270324707

Still slower than a dict, but much, much faster than a linear search.


> Is there some trick to apply the best search in wise use of resources
> while using the above said methods?

Yes. 

Measure, don't guess. Don't even think about optimising your code until
it is working. Use the data structures which are natural to the task, then
measure to see if it is too slow. Never assume something is too slow until
you've measured it. Measure using realistic data -- don't do all your
tests with lists of ten items if actual working data will have ten
thousand items, and vice versa.

And most importantly, think about whether optimisation is a worthwhile use
of your time: do you really care about saving five milliseconds in a
program that takes 30 seconds to run?


-- 
Steve.