python - 两个看似相似的 dict 语句的性能差异？

Question

“要避免的一个半陷阱是确保您执行: key in some_dict 而不是 key in some_dict.keys() 。两者在语义上是等效的，但在性能方面后者要慢得多(O(n) 与 O(1 ))。我见过人们这样做 in dict.keys() 认为它更明确，因此更好。”

我在网上找到了这条建议。任何人都可以解释并证明上述性能差异的合理性吗？这两个看似相似的声明的作用为何如此不同？

编辑:更准确地说，字典中的索引比列表中的索引更快吗？据我所知，哈希表是链表数组。该数组是键的数组。因此，在哈希表中查找键应该类似于在键列表中查找该键。 (？)

Answer 1

仅适用于 Python 2。

在 Python 3 中，dict.keys() 返回一个 View 对象 dict_keys，它包装了源 dict 对象:

$ python3
Python 3.5.2 (default, Nov 17 2016, 17:05:23)
>>> d = { 1: 11, 2:22, 3:33 }
>>> k = d.keys()
>>> k
dict_keys([1, 2, 3])
>>> d
{1: 11, 2: 22, 3: 33}
>>> d[4] = 44
>>> k
dict_keys([1, 2, 3, 4])  #!!! k includes the new key that was added to d
>>> 

因此，在 Python 3 中，key in dict.keys() 几乎与 key in dict 一样有效执行:

1. dict.keys() 在 O(1) 时间内创建 dict_keys 对象，然后
2. 查询操作通过 dict_keys 重新路由回 dict，后者在 O(1) 时间内执行。

与 Python 3 不同，在 Python 2 中，dict.keys() 返回一个列表对象，该对象必须在 O(n) 时间内构造:

$ python2
Python 2.7.12 (default, Nov 19 2016, 06:48:10) 
>>> d = { 1: 11, 2:22, 3:33 }
>>> k = d.keys()
>>> k
[1, 2, 3]
>>> d[4] = 44
>>> k
[1, 2, 3]
>>> 

因此，在 Python 2 中，key in dict.keys() (作为测试，而不是作为 for key in dict.keys() 的一部分)将有两个 O(n) 时间复杂度的来源:

1. 构建由 dict.keys() 返回的列表需要 O(n) 时间
2. 检查查询值是否在返回的列表中还需要 O(n) 时间。