Python列表交集效率:generator还是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

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

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是最快的方法。