Учитывая список наборов:
allsets = [set([1, 2, 4]), set([4, 5, 6]), set([4, 5, 7])]
Что такое pythonic способ вычислить соответствующий список наборов элементов, не имеющих совпадений с другими наборами?
only = [set([1, 2]), set([6]), set([7])]
Есть ли способ сделать это с пониманием списка?
Чтобы избежать квадратичного времени выполнения, вы должны сделать начальный проход, чтобы выяснить, какие элементы отображаются более чем в одном наборе:
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, но не кажется, чтобы иметь большое значение в любом случае.
Да, это можно сделать, но вряд ли это pythonic
>>> [(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.