Subtraction über eine Liste von Sätzen

Question

eine Liste von Sätzen Gegeben:

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

Was ist ein pythonic Weg, um die entsprechende Liste von Gruppen von Elementen, die keine Überschneidungen mit anderen Sätzen zu berechnen?

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

Gibt es eine Möglichkeit, dies mit einem Listenverständnis zu tun?

Answer 1

quadratische Laufzeit zu vermeiden, sollten Sie einen Anstich, um herauszufinden, welche Elemente erscheinen in mehr als einen Satz machen wollen:

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

Dann können Sie einfach machen Sie eine Liste von Sätzen Halte alle Elemente, die erscheinen nur einmal:

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

---

Alternativ kann statt direkt nondupes von element_counts konstruieren, können wir einen zusätzlichen Pass machen konstruiere eine Menge aller Elemente, die genau in einer Eingabe erscheinen. Dies erfordert eine zusätzliche Erklärung, aber es erlaubt uns, die Vorteile der & Operator für Schnittmenge zu nehmen die Liste Verständnis kürzer und effizienter zu machen:

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] 

Zeit zeigen scheint, dass eine all_uniques Satz mit erzeugt eine erhebliche Beschleunigung für den gesamten Dublettenentfernungsprozess. Es ist bis zu einem 3.5x speedup auf Python 3 für stark-doppelte Eingabesätze, obwohl nur über eine 30% speedup für die gesamte Duplikat-Beseitigung Prozess auf Python 2 aufgrund mehr der Laufzeit wird von der Konstruktion des Counters dominiert. Diese Beschleunigung ist ziemlich beträchtlich, wenngleich nicht annähernd so wichtig wie das Vermeiden einer quadratischen Laufzeit unter Verwendung von element_counts an erster Stelle. Wenn Sie Python 2 verwenden und dieser Code geschwindigkeitskritisch ist, sollten Sie statt Counter einen gewöhnlichen dict oder einen collections.defaultdict verwenden.

Eine andere Möglichkeit wäre, einen dupes Satz von element_counts zu konstruieren und original - dupes statt original & all_uniques in der Liste Verständnis, wie suggested von Munk zu verwenden. Ob diese Leistung besser oder schlechter ist als die Verwendung eines all_uniques Sets und &, hängt vom Grad der Duplizierung in Ihrer Eingabe und von der Python-Version ab, in der Sie sich befinden, aber doesn'tseem macht einen großen Unterschied.

Answer 2

Ja, es kann getan werden, aber kaum pythonic

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

Einige Bezug auf Mengen in the documentation gefunden werden kann. Der Operator * heißt unpacking operator.

Answer 3

Eine andere Lösung mit 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])] 

auch ohne Auspacken machbar und chain.from_iterable stattdessen verwenden.

Answer 4

Eine etwas andere Lösung mit Zähler und Comprehensions, um den - Operator für Set-Differenz zu nutzen.

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]