Более эффективные способы найти количество совпадающих значений, разделяемых двумя итерациями?

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

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

Мы можем использовать Counter, найденный в стандартной библиотеке Python.

Счетчик подсчитывает, сколько раз элемент был найден в итерируемом. Построение его из списка, по сути, дает карту для каждого элемента в списке по количеству вхождений.

Выполнение пересечения множества на двух счетчиках даст нам количество элементов, найденных в обоих списках. Однако вместо того, чтобы находить количество дубликатов, мы ищем, сколько раз элемент соответствует другому элементу. Это означает, что нам нужно использовать умножение вместо минимума для пересечения множества.

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]