how fast is Python code - another detail
Peter Otten
__peter__ at web.de
Thu Mar 4 15:10:35 EST 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
>> 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
and
key in theDict
tests *is* dangerous if you are concerned about speed.
Peter
More information about the Python-list
mailing list