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

Ответ 1

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

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 from 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.5x speedup на Python 3 для сильно дублированных наборов входных данных, хотя только около 30% speedup для общего процесса устранения дубликатов на Python 2 из-за большей части времени выполнения, в котором доминирует построение счетчика. Это ускорение довольно существенное, хотя и не так важно, как избежать квадратичного времени выполнения, используя element_counts в первую очередь. Если вы находитесь на Python 2, и этот код имеет критически высокую скорость, вы должны использовать обычный dict или collections.defaultdict вместо Counter.

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

Ответ 2

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

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

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

Ответ 3

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

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]

Ответ 4

Другое решение с 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.