Python tuples as keys slow?

Question

I'm trying to implement an fast lookup for sorted tuples in a dictionary; something that answers the question "Does the tuple (3,8) have an associated value, and if yes, what is it?". Let the integers in the tuples be bound from below by 0 and from above by max_int.

I went ahead and used Python's dict but found that to be pretty slow. Another approach to this problem would be to create a list T with max_int (mostly empty) dicts, and for each tuple (3,8) put T[3][8] = value. I though this is exactly the bucket-hash approach that Python takes with dicts, but the latter is about 30 times (!) faster here.

Also, though, it's ugly (especially since I'm now about to implement 3-tuples), so I'd much appreciate some hints here.

For reference, Here's the code I used to get the timings:

import numpy as np
import time

# create a bunch of sorted tuples
num_tuples = 10
max_int = 100
a = np.random.rand(num_tuples,2) * max_int
a = a.astype(int)
for k in xrange(len(a)):
    a[k] = np.sort(a[k])

# create dictionary with tuples as keys
d = {}
for t in a:
    d[tuple(t)] = 42

print d

# do some lookups
m = 100000
start_time = time.time()
for k in xrange(m):
    (3,8) in d.keys()
elapsed = time.time() - start_time
print elapsed

# now create the bucket-list structure mentioned above
t = [{} for k in xrange(max_int)]
for k in xrange(len(a)):
    t[a[k][0]][a[k][1]] = 42

print t

# do some lookups
m = 10000
start_time = time.time()
for k in xrange(m):
    8 in t[3].keys()
elapsed = time.time() - start_time
print elapsed

Answer 1

Here are precise timing results with Python 2.7:

>>> %timeit (3, 8) in d.keys()  # Slow, indeed
100000 loops, best of 3: 9.58 us per loop

>>> %timeit 8 in t[3].keys()  # Faster
1000000 loops, best of 3: 246 ns per loop

>>> %timeit (3, 8) in d  # Even faster!
10000000 loops, best of 3: 117 ns per loop

>>> %timeit 8 in t[3]  # Slightly slower
10000000 loops, best of 3: 127 ns per loop

They show that the standard (3, 8) in d (no .keys() list building) is actually a tad faster than the (less general) 8 in t[3] approach, and twice as fast as the relatively fast 8 in t[3].keys() of the question. This .keys/no .keys difference comes from the fact that (3, 8) in d.keys() builds a list (in Python 2) of the keys and then looks for (3, 8) in this list, which is much slower than looking for (3, 8) in the hash table of dictionary d.

As noted in the comments, the timing results are different with Python 3: Python 3's keys() has a fast in test because keys() returns instead a view on the keys, so that the in operator can use the hash table of the corresponding dictionary.

The speed difference in the original question comes from the fact that d.keys() builds a relatively long list, compared to t[3].keys().

PS: the %timeit function is provided by the excellent IPython shell. The original program can be executed through IPython with %run prog.py.

Answer 2

You're testing for different values. In the dictionary version, there's a lookup for 100,000 keys, whereas in the bucket-list structure, the lookup is for just 10,000 keys.

Apart from that, this snippet of code is slowing things down: (3,8) in d.keys() if you just wrote (3,8) in d, then the lookup time in both versions would be quite similar, and the difference negligible. Try this modified test and see for yourself:

import numpy as np
import time

# create a bunch of sorted tuples
num_tuples = 10
max_int = 100
a = np.random.rand(num_tuples,2) * max_int
a = a.astype(int)
for k in xrange(len(a)):
    a[k] = np.sort(a[k])

# create dictionary with tuples as keys
d = {}
for t in a:
    d[tuple(t)] = 42

# do some lookups
m = 100000
start_time = time.time()
for k in xrange(m):
    if (3,8) in d:
        pass

elapsed = time.time() - start_time
print elapsed

# now create the bucket-list structure mentioned above
t = [{} for k in xrange(max_int)]
for k in xrange(len(a)):
    t[a[k][0]][a[k][1]] = 42

# do some lookups
m = 100000
start_time = time.time()
for k in xrange(m):
    if 8 in t[3]:
        pass

elapsed = time.time() - start_time
print elapsed

The reason for the observed behavior is that both (3,8) in d.keys() and 8 in t[3].keys() are creating a new temporary list of keys every time, but the second version creates shorter lists. If you had simply used the idiom key in dictionary, the temporary lists no longer get created and performance starts to look similar for both approaches.

I'd go with the first version, is much simpler, easier to read and understand and idiomatic - and when used properly, performs just as well as the second version.

Answer 3

It is a bit odd to compare the speed of (a, b) in d to b in t[a] because the latter assumes that a must be present.

In any case, the first way should always be faster. Both version has both a and b. The first has the additional overhead of allocating a tuple and hashing it. However, the second way does two separate dictionary lookups.