The fastest search

[Fulvio]

***********************
Your mail has been scanned by InterScan MSS.
***********************
Hello,

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

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

F

[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.

[Gregor Horvath]

Fulvio schrieb:

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

measure it:

http://docs.python.org/lib/module-timeit.html

Regarding your debugger question in the seperate thread I don't know
since I am not using a debugger at all.

Most people coming from other languages are looking for a debugger and
are overlooking that in python a interactive interpreter, a good editor,
print statements and the tracebacks are all a lot of python developers need.

Small snippets of code are developed in the interpreter and when they
are working assembled in the editor. If something goes wrong a print on
the suspect place or the traceback is all I need. (of course this is
matter of taste)

--
Servus, Gregor

[Fulvio]

***********************
Your mail has been scanned by InterScan MSS.
***********************
On Saturday 21 October 2006 19:09, Steven D'Aprano wrote:

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

Very precious advice. Thank you, indeed. The lesson was good :-)

I'd only like to know if "List.index(vars)" has the same performance than
"vars in List" or even it's the same thing.
But, so far I still have my own question about that the search goes on the
key's name rather then its paired value. In fact, in my actual case the value
doesn't make any use.
However the search goes on a few hundred email ID, the difference is less than
a jiffy :-)

F

[Fulvio]

***********************
Your mail has been scanned by InterScan MSS.
***********************
On Saturday 21 October 2006 19:40, Gregor Horvath wrote:

Small snippets of code are developed in the interpreter and when they
are working assembled in the editor. If something goes wrong a print on
the suspect place or the traceback is all I need. (of course this is
matter of taste)

I also using this techinque, but I found myself to do a lot of rewriting on
the code, as long as probing several points on the program.
The pdb.py is much of what I need. Running the program can stop in critical
points and see if all comes as expected. It won't need to remove
several "print" from the code.
Obvious, it's referred for programs which aren't time critical.

F