python - Python 的 `in` 关键字是否执行线性搜索？

Question

Python 如何检查给定值是否存在于可迭代的 usingin关键字中。它是否执行线性搜索？喜欢：

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

? 或者它有不同的方式来做到这一点。除了线性搜索？

score 14 · Accepted Answer

Python 的in运算符调用__contains__容器上的魔法函数。这对于不同的容器以不同的方式实现。

对于strings、lists 和s，它tuple是一种线性搜索（O(N)

对于sets 和dicts，这是一个哈希表查找，速度要快得多（O(1)平均情况）。

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

score 8 · Accepted Answer

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

score 3 · Accepted Answer

如果它是一个线性数据结构，是的，它是一个线性搜索。示例：列表、字符串。如果它是一个集合，它就是一个O(1)操作，或者如果我们正在检查一个键是否在一个 dict 中也是O(1).

3 回答 3