how fast is Python code - another detail
__peter__ at web.de
Thu Mar 4 21:10:35 CET 2004
Andrew Koenig wrote:
> "Peter Otten" <__peter__ at web.de> wrote in message
> news:c280b0$1g3$03$1 at news.t-online.com...
>> 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
>> 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