作为键慢的Python元组？

Question

我试图快速查找字典中的排序元组;回答“这个元组（3,8）是否具有相关价值的问题，如果是，它是什么？”。让元组中的整数由下面的0和上面的max_int绑定。

我继续使用Python的字典却发现是相当缓慢的。解决这个问题的另一种方法是创建一个带有max_int（大部分是空的）字典的列表T，并且对于每个元组（3,8）将T [3] [8] =值。 虽然这正是Python采用字典的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/no .keys区别在于(3, 8) in d.keys()建立了密钥列表（在Python 2中），然后在此列表中查找(3, 8)，这比在字典d的哈希表中查找(3, 8)慢得多。

如在评论所指出的，定时结果是不同的使用Python 3：Python 3中的keys()具有快速in测试，因为keys()返回代替上的键的图，使得in操作员可使用的哈希表中的相应字典。

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

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

Answer 2

你为不同的值测试。在词典版本中，有一个100,000个键的查找，而在桶列表结构中，查找仅用于10,000个键。

除此之外，这段代码会减慢速度：(3,8) in d.keys()如果您只是写了(3,8) in d，那么两个版本的查找时间都会非常相似，而且差别可以忽略不计。试试这个修改的测试，看看自己：

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 

的原因观察到的行为是，无论(3,8) in d.keys()和8 in t[3].keys()是每次创建密钥的一个新的临时名单，但第二个版本创建短名单。如果您只是使用了成语key in dictionary，则不会再创建临时列表，并且两种方法的表现都看起来相似。

我与第一个版本去，要简单得多，更容易阅读和理解并习惯 - 在正确使用的情况下，执行一样好第二个版本。

Answer 3

比较(a, b) in d与b in t[a]的速度有些奇怪，因为后者假定a必须存在。

无论如何，第一种方式应该总是更快。两个版本都有a和b。第一个是分配一个元组并对其进行散列的额外开销。但是，第二种方法是执行两个单独的字典查找。