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

user_5166824 0
Viewed 136

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

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.

I used the following code to perform this task successfully - 

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

The problem is this code cannot handle larger lists efficiently. Is there a faster, more efficient, dare I say more pythonic way to solve this problem than the "double for" loop?

matching list sorting arrays python
3 Answers

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
user_6740390

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

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

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]
user_63404960
Related