More Efficient Ways To Find The Number Of Matching Values Shared By Two Iterables?

EDIT: Looking for the number of matches not the matches themselves. Cannot solve with sets or [x for x in list1 if x in list2] type manner. list1.count(x) if x in list2 works thoug

Solution 1:

Counters support multiset intersections with the & operator:

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

Solution 2:

We can use Counter found in the Python standard library.

Counter counts the number of times an item is found in an iterable. Constructing it from a list essentially yields a map from each item in the list to the number of occurrences.

Performing set intersection on two Counter's will give us the counts for items found in both lists. However, instead of finding the number of duplicates, we are looking for the number of times an element matches another element. This means we need to use multiplication instead of min for set intersection.

from collections import Counter

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

defnum_dups(l1, l2):
  c1, c2 = Counter(l1), Counter(l2)
  dups = merge(c1, c2)
  returnsum(x * y for x, y in dups.values())

Solution 3:

This approach is radically different from the others, and possibly too simplistic for your requirements - but thought I'd throw it in the mix.

It addresses this request:

• Let's say you have two lists, list1 and list2, and want to find the number of times a value from list1 matches a value from list2.

How about:

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

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

Output:

[2, 0, 3, 0, 0]