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__容器上的魔术函数.对于不同的容器,这以不同的方式实现.

对于strings,lists和tuples,它是一个线性搜索(O(N)),虽然它在C中实现它可能比你在问题中的纯python更快.

对于sets和dicts,它是一个哈希表查找,它更快(O(1)平均情况).

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

Answer 2

该in关键字依赖于执行__contains__的对象的类方法,你在呼唤.这意味着对于任何不可清除的内容(列表,字符串),它执行线性搜索,但对于可哈希的数据结构(dict,set),它将按照常量时间进行分摊.