Python 列表交集效率：生成器还是 filter()?

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)

使用filter()函数：

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

还有其他建议吗？

提前谢谢你，
Amnon

Answer 1

我试着比较了三种列表交集的方法的速度：

import random

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

方法一：列表推导

耗时：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) 

方法三：numpy.intersect1d

耗时：0.323300838470459

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

结论

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

Answer 2

你的解决方案的复杂度是 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%。

Answer 3

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

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

集合是可以遍历的，所以不需要把结果转换成其他形式。