Python Cookbook

Finding the Intersection of Two Dictionaries

Credit: Andy McKay, Chris Perkins, Sami Hangaslammi

Problem

Given two dictionaries, you need to find the set of keys that are in both dictionaries.

Solution

Dictionaries are a good concrete representation for sets in Python, so operations such as intersections are common. Say you have two dictionaries (but pretend that they each contain thousands of items):

some_dict = { 'zope':'zzz', 'python':'rocks' }
another_dict = { 'python':'rocks', 'perl':'$' }

Here’s a bad way to find their intersection that is very slow:

intersect = []
for item in some_dict.keys(  ):
    if item in another_dict.keys(  ):
        intersect.append(item)
print "Intersects:", intersect

And here’s a good way that is simple and fast:

intersect = []
for item in some_dict.keys(  ):
    if another_dict.has_key(item):
        intersect.append(item)
print "Intersects:", intersect

In Python 2.2, the following is elegant and even faster:

print "Intersects:", [k for k in some_dict if k in another_dict]

And here’s an alternate approach that wins hands down in speed, for Python 1.5.2 and later:

print "Intersects:", filter(another_dict.has_key, some_dict.keys())

Discussion

The keys method produces a list of all the keys of a dictionary. It can be pretty tempting to fall into the trap of just using in, with this list as the righthand side, to test for membership. However, in the first example, you’re looping through all of some_dict, then each time looping through all of another_dict. If some_dict has N1 items, and ...