3

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

我正在使用if item[x] in randomList. 这效率如何？python 是否对每个容器进行某种散列处理，还是在内部直接搜索另一个容器以找到我正在寻找的元素？

此外，如果它进行线性搜索，那么它会创建一个 randomList 的字典并用它进行查找吗？

4

4 回答 4

8

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

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

于 2013-06-20T17:50:46.810 回答
2

您需要将列表预先转换为一组，其中散列可用于 O(1) 查找。

见http://wiki.python.org/moin/TimeComplexity

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

于 2013-06-20T17:43:47.223 回答
0

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

于 2013-06-20T17:55:35.820 回答
0

如果两个列表已排序，则可以不使用集合来执行此操作，如下所示：

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]

该算法在此处描述。

于 2013-06-20T17:59:06.060 回答