Confused compare function :)
steve+comp.lang.python at pearwood.info
Fri Dec 7 23:16:07 CET 2012
On Thu, 06 Dec 2012 23:14:17 +1100, Chris Angelico wrote:
> Setting up the try/except is a constant time cost,
It's not just constant time, it's constant time and *cheap*. Doing
nothing inside a try block takes about twice as long as doing nothing:
[steve at ando ~]$ python2.7 -m timeit "try: pass
> except: pass"
10000000 loops, best of 3: 0.062 usec per loop
[steve at ando ~]$ python2.7 -m timeit "pass"
10000000 loops, best of 3: 0.0317 usec per loop
> while the duplicated
> search for k inside the dictionary might depend on various other
It depends on the type, size and even the history of the dict, as well as
the number, type and values of the keys. Assuming a built-in dict, we can
say that in the absence of many collisions, key lookup can be amortized
over many lookups as constant time.
> In the specific case of a Python dictionary, the membership
> check is fairly cheap (assuming you're not the subject of a hash
> collision attack - Py3.3 makes that a safe assumption),
Don't be so sure -- the hash randomization algorithm for Python 3.3 is
trivially beaten by an attacker.
but in general, yes, key lookup in dicts is fast. But not as fast as
setting up a try block.
Keep in mind too that the "Look Before You Leap" strategy is
fundamentally unsound if you are using threads:
# in main thread:
if key in mydict: # returns True
x = mydict[key] # fails with KeyError
How could this happen? In the fraction of a second between checking
whether the key exists and actually looking up the key, another thread
could delete it! This is a classic race condition, also known as a Time
Of Check To Time Of Use bug.
More information about the Python-list