Как вычесть элементы одного списка из другого в python

Пересечение списков, совпадающие элементы двух списков

В данной задаче речь идет о поиске элементов, которые присутствуют в обоих списках. При этом пересечение списков и поиск совпадающих (перекрывающихся) элементов двух списков будем считать несколько разными задачами.

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

[5, 4, 2, ‘r’, ‘ee’] и [4, ‘ww’, ‘ee’, 3]

Областью их пересечения будет список [4, ‘ee’] .

Если же исходные списки выглядят так:

[5, 4, 2, ‘r’, 4, ‘ee’, 4] и [4, ‘we’, ‘ee’, 3, 4] ,

то списком их совпадающих элементов будет [4, ‘ee’, 4] , в котором есть повторения значений, потому что в каждом из исходных списков определенное значение встречается не единожды.

Начнем с простого — поиска области пересечения. Cначала решим задачу «классическим» алгоритмом, не используя продвинутые возможностями языка Python: будем брать каждый элементы первого списка и последовательно сравнивать его со всеми значениями второго.

a = [5, [1, 2], 2, 'r', 4, 'ee'] b = [4, 'we', 'ee', 3, [1, 2]] c = [] for i in a: for j in b: if i == j: c.append(i) break print(c)

Результат выполнения программы:

[[1, 2], 4, 'ee']

Берется каждый элемент первого списка (внешний цикл for ) и последовательно сравнивается с каждым элементом второго списка (вложенный цикл for ). В случае совпадения значений элемент добавляется в третий список c . Команда break служит для выхода из внутреннего цикла, так как в случае совпадения дальнейший поиск при данном значении i бессмыслен.

Алгоритм можно упростить, заменив вложенный цикл на проверку вхождения элемента из списка a в список b с помощью оператора in :

a = [5, [1, 2], 2, 'r', 4, 'ee'] b = [4, 'we', 'ee', 3, [1, 2]] c = [] for i in a: if i in b: c.append(i) print(c)

Здесь выражение i in b при if по смыслу не такое как выражение i in a при for . В случае цикла оно означет извлечение очередного элемента из списка a для работы с ним в новой итерации цикла. Тогда как в случае if мы имеем дело с логическим выражением, в котором утверждается, что элемент i есть в списке b . Если это так, и логическое выражение возвращает истину, то выполняется вложенная в if инструкция, то есть элемент i добавляется в список c .

Принципиально другой способ решения задачи – это использование множеств. Подходит только для списков, которые не содержат вложенных списков и других изменяемых объектов, так как встроенная в Python функция set() в таких случаях выдает ошибку.

a = [5, 2, 'r', 4, 'ee'] b = [4, 1, 'we', 'ee', 'r'] c = list(set(a) & set(b)) print(c)

['ee', 4, 'r']

Выражение list(set(a) & set(b)) выполняется следующим образом.

1. Сначала из списка a получают множество с помощью команды set(a) .
2. Аналогично получают множество из b .
3. С помощью операции пересечения множеств, которая обозначается знаком амперсанда & , получают третье множество, которое представляет собой область пересечения двух исходных множеств.
4. Полученное таким образом третье множество преобразуют обратно в список с помощью встроенной в Python функции list() .

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

Однако если мы вернемся к решению задачи без использования множеств и добавим в первый список повтор значения, то получим некорректный результат:

В список пересечения попадают оба равных друг другу значения из первого списка. Это происходит потому, что когда цикл извлекает, в данном случае, вторую 4-ку из первого списка, выражение i in b также возвращает истину, как и при проверке первой 4-ки. Следовательно, выражение c.append(i) выполняется и для второй четверки.

Чтобы решить эту проблему, добавим дополнительное условие в заголовок инструкии if . Очередной значение i из списка a должно не только присутствовать в b , но его еще не должно быть в c . То есть это должно быть первое добавление такого значения в c :

a = [5, 2, 'r', 4, 'ee', 4] b = [4, 'we', 'ee', 3] c = [] for i in a: if i in b and i not in c: c.append(i) print(c)

[4, 'ee']

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

Алгоритмом решения такой задачи может быть следующий:

1. В цикле будем перебирать элементы первого списка.
2. Если на текущей итерации цикла взятого из первого списка значения нет в третьем списке, то только в этом случае следует выполнять все нижеследующие действия. В ином случае такое значение уже обрабатывалось ранее, и его повторная обработка приведет к добавлению лишних элементов в результирующий список.
3. С помощью спискового метода count() посчитаем количество таких значений в первом и втором списке. Выберем минимальное из них.
4. Добавим в третий список количество элементов с текущим значением, равное ранее определенному минимуму.

a = [5, 2, 4, 'r', 4, 'ee', 1, 1, 4] b = [4, 1, 'we', 'ee', 'r', 4, 1, 1] c = [] for item in a: if item not in c: a_item = a.count(item) b_item = b.count(item) min_count = min(a_item, b_item) # c += [item] * min_count for i in range(min_count): c.append(item) print(c)

[4, 4, 'r', 'ee', 1, 1]

