Можно ли извлечь список пересечений, который содержит повторяющиеся значения?

Question

Я хочу получить пересечение списков, где дублирование не устранено.И я надеюсь, что этот метод - быстрый способ не использовать циклы.Ниже была моя попытка, но этот метод не удался, потому что дубликаты были удалены.

a = ['a','b','c','f']
b = ['a','b','b','o','k']

tmp = list(set(a) & set(b))
>>>tmp
>>>['b','a']

Я хочу, чтобы результат был ['a', 'b', 'b'].

В этом методе 'a' является фиксированным значениеми 'b' является значением переменной.

И концепция извлечения значения 'a' из 'b'.

Существует ли способ извлечь список перекрестных значений, которыйне удалить повторяющиеся значения?

Answer 1

Я думаю, что это не быстрее, чем цикл, и, наконец, вам, вероятно, все еще нужен цикл для извлечения результата.В любом случае ...

from collections import Counter

a = ['a','a','b','c','f']
b = ['a','b','b','o','k']

count_b = Counter(b)
count_ab = Counter(set(b)-set(a))
count_b - count_ab

#=> Counter({'a': 1, 'b': 2})

---

Я имею в виду, если res содержит результат, вам необходимо:

[ val for sublist in [ [s] * n for s, n in res.items() ] for val in sublist ]
#=> ['a', 'b', 'b']

Answer 2

Если вы настаиваете на том, чтобы не использовать for явно , тогда это будет работать:

>>> list(filter(a.__contains__, b))
['a', 'b', 'b']

Но прямой вызов магических методов, таких как __contains__, не является рекомендуемой практикой для лучшихнасколько мне известно, рассмотрим это вместо:

>>> list(filter(lambda x: x in a, b))
['a', 'b', 'b']

И если вы хотите улучшить поиск в a с O (n) до O (1) , затем сначала создайте set:

>>> a_set = set(a)
>>> list(filter(lambda x: x in a_set, b))
['a', 'b', 'b']

Answer 3

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

В соответствии с тем, как в настоящее время работают дубликаты, общими элементами являются 'a' и 'b', а списки перечней пересечений 'a' с кратностью 1 и 'b' с кратностью 2. Примечание 'a' встречается один раз в обоих списках a и b , но 'b' встречается дважды на b .Список пересечений перечисляет общий элемент с кратностью, равной списку, имеющему этот элемент с кратностью максимум .

Ответ - да .Тем не менее, цикл может быть вызван неявно - хотя вы хотите, чтобы ваш код не использовал явно операторы цикла.Этот алгоритм, однако, всегда будет итеративным.

Шаг 1: Создайте набор пересечений, Intersect, который не содержит дубликатов (вы уже сделали это).Преобразование в список для сохранения индексации.

Шаг 2: Создайте второй массив, IntersectD.Создайте новую переменную Freq, которая подсчитывает максимальное количество вхождений для этого общего элемента, используя count.Используйте Intersect и Freq для добавления элемента Intersect[k] несколько раз в зависимости от его соответствующего Freq[k].

Пример кода с 3 списками будет

a = ['a','b','c','1','1','1','1','2','3','o']
b = ['a','b','b','o','1','o','1']
c = ['a','a','a','b','1','2']

intersect = list(set(a) & set(b) & set(c)) # 3-set case
intersectD = []

for k in range(len(intersect)):
  cmn = intersect[k]
  freq = max(a.count(cmn), b.count(cmn), c.count(cmn)) # 3-set case
  for i in range(freq): # Can be done with itertools
    intersectD.append(cmn)

>>> intersectD
>>> ['b', 'b', 'a', 'a', 'a', '1', '1', '1', '1']

Для случаев, включающих более двух списков, freq для этого общего элемента может быть вычислено с использованием более сложного пересечения множеств и выражения max.Если используется список списков, freq может быть вычислено с использованием внутреннего цикла.Вы также можете заменить внутренний i-цикл выражением itertools из Как подсчитать вхождения элемента списка? .

Answer 4

Решение может быть

good = set(a)
result = [x for x in b if x in good]

, здесь есть две петли;один - это цикл построения множеств set (который реализован в C, в сто раз быстрее, чем все, что вы можете сделать в Python), другой - понимание и выполнение в интерпретаторе.Первый цикл сделан, чтобы избежать линейного поиска в a для каждого элемента b (если a становится большим, это может быть серьезной проблемой).

Обратите внимание, что использование filter вместовероятно, не получит большого выигрыша (если вообще что-нибудь), потому что, несмотря на то, что цикл filter находится в C, для каждого элемента он должен будет вернуться к интерпретатору, чтобы вызвать функцию фильтрации.

Обратите внимание, что если вы заботитесьЧто касается скорости, то, вероятно, Python не является хорошим выбором ... например, может быть, PyPy был бы лучше здесь, и в этом случае просто написание оптимального алгоритма явно должно быть в порядке (избегая повторного поиска a для дубликатов, когда они последовательны вb как это происходит в вашем примере)

good = set(a)
res = []
i = 0
while i < len(b):
    x = b[i]
    if x in good:
        while i < len(b) and b[i] == x:  # is?
            res.append(x)
            i += 1
    else:
        i += 1

Конечно, при оптимизации производительности единственный реальный способ - это попытаться измерить реальные данные в реальной системе ... угадывание работает все меньше и меньше по мере развития технологий истановится более сложным.

Answer 5

>>a = ['a','b','c','f']
>>b = ['a','b','b','o','k']
>>items = set(a)
>>found = [i for i in b if i in items]
>>items
{'f', 'a', 'c', 'b'}
>>found
['a', 'b', 'b']

Это должно сделать вашу работу.