odejmowanie nad listą zestawów

Question

otrzymali listę zestawów:

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

Co jest pythonic sposób obliczyć odpowiednią listę zestawów elementów nie mających pokrywać się z innymi zestawami?

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

Czy istnieje sposób, aby to zrobić ze zrozumieniem listy?

Answer 1

Aby uniknąć kwadratowego czasu pracy, którą chcesz dokonać wstępnej przepustkę, aby dowiedzieć się, które elementy pojawiają się w więcej niż jednym zestawie

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

Następnie można po prostu zrobić listę zestawów zachowując wszystkie elementy, które pojawiają się tylko raz:

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

---

Alternatywnie, zamiast konstruowania nondupes z element_counts bezpośrednio, możemy wykonać dodatkową przepustkę do skonstruuj zestaw wszystkich elementów, które pojawiają się dokładnie na jednym wejściu. To wymaga dodatkowego oświadczenia, ale pozwala nam skorzystać z operatora & dla zadanej skrzyżowania, aby lista zrozumienie krótsze i bardziej efektywne:

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] 

Timing wskazuje na to, że za pomocą all_uniques zestaw produkuje znaczne przyspieszenie dla ogólnego procesu eliminacji duplikatów. To około 3.5x speedup na Pythonie 3 dla mocno zduplikowanych zestawów wejściowych, ale tylko o 30% speedup dla ogólnego procesu eliminacji duplikatów w Pythonie 2 z powodu większej ilości czasu zdominowanego przez konstruowanie licznika. Przyspieszenie to jest dość znaczące, ale nie jest tak ważne, jak uniknięcie kwadratowego środowiska wykonawczego, w pierwszej kolejności za pomocą element_counts. Jeśli korzystasz z Pythona 2, a ten kod jest krytyczny pod względem szybkości, możesz użyć zwykłego dict lub collections.defaultdict zamiast Counter.

Innym sposobem byłoby skonstruować dupes zestaw z element_counts i używać original - dupes zamiast original & all_uniques na liście zrozumienia, jak suggested przez Munka. To, czy działa lepiej, czy gorzej niż przy użyciu zestawu all_uniques i &, zależy od stopnia duplikacji danych wejściowych i wersji Pythona, ale także od tego, czy jest to duża różnica.

Answer 2

Tak można to zrobić, ale jest mało pythonic

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

Niektóre odniesienia na zbiorach można znaleźć in the documentation. Operator * nazywa się unpacking operator.

Answer 3

Innym rozwiązaniem z 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])] 

wykonalne także bez rozpakowywania i stosując zamiast chain.from_iterable.

Answer 4

Nieco inne rozwiązanie z użyciem licznika i ze zrozumieniem, aby skorzystać z operatora - dla ustawionej różnicy.

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]