Python的`in`关键字执行线性搜索吗？

Question

Python如何使用in关键字检查迭代器中是否存在给定值。它执行线性搜索吗？如：

def naive(iterable, val): 
    for i in range(len(l)): 
     if iterable[i]==val: 
      return True 
    return False 

？或者它有不同的做法。除了线性搜索？

Answer 1

Python的in运营商要求在容器上的__contains__神奇的功能。这对不同容器以不同方式实施。

对于str英格斯，list S和tuple S，它是一个线性搜索（O(N)），但因为它在C'S实现它可能会比你在你的问题有纯Python的速度更快。

对于set s和dict s，这是一个散列表查找，速度要快得多（O(1)平均大小写）。

其他容器将具有不同的性能特征。我不认为标准库中有任何内容，但是平衡树数据结构可能是O(log N)。

Answer 2

如果它是一个线性数据结构，是的，这是一个线性搜索。例子：一个列表，一个字符串。如果它是一个集合，它是一个O(1)操作，或者如果我们正在检查密钥是否在字典中也是O(1)。

Answer 3

in关键字取决于您所调用的对象类中的__contains__方法的实现。这意味着对于任何不可散列的东西（列表，字符串），它执行线性搜索，但对于可排列的数据结构（字典，集合），它将被分摊到不变的时间。