<分区>
Python 如何使用 in 关键字检查给定值是否存在于可迭代对象中。它执行线性搜索吗？喜欢:
def naive(iterable, val):
for i in range(len(l)):
if iterable[i]==val:
return True
return False
?或者它有不同的方式来做到这一点。除了线性搜索？
<分区>
Python 如何使用 in 关键字检查给定值是否存在于可迭代对象中。它执行线性搜索吗？喜欢:
def naive(iterable, val):
for i in range(len(l)):
if iterable[i]==val:
return True
return False
?或者它有不同的方式来做到这一点。除了线性搜索？
最佳答案
Python 的 in 运算符调用容器上的 __contains__ 魔法函数。这是针对不同的容器以不同的方式实现的。
对于strings、lists和tuples，这是一个线性搜索(O(N) )，尽管因为它是用 C 实现的，所以它可能比您在问题中使用的纯 Python 更快。
对于 set 和 dict，它是一个哈希表查找，速度要快得多(O(1) 平均情况).
其他容器将具有不同的性能特征。我认为标准库中没有，但平衡树数据结构可能是 O(log N)。
关于python - Python 的 `in` 关键字是否执行线性搜索？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15330969/