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)

其他建议？

提前谢谢你，

安农

Answer 1

这两个都没有。最好的方法是使用集合。

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

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

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

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

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) 

解决方案2:设置

时间流逝：0.09089064598083496

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

解决方案3: numpy.intersect1d

时间流逝：0.323300838470459

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

结论

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