Python 元组作为键慢吗？

我正在尝试实现字典中排序元组的快速查找；回答“元组 (3,8) 是否有关联值，如果有，它是什么？”的问题。令元组中的整数从下方以 0 为界，从上方以 max_int 为界。

我继续使用 Python 的 dict，但发现速度相当慢。解决此问题的另一种方法是创建一个具有 max_int （大部分为空）字典的列表 T，并为每个元组 (3,8) 输入 T[3][8] = value。 我认为这正是 Python 对字典采用的存储桶哈希方法，但后者的速度大约快 30 倍（！）。

不过，它也很丑陋（特别是因为我现在即将实现 3 元组），所以我非常感谢这里的一些提示。

作为参考，这是我用来获取计时的代码：

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

以下是 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

他们表明，标准(3, 8) in d (no .keys()列表构建）实际上比（不太通用）快一点8 in t[3]方法，以及快两倍由于相对较快8 in t[3].keys()的问题。这.keys/no .keys差异来自于这样一个事实：(3, 8) in d.keys()构建一个键列表（在 Python 2 中），然后查找(3, 8)在这个列表中，这比查找要慢得多(3, 8)在字典的哈希表中d.

正如评论中所述，计时结果与 Python 3 不同：Python 3keys()有一个快速in测试因为keys()相反，返回键的视图，以便in运算符可以使用对应字典的哈希表。

原始问题中的速度差异来自于以下事实：d.keys()与相比，建立了一个相对较长的列表t[3].keys().

PS: the %timeit功能由优秀的提供IPython http://ipython.org/壳。原始程序可以通过 IPython 执行%run prog.py.