how fast is Python code - another detail

Peter Otten __peter__ at web.de
Thu Mar 4 20:33:52 CET 2004


Gregor Lingl wrote:

> I think I understand why it is the case - the timing factor
> is proportional to the square of len(wordlist), because
> in every loop a list d.keys() has to be computed and now
> this has to be used for searching for the key sig,
> while for sig in d uses some built-in generator-property
> of dictionaries ...  (?)

I think you do not understand. The change from

key in theDict # old style would be theDict.has_key(key)

to

# iterkeys() can sometimes be used to avoid the creation of 
# the list with all keys, you would have to introduce a for loop.
# But keys vs iterkeys is not the relevant difference here
key in theDict.keys()                       


changes the lookup from constant time (a hash value is calculated which is
used as an index into a list of values if all goes well) to proportonial to
len(theDict) because on average half of the list has to be searched before
the matching entry is found.

Peter



More information about the Python-list mailing list