python - 为什么以元组为键的'in'运算符在python中这么慢？

Question

我有一个字典，例如：

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

然后我查询密钥：

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

当有百万条记录时，速度很痛苦，'in'操作符有什么问题吗？

是顺序搜索吗​​？

我必须 concat str 作为绕过这个问题的关键。

Answer 1

你应该使用

(k1,k2) in d

而不是调用d.keys().

在 Python 2 中按照自己的方式进行操作会导致线性搜索，并且会否定dict. 在 Python 3 中，您的代码很高效（请参阅下面的注释），但我的版本更清晰。

Answer 2

鉴于诺伦皇室的加入，我想我会注意到你实际上可以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 微秒。这快了近二十万倍。

只是认为这值得一提。

编辑：

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

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。