在Python中快速查找列表交集的元素数量

Question

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

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

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

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

我正在处理大量列表数据，即使是最微小的改进也能提升效率。谢谢。

- van

---

这两个操作不同：第一个是两个列表的“交集”，第二个是“差集”。 - mhawke

你说得对，这是一个愚蠢的错误。正确的解决方案应该是 len(set(my_list).intersection(set(other_list)))。 - van

Answer 1

一种简单的方法是找到最短的列表... 然后使用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))

- Jon Clements

---

你是想找到较短的列表以加快列表设置转换的速度吗？ - van

@nicck，您只需要将第一个列表“去重”后与较长的列表相交- 您只需要在其中一个列表中使用唯一值即可使其作为“set”运行，因为“.intersection”可以接受任何可迭代对象...因此，如果第一个列表仅具有两个唯一值（假设），则当相应的列表有数百万个时，它非常有效率。 - Jon Clements

@nicck 当然，如果您恰好知道一个列表比另一个列表更独特，请优先考虑该列表，这是一种天真的方法，但通常比将两个列表转换为set更好。 - Jon Clements

Answer 2

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

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

否则，使用set求交集将达到最快的速度。

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

- Cory Kramer

---

这个列表到集合的转换不会比我所获得的改进更耗费时间吗？ - van

你需要计时以确定。转换本身需要时间，但通过使 x in other_list 操作更快，它将弥补自己的时间成本。 - Cory Kramer

Answer 3

你可以尝试使用 filter 函数。由于你提到你正在处理大型列表，itertools 模块的 ifilter 是一个不错的选择：

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

- Saksham Varma

Answer 4

从 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)) 在平均情况下比嵌套列表推导式更快。

- mhawke

Answer 5

这个想法是先对两个列表进行排序，然后像合并它们一样遍历它们，以找到也属于第二个列表的第一个列表中的元素。这样我们就有了一个 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倍。

编辑：

考虑到列表元素是唯一的，两个列表的交集元素在两个列表的并集中会出现两次。而且当我们对这个并集进行排序时，它们会排在一起。所以以下方法也是有效的：

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())

- JuniorCompressor

---

你正在执行两个排序操作，然后是一个重复的 while 循环来检索长度 :) - 我在那时停止阅读... - Jon Clements