为什么'键入d.keys()'在O(n)时完成,而'key in d'在O(1)中完成？

Question

我对这个问题有一个后续问题.原始问题的一位评论者提到他过去曾经误认为人们使用如下语法:

key in d.keys()

在O(n)时间内完成,而不是

key in d

在O(1)时间内完成,没有意识到差异.直到今天(当我在试图理解为什么我的代码运行如此缓慢之后偶然发现原始问题时),我才是其中之一.我尝试使用Python 2.7.5验证注释的准确性,果然,这里是timeit的结果:

$ python -m timeit -s 'd=dict.fromkeys(range(100))' '1000 in d.keys()'
100000 loops, best of 3: 2.18 usec per loop
$ python -m timeit -s 'd=dict.fromkeys(range(100))' '1000 in d'
10000000 loops, best of 3: 0.0449 usec per loop
$ python -m timeit -s 'd=dict.fromkeys(range(1000))' '10000 in d.keys()'
100000 loops, best of 3: 17.9 usec per loop
$ python -m timeit -s 'd=dict.fromkeys(range(1000))' '10000 in d'
10000000 loops, best of 3: 0.0453 usec per loop    

对于具有100个密钥的字典,速度差异大约为50倍(2.19 usec/0.0449 usec),对于具有1000个密钥的字典,存在400X差异(17.9 usec/0.0453 usec),对于明确构造的搜索,搜索键太大,无法在字典中找到.换句话说,O(n)与O(1),正如评论者所说.

我的问题:为什么会有所不同？这两种语法看起来几乎相同!显然,Python必须在这两种情况之间做一些非常不同的事情,但究竟在内部究竟发生了什么呢？

Answer 1

d.keys()返回一个列表,它是dict键的副本,而不是视图.构造该列表需要O(n),查找也是如此,即使用list.__contains__迭代键.

另一方面,key in d基本上是电话

d.__contains__(key)

通过dict.__contains__在dict键上进行O(1)散列查找,可以有效地实现该方法.这恰恰是存在的理由为dict数据结构,它是当你访问一个字典,你得到一个快速的O(1)查找同样的原因d[key].

总之,key in d.keys()在python 2中永远不合适.

_{注意:在python3中,这已经改变了,其中使用key in d.keys()将或多或少等同key in d.viewkeys()于python 2.}