对于大型列表，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__，但理想情况下，如果"不明显"，则应在文档中提供一些关于它如何实现的信息。

Answer 2

您需要将列表预先转换为一个集合，在该集合中可以使用哈希进行O（1）查找。

请参阅http://wiki.python.org/moin/TimeComplexity

（通常，你必须搜索"经典"列表中的每个元素，以判断其中是否有内容（除非你的数据结构也保留了一组所有元素，但这会增加大量的时间和空间复杂性，程序员可以自己实现）。）

Answer 3

ninjagecko已经回答了列表（和元组FWIW）的具体情况，一般答案是："这取决于‘容器’实现"（我引用‘容器’，因为它也可以是生成器）。对于内置类型，您需要用于快速查找的集合或dict。否则，您最好检查容器的文档或实现。

Answer 4

如果对两个列表进行排序，则可以在不使用集合的情况下执行此操作，如下所示：

def gen(P1, P2):
    i, j = 0, 0
    I, J = len(P1), len(P2)
    while i != I and j != J:
        if P1[i] == P2[j]:
            yield P1[i]
            i, j = i + 1, j + 1
        else:
            if P1[i] < P2[j]:
                i += 1
            else:
                j += 1

这返回P1和P2的交点：

>>> P1 = [1, 2, 3, 5, 90]
>>> P2 = [2, 3, 5, 30, 48]
>>> list(gen(P1, P2))
[2, 3, 5]

这里对算法进行了描述。