Python元组作为键慢？

Question

我正在尝试在字典中实现快速查找已排序的元组; 回答"元组(3,8)是否具有相关价值的问题,如果是,它是什么？".让元组中的整数从下面绑定0,从上面绑定max_int.

我继续使用Python的dict,但发现它很慢.解决这个问题的另一种方法是创建一个包含max_int(通常为空)dicts的列表T,并为每个元组(3,8)设置T [3] [8] = value.我虽然这正是Python用dicts采用的bucket-hash方法,但后者在这里快了大约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

他们表明,标准(3, 8) in d(没有.keys()列表构建)实际上比(不太常规)8 in t[3]方法快一点,并且速度是问题相对较快的两倍8 in t[3].keys().这个.keys/没有.keys区别来自于(3, 8) in d.keys()构建密钥的列表(在Python 2中)然后(3, 8)在此列表中查找的事实,这比(3, 8)在字典的哈希表中查找要慢得多d.

正如评论中所指出的,时序结果与Python 3不同:Python 3 keys()具有快速in测试,因为keys()返回键而不是视图,因此in操作员可以使用相应字典的哈希表.

原始问题的速度差异来自d.keys()构建相对较长的列表的事实,与之相比t[3].keys().

PS:该%timeit功能由优秀的IPython shell提供.原始程序可以通过IPython执行%run prog.py.