Confused compare function :)

[Steven D'Aprano]

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
> factors. 

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.

http://bugs.python.org/issue14621#msg173455

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.


-- 
Steven