为什么'in'运算符使用元组作为python中的键如此慢？

Question

我有一个词典,如:

d=dict()
d[('1','2')] = 'value'

然后我查询密钥:

if (k1,k2) in d.keys():

当有百万条记录时,速度是一种痛苦,"运行"运算符有什么问题吗？

它是顺序搜索吗​​？

我必须将str作为绕过这个问题的关键.

Answer 1

你应该用

(k1,k2) in d

而不是打电话d.keys().

按照自己的方式行事,在Python 2中将导致线性搜索,而不是否定a的好处dict.在Python 3中,您的代码是高效的(请参阅下面的评论),但我的版本更清晰.

Answer 2

鉴于Nolen Royalty的补充,我想我会注意到你可以timeit用更好的方式进行测试.通过将构造移动dict到设置功能,我们可以只对时间进行操作dict,给我们一个可以轻松比较的结果.

在3.2中:

python -m timeit -s 'd = {(str(i), str(j)):"a" for i in range(100) for j in range(1000)}' '_ = ("1", "2") in d.keys()' '_ = (1, 2) in d.keys()'
1000000 loops, best of 3: 0.404 usec per loop

python -m timeit -s 'd = {(str(i), str(j)):"a" for i in range(100) for j in range(1000)}' '_ = ("1", "2") in d' '_ = (1, 2) in d'
1000000 loops, best of 3: 0.247 usec per loop

你可以看到差异.在3.x中,直接使用它会使dict我们的速度提高近2倍,这也不错.

在2.7.3中:

python2 -m timeit -s 'd = {(str(i), str(j)):"a" for i in range(100) for j in range(1000)}' '_ = ("1", "2") in d.keys(); _ = (1, 2) in d.keys()'
10 loops, best of 3: 36.3 msec per loop

python2 -m timeit -s 'd = {(str(i), str(j)):"a" for i in range(100) for j in range(1000)}' '_ = ("1", "2") in d' '_ = (1, 2) in d'
10000000 loops, best of 3: 0.197 usec per loop

在2.x中,差异确实令人震惊.使用dict.keys()需要36,300微秒,而只dict需要0.2微秒.这快了近20万倍.

只是觉得这值得注意.

编辑:

蒂姆做了一个有趣的评论,所以我决定做另一个测试.我尝试构建列表,然后只进行哈希查找,结果如下:

python2 -m timeit -s 'd = {(str(i), str(j)):"a" for i in range(100) for j in range(1000)}' 'd.keys()' 'd.keys()'
100 loops, best of 3: 5.84 msec per loop

python2 -m timeit -s 'd = {(str(i), str(j)):"a" for i in range(100) for j in range(1000)}' -s 'l=d.keys()' '_ = ("1", "2") in l' '_ = ("1", "2") in l'
10 loops, best of 3: 25.3 msec per loop

您可以看到,在这样的大型字典中,构建列表大约需要1/6的时间,在5/6的时间内搜索列表.