Python字典中的'in'子句每次都会调用keys()函数吗？

Question

假设我有一个

dict = {...} #lots of words in dictionary  

我需要做一个

for word in ...: #long list of words
    if word in dict:
        #do something

我的问题是，使用 'if word in dict' 这个写法每次都会调用 dict.keys() 函数吗？这样会不会比我在前面加一个变量 dict_keys = dict.keys() 要慢很多？我说的结果是这个。

dict = {...}
dict_keys = dict.keys()

for word in ...:
    if word in dict_keys:
        #do something

谢谢

Answer 1

简单来说：不是的，更像是 __contains__，它的效率是 O(1)（也就是说，执行起来很快）。

Answer 2

其实，内置的字典（dict）会直接调用它的 __contains__ 方法，这个方法会直接运行一个叫 dict_has_key 的C语言函数，这个函数非常快。所以，第一种方法更好，因为它不需要你去检查字典里所有的键，而调用 keys() 方法就会这样做。

Answer 3

不，foo in mydict 实际上要快很多，比 foo in keys_list 要快。这是因为 dict 是一种哈希表，查找里面的元素是 O(1)，也就是说，无论里面有多少个元素，查找的时间基本上是固定的。而 foo in keys_list 的查找时间是 O(n)，也就是说，随着元素数量的增加，查找的时间会变得更慢。

不过你可以自己测试一下：

$ python -m timeit -s "x = range(1000)" "15 in x"
1000000 loops, best of 3: 0.311 usec per loop
$ python -m timeit -s "x = dict.fromkeys(xrange(1000))" "15 in x"
10000000 loops, best of 3: 0.0515 usec per loop

所以直接在 dict 中检查1000个元素的速度要快一个数量级，不考虑 .keys() 的时间。