how fast is Python code - another detail

Peter Otten __peter__ at
Thu Mar 4 21:10:35 CET 2004

Andrew Koenig wrote:

> "Peter Otten" <__peter__ at> wrote in message
> news:c280b0$1g3$03$1 at
>> 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.
> Worse:  Evaluating theDict.keys() requires building a list from all the
> keys.  So even if the key is the first element of the list, the run time
> is O(len(theDict)).

Might be interesting to measure the impact of boths effects separately by
keeping a copy of keys that will be updated in the if clause.

> Moreover, there's no way for the compiler to optimize such expressions in
> general, because it doesn't know the type of theDict during compilation.

Conclusion: the outward similarity of the

value in theList


key in theDict

tests *is* dangerous if you are concerned about speed.


More information about the Python-list mailing list