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_s etup = "L = range(10000)"
search_list = "L.index(75 00)"
timeit.Timer( search_list, search_list_set up).timeit(1000 0)

8.0721840858459 473

>>search_dict_s etup = """D = {}

.... for i in range(10000):
.... D[i] = None
.... """

>>search_dict = "D.has_key(7500 )"
timeit.Timer( search_dict, search_dict_set up).timeit(1000 0)

0.0079340934753 417969

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

How about searches that fail?

>>search_dict_f ail = "D.has_key(-7500)"
timeit.Timer( search_dict_fai l, search_dict_set up).timeit(1000 0)

0.0060589313507 080078

>>search_list_f ail = """try:

.... L.index(-7500)
.... except ValueError:
.... pass
.... """

>>timeit.Timer( search_list_fai l, search_list_set up).timeit(1000 0)

11.371721982955 933

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_sear ch = "bisect.bisect( L, 7500)"
timeit.Timer( binary_search, binary_search_s etup).timeit(10 000)

0.0459549427032 4707

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(var s)" 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