6

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

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

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

4

3 回答 3

14

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

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

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

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

于 2013-03-11T04:03:26.710 回答
8

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

于 2013-03-11T03:59:59.957 回答
3

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

于 2013-03-11T03:59:53.877 回答