Python 元组作为键慢？

Question

我正在尝试实现对字典中已排序元组的快速查找；回答问题“元组 (3,8) 是否有关联值，如果有，它是什么？”的东西。让元组中的整数从下到上用 0 绑定(bind)，从上到下用 max_int 绑定(bind)。​​

我继续使用 Python 的字典，但发现它非常慢。解决这个问题的另一种方法是创建一个带有 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

Answer 1

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

他们表明 d 中的标准 (3, 8) (没有 .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 3 的 keys() 具有快速的 in 测试，因为 keys() 返回键的 View ，以便 in 运算符可以使用相应字典的哈希表。

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

PS: %timeit 函数由优秀的IPython 提供壳。原始程序可以通过 IPython 使用 %run prog.py 执行。