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__方法的實現。這意味着對於任何不可散列的東西（列表，字符串），它執行線性搜索，但對於可排列的數據結構（字典，集合），它將被分攤到不變的時間。