Вычитание по списку множеств

Учитывая список наборов:

allsets = [set([1, 2, 4]), set([4, 5, 6]), set([4, 5, 7])] 

Что такое pythonic способ вычислить соответствующий список наборов элементов, не имеющих совпадений с другими наборами?

 only = [set([1, 2]), set([6]), set([7])] 

Есть ли способ сделать это со списком?

4 Solutions collect form web for “Вычитание по списку множеств”

Чтобы избежать квадратичного времени выполнения, вы должны сделать начальный проход, чтобы выяснить, какие элементы отображаются более чем в одном наборе:

 import itertools import collections element_counts = collections.Counter(itertools.chain.from_iterable(allsets)) 

Затем вы можете просто составить список наборов, сохраняющих все элементы, которые появляются только один раз:

 nondupes = [{elem for elem in original if element_counts[elem] == 1} for original in allsets] 

В качестве альтернативы, вместо того, nondupes напрямую создавать nondupes из element_counts , мы можем сделать дополнительный проход для построения набора всех элементов, которые отображаются ровно на одном входе. Для этого требуется дополнительное утверждение, но оно позволяет нам использовать оператор & для заданного пересечения, чтобы сделать понимание списка короче и эффективнее:

 element_counts = collections.Counter(itertools.chain.from_iterable(allsets)) all_uniques = {elem for elem, count in element_counts.items() if count == 1} # ^ viewitems() in Python 2.7 nondupes = [original & all_uniques for original in allsets] 

Сроки показывают, что использование набора all_uniques дает существенное ускорение для общего процесса устранения дубликатов. Это примерно до 3,5-кратного ускорения на Python 3 для сильно дублированных наборов ввода, хотя только около 30% ускорения для полного процесса устранения дубликатов на Python 2 из-за большей части времени выполнения, в котором доминирует построение счетчика. Это ускорение довольно существенное, хотя и не так важно, как избежать квадратичного времени выполнения, используя element_counts в первую очередь. Если вы находитесь на Python 2, и этот код является критичным для скорости, вы бы хотели использовать обычный dict или dict вместо Counter .

Другим способом было бы создать набор dupes заданный из element_counts и использовать original - dupes вместо original & all_uniques в понимании списка, как предложено munk. Будет ли это all_uniques лучше или хуже, чем использование набора all_uniques и & будет зависеть от степени дублирования в вашем входе и от того, какая версия Python вы используете, но , похоже , это не имеет большого значения в любом случае.

Да, это можно сделать, но вряд ли питонично

 >>> [(i-set.union(*[j for j in allsets if j!= i])) for i in allsets] [set([1, 2]), set([6]), set([7])] 

Некоторую ссылку на наборы можно найти в документации . Оператор * называется оператором распаковки .

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

 from itertools import chain from collections import Counter allsets = [{1, 2, 4}, {4, 5, 6}, {4, 5, 7}] element_counts = Counter(chain.from_iterable(allsets)) dupes = {key for key in element_counts if element_counts[key] > 1} only = [s - dupes for s in allsets] 

Другое решение с itertools.chain :

 >>> from itertools import chain >>> [x - set(chain(*(y for y in allsets if y!=x))) for x in allsets] [set([1, 2]), set([6]), set([7])] 

Также можно выполнять без распаковки и использования chain.from_iterable .

  • Примените функцию попарно на ряды панды
  • Python Set: почему my_set = {* my_list} недействителен?
  • Python - лучший язык программирования в мире.