Schnell Weg, um einen Satz zu verlängern, wenn wir wissen, dass Elemente sind einzigartig

Question

ich mehrere Iterationen des Typs bin ausführen:

masterSet=masterSet.union(setA) 

Als Set wächst die Länge der Zeit, diese Vorgänge auszuführen genommen wächst (als wären sie eine erwarte, denke ich).

Ich erwarte, dass die Zeit in Anspruch genommen wird zu überprüfen, ob jedes Element von SetA bereits in MasterSet ist?

Meine Frage ist, dass, wenn ich weiß, dass MasterSet noch keine der Elemente in SetA enthält, kann ich das schneller tun?

[UPDATE]

Da diese Frage nach wie vor zieht Ansichten, die ich dachte, dass ich aus den Kommentaren und Antworten unten, um ein paar der Dinge aufklären würde:

Wenn Iterieren obwohl es viele Iterationen waren, wo ich wusstesetA würde von masterSet wegen seiner wie es konstruiert wurde (ohne zu haben, irgendwelche Prüfungen zu überprüfen) getrennt, aber ein paar Iterationen brauchte ich die Eindeutigkeitsprüfung.

Ich fragte mich, ob es einen Weg zu ‚sagen‘ das masterSet.union() Verfahren nicht mit der uniquness überprüfen Sie diese Zeit um zu stören, da ich weiß, dass dies eine von masterSet unterscheidet gerade diese Elemente fügen schnell des Programmierers Behauptung zu vertrauen sie auf jeden Fall distict waren . Perhpas durch Aufruf einer anderen ".unionWithDistinctSet()" Prozedur oder etwas.

Ich denke, die Antworten haben darauf hingewiesen, dass dies nicht möglich ist (und das wirklich Operationen sollten schnell genug sein sowieso), aber masterSet.update(setA) statt Union als seine etwas schneller noch zu verwenden.

Ich habe die klarste Antwort in diese Richtung akzeptiert, das Problem, das ich zu der Zeit hatte, gelöst und mit meinem Leben weitergemacht, aber würde immer noch gerne hören, ob meine Hypothese .unionWithDistinctSet() jemals existieren könnte?

Answer 1

Sie können set.update verwenden, um Ihren Mastersatz zu aktualisieren. Das spart eine neue Reihe die ganze Zeit Zuteilung, so dass es ein wenig schneller als set.union sein sollte ...

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

Natürlich, wenn Sie diese in einer Schleife tun:

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

Das könnte dir eine Leistungssteigerung erhalten, indem etwas wie tun:

masterSet = set().union(*iterable) 

---

Letztlich Mitgliedschaft Testen eines Satzes ist O (1) (in der durchschnittliche Fall), also testen, ob das Element bereits in der Menge enthalten ist, ist nicht wirklich ein großer Leistungshit.

Answer 2

Wie mgilson darauf hinweist, können Sie update verwenden, um ein Set direkt von einem anderen Set zu aktualisieren. Das geht etwas schneller:

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

Wenn Sie wissen, dass Ihre Elemente einzigartig sind, ist ein Set nicht unbedingt die beste Struktur.

Eine einfache Liste ist viel schneller zu erweitern.

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

Answer 4

Natürlich könnte diese Überprüfung Verzicht auf eine große Einsparung, wenn die __eq__(..) Methode sehr teuer ist. In der CPython-Implementierung wird __eq__(..) mit jedem Element aufgerufen, das bereits in der Menge ist, die auf die gleiche Zahl hasht. (Referenz: source code for set.)

Jedoch wird es diese Funktionalität in einer Million Jahren nie geben, weil es einen anderen Weg öffnet, die Integrität eines Satzes zu verletzen. Die damit verbundenen Probleme überwiegen den (typischerweise vernachlässigbaren) Leistungszuwachs. Wenn dies als ein Leistungsengpass festgestellt wird, ist es nicht schwer, eine C++ - Erweiterung zu schreiben und seine STL <set> zu verwenden, die um eine oder mehrere Größenordnungen schneller sein sollte.