modo rapido per estendere un insieme se sappiamo elementi sono unici

Question

sto eseguendo più iterazioni del tipo:

masterSet=masterSet.union(setA) 

Come il set cresce la lunghezza del tempo necessario per eseguire queste operazioni è in crescita (come si farebbe aspetto, immagino).

Mi aspetto che il tempo venga occupato controllando se ciascun elemento di setA è già in masterSet?

La mia domanda è che se SO che masterSet non contiene già alcun elemento in setA posso farlo più rapidamente?

[UPDATE]

Dato che la questione è ancora attirando vista ho pensato di chiarire alcune delle cose dai commenti e le risposte qui sotto:

Quando l'iterazione se c'erano molte iterazioni dove sono sapevasetA sarebbe distinto da masterSet a causa di come è stato costruito (senza dover elaborare alcun controllo) ma poche iterazioni avevo bisogno del controllo di unicità.

mi chiedevo se ci fosse un modo per 'raccontare' la procedura masterSet.union() di non perdere tempo con la uniquness controllare questa volta come so che questo è distinto da masterSet basta aggiungere questi elementi di fiducia rapidamente l'affermazione del programmatore erano sicuramente distict . Perhpas chiama diverse ".unionWithDistinctSet()" procedura o qualcosa del genere.

Penso che le risposte abbiano suggerito che questo non è possibile (e che le operazioni effettivamente impostate dovrebbero essere abbastanza veloci lo stesso) ma usare masterSet.update(setA) invece di unione come il suo ancora un po 'più veloce.

Ho accettato la risposta più chiara lungo queste linee, risolto il problema che stavo avendo in quel momento e sono andato avanti con la mia vita, ma mi piacerebbe ancora sentire se il mio ipotizzato .unionWithDistinctSet() potesse mai esistere?

Answer 1

È possibile utilizzare set.update per aggiornare il set principale in posizione. Ciò consente di risparmiare l'assegnazione di un nuovo set di tutto il tempo e quindi dovrebbe essere un po 'più veloce di set.union ...

>>> s = set(range(3)) 
>>> s.update(range(4)) 
>>> s 
set([0, 1, 2, 3]) 

Naturalmente, se si sta facendo questo in un ciclo:

masterSet = set() 
for setA in iterable: 
    masterSet = masterSet.union(setA) 

Potrebbero un miglioramento delle performance facendo qualcosa di simile:

masterSet = set().union(*iterable) 

---

in ultima analisi, il controllo di appartenenza di un insieme è O (1) (in il caso medio), quindi testare se l'elemento è già contenuto nel set non è davvero un grande successo in termini di prestazioni.

Answer 2

Come fa notare mgilson, è possibile utilizzare update per aggiornare un set sul posto da un altro set. In realtà funziona un po 'più veloce:

def union(): 
    i = set(range(10000)) 
    j = set(range(5000, 15000)) 
    return i.union(j) 

def update(): 
    i = set(range(10000)) 
    j = set(range(5000, 15000)) 
    i.update(j) 
    return i 

timeit.Timer(union).timeit(10000) # 10.351907968521118 
timeit.Timer(update).timeit(10000) # 8.83384895324707 

Answer 3

Se sai che i tuoi elementi sono unici, un set non è necessariamente la struttura migliore.

Un elenco semplice è molto più veloce da estendere.

masterList = list(masterSet) 
masterList.extend(setA) 

Answer 4

Di sicuro, rinunciando questo controllo potrebbe essere un grande risparmio quando il metodo __eq__(..) è molto costoso. Nell'implementazione CPython, __eq__(..) viene chiamato con ogni elemento già presente nel set che esegue lo hash sullo stesso numero. (Riferimento: source code for set.)

Tuttavia, non ci sarà mai questa funzionalità tra un milione di anni, perché apre un altro modo per violare l'integrità di un set. Il problema associato a questo supera di gran lunga il guadagno di prestazioni (generalmente trascurabile). Mentre se questo è determinato come un collo di bottiglia delle prestazioni, non è difficile scrivere un'estensione C++ e usare il suo STL <set>, che dovrebbe essere più veloce di uno o più ordini di grandezza.