Why is if a in dict.keys() so slow.....

[Neel Krishnaswami]

Martin Franklin <martin.franklin at waii.com> wrote:
> Hi,
> 
> Just thought i'd throw this out there....
> 
> This is very slow:-
> 
> if split[0] in map_dict.keys():
>     print 'found it!', map_dict[split[0]]
> else:
>     print 'not found'
> 
> Question is why?


dict.keys() generates a list of the keys each time it is called, so
you are generating a list of 40K elements 250,000 times. Then, to do
the "split[0] in map_dict.keys()" test, you are searching through that
list one element at a time. So on average you'll search 40K/2 = 20K
elements before finding the key. Lookup for dictionaries (ie, writing
dict[foo]) is very fast -- the time to do a lookup doesn't go up, no
matter how many items you put in the dictionary. So the try/except
statement should run around 20K times faster.

If you just want to check whether an element is in a dictionary, there
is a method called dict.has_key(foo); it will return true if foo is a
key in the dictionary and false if not. This is also a very fast
lookup.

So you could also write:

  if map_dict.has_key(split[0])
      print "Found it!"
  else:
      print "Not found!"

The choice of try/except versus dict.has_key() is mostly one of taste;
the speed differences between the two is quite small, so you should
pick whichever one makes your intent clearer. (Incidentally, this will
also usually be the faster choice.)


Neel