Если значение встречается в одном списке, но не в другом, то метод count() другого вернет 0. Соответственно, функция min() вернет 0, а цикл с условием i in range(0) не выполнится ни разу. Поэтому, если значение встречается в одном списке, но его нет в другом, оно не добавляется в третий.

При добавлении значений в третий список вместо цикла for можно использовать объединение списков с помощью операции + и операцию повторения элементов с помощью * . В коде выше данный способ показан в комментарии.

X Скрыть Наверх

Решение задач на Python

Быстрое вычитание списков

В случае, когда количество элементов списков A и B высоко (порядка 100 000 и выше), способ естественно работает очень медленно. Возможно ли реализовать подобный поиск быстрее? Если да, то как именно?

Отслеживать
Denis Leonov
задан 22 мар 2017 в 6:45
Denis Leonov Denis Leonov
540 4 4 золотых знака 10 10 серебряных знаков 24 24 бронзовых знака

4 ответа 4

Сортировка: Сброс на вариант по умолчанию

i in B это O(m) операция для списков ( m = len(B) ). Поэтому ваш код это O(n * m) алгоритм ( n = len(A) ), то есть для длин списков ~ 100_000 (10 5 ) ваша реализация вычитания списков займёт порядка 10_000_000_000 (10 10 ) операций. Если при работе с чуть бОльшими списками в телефоне вдруг всё начинает тормозить, когда для маленьких списков всё летает, то одно из вероятных объяснений, что программист использовал квадратичный алгоритм вместо линейного (или квази-линейного).

Можно значительно улучшить производительность (если все элементы списка хэшируются) с помощью set() :

Bset = frozenset(B) C = [item for item in A if item not in Bset] # C = A - B 

item in Bset это O(1) операция (в среднем). Поэтому C список вычисляется за O(n + m) (линейный алгоритм), что значительно лучше O(n * m) для больших B .

Обратите внимание, что set(A) не вызывается, иначе получатся результаты отличные от кода в вашем вопросе, если в A есть повторяющиеся элементы или если вы хотите исходный порядок в A сохранить:

>>> A = "abracadabra" >>> B = ['a', 'b', 'c'] >>> Bset = frozenset(B) >>> [item for item in A if item not in Bset] ['r', 'd', 'r'] 

Обратите внимание, ‘r’ встречается дважды в результате и относительный порядок ‘r’ и ‘d’ сохранён.

Если элементы не являются хэшируемыми (к примеру вложенные списки), то можно отсортировать B и использовать двоичный поиск, чтобы определить присутствует ли элемент в отсортированной последовательности:

from bisect import bisect_left def contains(sorted_seq, item): i = bisect_left(sorted_seq, item) return i != len(sorted_seq) and sorted_seq[i] == item 

>>> A = map(list, "abracadabra") >>> B = [['a'], ['b'], ['c']] >>> Bsorted = sorted(B) >>> [item for item in A if not contains(Bsorted, item)] [['r'], ['d'], ['r']] 

Это O((n + m) * log m) алгоритм. log() функция достаточно медленно растёт, к примеру, log10(10 5 ) == 5 Поэтому не измеряя производительность, сложно сказать какой код (на основе set или sorted) быстрее на заданных входных списках, платформе.

Если дополнительно порядок элементов в B списке не определён ( sorted() не работает) и можно только сравнивать элементы напрямую ( a == b ), то придётся использовать O(n * m) алгоритм аналогичный приведённому в вопросе:

>>> A = [1, "a", 1] >>> B = [[], 1] >>> [item for item in A if item not in B] ['a'] 

Как set(B) так и sorted(B) не работают в этом случае.

Стоит заметить, что C в примере ( [‘a’] ) не содержит единицу хотя она встречается два раза в A списке и только один раз в B .

Чтобы учесть число повторений в B :

C = [] for item in A: try: B.remove(item) except ValueError: C.append(item) # item not in B 

В этом случае C == [‘a’, 1] , а не [‘a’] . Код разрушает B . Алгоритм также O(n * m) .

Для хэшируемых элементов, чтобы учесть количество повторений элементов в B , можно в этом случае collections.Counter использовать как мультимножество:

from collections import Counter A = "abracadabra" B = ['a', 'b', 'c'] Bcount = Counter(B) C = [] for item in A: if Bcount[item] == 0: C.append(item) else: Bcount[item] -= 1 

Результат C == [‘r’, ‘a’, ‘a’, ‘d’, ‘a’, ‘b’, ‘r’, ‘a’] отличается от C == [‘r’, ‘d’, ‘r’] полученного выше алгоритмом, который не учитывает количество повторений в B .

Если порядок элементов в результате не важен, то можно упростить код:

C = list((Counter(A) - Counter(B)).elements()) 

Возможный результат: C == [‘b’, ‘r’, ‘r’, ‘a’, ‘a’, ‘a’, ‘a’, ‘d’] . С точностью до порядка элементов внутри C , он совпадает с предыдущим примером. Оба алгоритма линейные — О(m + n) .

Так как порядок не сохраняется, то имеет смысл использовать просто:

C = Counter(A) - Counter(B) # -> Counter() 

