python - Python列表交集效率：生成器还是过滤器（）？

Question

我想在 Python (2.7) 中与两个列表相交。我需要结果是可迭代的：

list1 = [1,2,3,4]
list2 = [3,4,5,6]
result = (3,4) # any kind of iterable

提供一个完整的迭代将在交集之后首先执行，以下哪个更有效？

使用生成器：

result = (x for x in list1 if x in list2)

使用过滤器（）：

result = filter(lambda x: x in list2, list1)

其他建议？

在此先感谢，
安农

score 26 · Accepted Answer

这些都不是。最好的方法是使用集合。

list1 = [1,2,3,4]
list2 = [3,4,5,6]
result = set(list1).intersection(list2)

集合是可迭代的，因此无需将结果转换为任何内容。

score 8 · Accepted Answer

您的解决方案的复杂性为O(m*n)，其中m和n是两个列表的各自长度。您可以提高O(m+n)对其中一个列表使用集合的复杂性：

s = set(list1)
result = [x for x in list2 if x in s]

在速度比可读性更重要的情况下（即几乎从不），您还可以使用

result = filter(set(a).__contains__, b)

这比我机器上的其他解决方案快约 20%。

score 5 · Accepted Answer

我试图比较列表交集的3种方法的速度：

import random

a = [random.randint(0, 1000) for _ in range(1000)]
b = [random.randint(0, 1000) for _ in range(1000)]

解决方案 1：列表理解

时间流逝：8.95265507698059

import time
start = time.time()
for _ in range(1000):
    result = [x for x in a if x in b]
elapse = time.time() - start
print(elapse)

时间流逝：0.09089064598083496

start = time.time()
for _ in range(1000):
    result = set.intersection(set(a), set(b))
elapse = time.time() - start
print(elapse)

时间流逝：0.323300838470459

start = time.time()
for _ in range(1000):
    result = np.intersect1d(a, b)
elapse = time.time() - start
print(elapse)

我认为使用set.intersection是最快的方法。

score 1 · Accepted Answer

对于列表，最有效的方法是使用：

result = set(list1).intersection(list2)

如前所述，但对于 numpy 数组，intersection1d函数更有效：

import numpy as np
result = np.intersection1d(list1, list2)

特别是，当您知道列表没有重复值时，您可以将其用作：

result = np.intersection1d(list1, list2, assume_unique=True)