查找列表交集元素数量的快速方法 (Python)

Question

在Python中有没有更快的方法来计算这个值：

len([x for x in my_list if x in other_list])

我尝试使用集合，因为列表的元素是唯一的，但我没有发现任何区别。

len(set(my_list).intersection(set(other_list)))

我正在处理大名单，所以即使是最微小的改进也很重要。谢谢

Answer 1

我认为像这样的生成器表达式会很快

sum(1 for i in my_list if i in other_list)

否则，set 交叉路口的速度与到达

的速度差不多

len(set(my_list).intersection(other_list))

Answer 2

想法是先对两个列表进行排序，然后像我们要合并它们一样遍历它们，以便找到第一个列表中也属于第二个列表的元素。这样我们就有了一个 O(n logn) 算法。

def mycount(l, m):
    l.sort()
    m.sort()
    i, j, counter = 0, 0, 0
    while i < len(l) and j < len(m):
        if l[i] == m[j]:
            counter += 1
            i += 1
        elif l[i] < m[j]:
            i += 1
        else:
            j += 1
    return counter

根据本地测试，在处理 10000 个元素的列表时，它比 len([x for x in a if x in b]) 快 100 倍。

编辑：

考虑到列表元素是唯一的，公共元素在两个列表的并集中出现频率为2。当我们对这个联合进行排序时，它们也会在一起。所以以下也是有效的：

def mycount(l, m):
    s = sorted(l + m)
    return sum(s[i] == s[i + 1] for i in xrange(len(s) - 1))

同样，我们可以使用计数器：

from collections import Counter
def mycount(l, m):
    c = Counter(l)
    c.update(m)
    return sum(v == 2 for v in c.itervalues())

Answer 3

从https://wiki.python.org/moin/TimeComplexity开始，设置两个集合s和t的交集具有时间复杂度：

平均 - O(min(len(s), len(t))

最差 - O(len(s) * len(t))

len([x for x in my_list if x in other_list]) 的复杂度为 O(n^2)，相当于 set.intersection().

的最坏情况

如果您使用set.intersection()，您只需要先将其中一个列表转换为集合：

所以 len(set(my_list).intersection(other_list)) 应该 平均而言 会比嵌套列表理解更快。

Answer 4

简单的方法是找到长度最小的列表...而不是将其用于 set.intersection...，例如：

a = range(100)
b = range(50)

fst, snd = (a, b) if len(a) < len(b) else (b, a)
len(set(fst).intersection(snd))

Answer 5

您可以尝试使用 filter 函数。既然你提到你正在处理巨大的列表，ifilterof itertools 模块将是一个不错的选择：

from itertools import ifilter
my_set = set(range(100))
other_set = set(range(50))
for item in ifilter(lambda x: x in other_set, my_set):
    print item

查找列表交集元素数量的快速方法 (Python)

A fast way to find the number of elements in list intersection (Python)

python

optimization