так как иначе использование списка для C может создать впечатление, что порядок элементов учитывается.

Если не нужно учитывать ни порядок ни количество повторений, то разницу списков можно найти, используя set (множество — разновидность @Alban ответа):

C = set(A).difference(B) # ->

Видно, что в зависимости от желаемого определения вычитания для списков, разность разные значения принимает:

A = "abracadabra" B = ['a', 'b', 'c'] # C = A - B # -> # нет порядка, нет повторений # -> Counter() # нет порядка # -> ['r', 'd', 'r'] # порядок сохранён, но без учёта повторений в B # -> ['r', 'a', 'a', 'd', 'a', 'b', 'r', 'a'] # порядок + с учётом повторений в B 

В разных ситуациях разные определения могут быть полезны. Явной очевидной предпочтительной семантики здесь нет — вероятно поэтому операция вычитания ( A — B ) не определена для списков в Питоне.

Python-сообщество

• Начало
• » Python для новичков
• » Вычитание списков?

#1 Окт. 24, 2012 11:21:01

tfox Зарегистрирован: 2012-04-13 Сообщения: 55 Репутация: 0 Профиль Отправить e-mail

Вычитание списков?

Как из одного списка удалить все элементы которые есть в другом списке?

l1 = [1, 2, 3] l2 = [2] # сложение списков работает l3 = l1 + l2 print l3 # а это не работает :( l3 = l1 - l2 print l3 

#2 Окт. 24, 2012 11:29:09

GaiveR От: Зарегистрирован: 2011-08-13 Сообщения: 122 Репутация: 16 Профиль Отправить e-mail

Вычитание списков?

#3 Окт. 24, 2012 12:17:52

dimy44 От: Евпатория Зарегистрирован: 2012-04-21 Сообщения: 463 Репутация: 42 Профиль

Вычитание списков?

>>> lst1 = range(10) >>> lst2 = [1, 1, 4, 5] >>> col = set(lst2) >>> lst1 = [i for i in lst1 if i not in col] >>> lst1 [0, 2, 3, 6, 7, 8, 9] >>> 

это на тот случай, если важно сохранить последовательность элементов уменьшаемого списка.

#4 Окт. 24, 2012 14:14:04

tfox Зарегистрирован: 2012-04-13 Сообщения: 55 Репутация: 0 Профиль Отправить e-mail

Вычитание списков?

dimy44
это на тот случай, если важно сохранить последовательность элементов уменьшаемого списка.

Да. Мне важно сохранить последовательность элементов уменьшаемого списка.
Это выражение тоже сохраняет элементы в том же порядке как они и были:

GaiveR
l3 = list(set(l1).difference(l2))

#5 Окт. 24, 2012 15:01:03

dimy44 От: Евпатория Зарегистрирован: 2012-04-21 Сообщения: 463 Репутация: 42 Профиль

Вычитание списков?

Это уж как карта ляжет.

>>> lst1 = [1, 5, 1, 3, 4, 2, 6]
>>> lst2 = [1, 2]
>>> list(set(lst1).difference(lst2))
[3, 4, 5, 6]
>>>

#6 Окт. 24, 2012 16:33:38

dimy44 От: Евпатория Зарегистрирован: 2012-04-21 Сообщения: 463 Репутация: 42 Профиль

Вычитание списков?

И да, забыл еще указать, что если у Вас в списке будут повторяющиеся элементы, которые не нужно вычитать, то даже если предположить, что очередность не важна, все-равно set испортит Ваш список, т.к. уберет дублирующие элементы.

Удаление элементов одного списка из другого в Python

Очень часто при работе с данными в Python возникает необходимость удалить все элементы одного списка из другого. Допустим, есть два списка: list1 = [1, 2, 3, 4, 5] и list2 = [2, 4] . Задача состоит в том, чтобы получить список, который содержит все элементы list1 , которые не входят в list2 . В данном случае, результатом должен быть список [1, 3, 5] .

Существует несколько путей решения этой проблемы в Python. Наиболее простым и понятным, хоть и не самым эффективным, является использование цикла.

Использование цикла

list1 = [1, 2, 3, 4, 5] list2 = [2, 4] result = [] for i in list1: if i not in list2: result.append(i) print(result) # Вывод: [1, 3, 5]

Этот код проходит по всем элементам list1 и, если элемент не входит в list2 , добавляет его в результирующий список.

Использование списковых включений (list comprehensions)

Списковые включения — это мощный инструмент Python, который позволяет генерировать списки в одну строку кода. Этот метод эффективнее предыдущего и является более «pythonic» способом решения данной задачи.

list1 = [1, 2, 3, 4, 5] list2 = [2, 4] result = [i for i in list1 if i not in list2] print(result) # Вывод: [1, 3, 5]

Использование множеств (set)

Еще одним способом решения данной задачи является использование множеств в Python. Множества — это наборы уникальных элементов, поддерживающие операции над множествами, такие как объединение, пересечение и разность.

list1 = [1, 2, 3, 4, 5] list2 = [2, 4] result = list(set(list1) - set(list2)) print(result) # Вывод: [1, 3, 5]

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

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