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

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”循环更快，更有效的方法了，我敢说比此方法更Python化的方法来解决此问题？

Answer 1

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

Counter计算可重复项中找到某项的次数。从列表构造它实际上会产生一个从列表中每个项目到出现次数的映射。

在两个Counter上执行集合相交将为我们提供两个列表中找到的项目的计数。然后，我们可以对其求和以找到共享的项目总数。

from collections import Counter

def num_dups(l1, l2)
  c1, c2 = Counter(l1), Counter(l2)
  dups = c1 & c2
  return sum(dups.values())

Answer 2

计数器支持使用&运算符的多集交集，并使用+运算符添加计数：

>>> from collections import Counter
>>> list1 = list("abba")   
>>> list2 = list("bbanana") 
>>> c1 = Counter(list1)
>>> c2 = Counter(list2)
>>> c = c1 + c2
>>> 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