sottrazione su un elenco di gruppi

Question

Dato un elenco di insiemi:

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

cosa è un modo divinatorio per calcolare il corrispondente elenco di insiemi di elementi aventi sovrapposizione con altre serie?

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

C'è un modo per farlo con una comprensione di lista?

Answer 1

Per evitare runtime quadratica, che ci si vuole fare un passo iniziale per capire quali elementi appaiono in più di una serie:

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

allora si può semplicemente fare un elenco di gruppi mantenendo tutti gli elementi che comparire solo una volta:

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

---

in alternativa, invece di costruire nondupes da element_counts direttamente, possiamo fare un passaggio aggiuntivo costruire un insieme di tutti gli elementi che appaiono esattamente in un input. Ciò richiede una dichiarazione aggiuntiva, ma ci permette di sfruttare l'operatore & per il set di intersezione a fare l'elenco di comprensione più breve e più efficiente:

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 sembra indicare che utilizzando un all_uniques insieme produce un aumento di velocità sostanziale per il processo generale di eliminazione dei duplicati. Spetta a circa un 3.5x speedup su Python 3 per insiemi di input fortemente duplicati, anche se solo su un 30% speedup per il processo generale di eliminazione dei duplicati su Python 2 a causa di un maggior numero di runtime dominato dalla costruzione del contatore. Questa accelerazione è abbastanza consistente, sebbene non altrettanto importante quanto evitare il runtime quadratico utilizzando element_counts in primo luogo. Se utilizzi Python 2 e questo codice è critico per la velocità, ti consigliamo di utilizzare un numero ordinario dict o uno anziché uno Counter.

Un altro modo sarebbe quello di costruire un insieme dupes da element_counts Utilizzando original - dupes anziché original & all_uniques nell'elenco comprensione, come suggested da Munk. Se questo funziona meglio o peggio dell'uso di un set all_uniques e & dipenderebbe dal grado di duplicazione nel tuo input e dalla versione di Python in uso, ma è doesn'tseem fare una grande differenza in entrambi i casi.

Answer 2

Sì, può essere fatto, ma non è certo divinatorio

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

Qualche riferimento sul set può essere trovato in the documentation. L'operatore * si chiama unpacking operator.

Answer 3

Un'altra soluzione con 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])] 

fattibile anche senza il disimballaggio e utilizzando chain.from_iterable invece.

Answer 4

Una soluzione leggermente diversa utilizzando Contatore e comprensione, per sfruttare l'operatore - per la differenza di impostazione.

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]