查找两个可迭代对象共享的匹配值数量的更有效方法？

Question

编辑：寻找比赛的数量而不是比赛本身。无法用集合或 [x for x in list1 if x in list2] 类型的方式解决。 list1.count(x) if x in list2 虽然有效。

假设您有两个列表，list1 和 list2，并且想要查找 list1 中的值与 list2 中的值匹配的次数。

我使用以下代码成功执行了此任务 -

sum([x==y for x in list1 for y in list2])

问题是这段代码无法有效地处理更大的列表。有没有比 "double for" 循环更快、更有效、我敢说更 pythonic 的方法来解决这个问题？

Answer 1

计数器支持使用 & 运算符的多重集交集：

>>> from collections import Counter
>>> list1 = list("abba")   
>>> list2 = list("bbanana") 
>>> c1 = Counter(list1)
>>> c2 = Counter(list2)
>>> sum(c1[k]*c2[k] for k in c1 & c2)  # O(n)
10
>>> sum([x==y for x in list1 for y in list2])  # O(n**2)
10

Answer 2

我们可以使用 Python 标准库中的 Counter。

计数器计算在可迭代对象中找到某项的次数。从列表构建它本质上会产生从列表中的每个项目到出现次数的映射。

对两个计数器执行集交集将为我们提供在两个列表中找到的项目的计数。但是，我们不是查找重复项的数量，而是查找一个元素与另一个元素匹配的次数。这意味着我们需要对集合交集使用乘法而不是最小值。

from collections import Counter

def merge(d1, d2):
  return {k: (d1[k], d2[k]) for k in d1 if k in d2}

def num_dups(l1, l2):
  c1, c2 = Counter(l1), Counter(l2)
  dups = merge(c1, c2)
  return sum(x * y for x, y in dups.values())

Answer 3

这种方法与其他方法截然不同，对于您的要求来说可能过于简单 - 但我想我会把它混在一起。

它解决了这个请求：

假设您有两个列表，list1 和 list2，并且想要查找 list1 中的值与 list2 中的值匹配的次数。

怎么样：

a = ['a', 'b', 'c', 'd', 'e']
b = ['a', 'a', 'c', 'c', 'c']

[b.count(i) for i in a]

输出：

[2, 0, 3, 0, 0]

查找两个可迭代对象共享的匹配值数量的更有效方法？

More efficient ways to find the number of matching values shared by two iterables?

python

arrays

sorting

list

matching

输出：