python - 对于大型列表，Python 的 'in' 或 'not in' 运算符的效率如何？

Question

我有一个超过 100000 个值的列表，我正在遍历这些值并检查每个值是否包含在另一个随机值列表(相同大小)中。

我通过使用 if item[x] in randomList 来做到这一点。这有多有效？ python 是对每个容器进行某种哈希处理，还是在内部直接搜索另一个容器以找到我要查找的元素？

此外，如果它以线性方式执行此搜索，那么它是否会创建 randomList 的字典并使用它进行查找？

Answer 1

in 是由它所应用的对象的 __contains__ 魔术方法实现的，因此效率取决于它。例如，set、dict 和 frozenset 将是基于散列的查找，而 list 将需要线性搜索。但是，xrange(或 Python 3.x 中的 range)有一个 __contains__ 方法，它不需要线性搜索，而是可以使用开始/停止/步骤信息以确定真值。 (例如:7 in xrange(4, 1000000) 不是线性完成的)。

自定义类可以自由实现 __contains__，但它们认为合适，但如果“不明显”，理想情况下应在文档中提供有关如何实现的一些信息。