How does the performance of dictionary key lookups compare in Python?

Question

How does:

dict = {}
if key not in dict:
 dict[key] = foo

Compare to:

try:
 dict[key]
except KeyError:
 dict[key] = foo 

ie, is the look up of a key in anyway faster than the linear search through dict.keys(), that I assume the first form will do?

Answer 1

Just to clarify one point: if key not in d doesn't do a linear search through d's keys. It uses the dict's hash table to quickly find the key.

Answer 2

You're looking for the setdefault method:

>>> r = {}
>>> r.setdefault('a', 'b')
'b'
>>> r
{'a': 'b'}
>>> r.setdefault('a', 'e')
'b'
>>> r
{'a': 'b'}

Answer 3

The answer depends on how often the key is already in the dict (BTW, has anyone mentioned to you how bad an idea it is to hide a builtin such as dict behind a variable?)

if key not in dct:
 dct[key] = foo

If the key is in the dictionary this does one dictionary lookup. If the key is in the dictionary it looks up the dictionary twice.

try:
 dct[key]
except KeyError:
 dct[key] = foo 

This may be slightly faster for the case where the key is in the dictionary, but throwing an exception has quite a big overhead, so it is almost always not the best option.

dct.setdefault(key, foo)

This one is slightly tricky: it always involves two dictionary lookups: the first one is to find the setdefault method in the dict class, the second is to look for key in the dct object. Also if foo is an expression it will be evaluated every time whereas the earlier options only evaluate it when they have to.

Also look at collections.defaultdict. That is the most appropriate solution for a large class of situations like this.