Überblick

Wenn eine festgelegte Operation ausgeführt wird, kann die Ausführungsgeschwindigkeit verbessert werden, indem die Anzahl der Elemente des erhaltenen Ergebnisses verringert wird. Da das Operationsergebnis in einem neuen festgelegten Objekt zurückgegeben wird, dauert es einige Zeit, das Objekt zu erstellen, wenn die Anzahl der Elemente groß ist.

Hintergrund

Wenn ich in ABC157 D Friend Suggestions "len (XYZ)" einstelle, um die Anzahl der Elemente in einem bestimmten Satz zu berechnen, wurde dies zu TLE. AC wurde mit len (X) -len (X & (Y | Z)) durchgeführt. Ich habe versucht zu überprüfen, warum die Geschwindigkeit unterschiedlich ist.

|X|Wann ist groß

Unter der Voraussetzung des Problems|X|,|Y|,|Z| \leq 10^5Aber diesmal bin ich tatsächlich darauf gestoßen|X| \gg |Y|,|Z|Lassen Sie uns den Zustand von messen.

from timeit import timeit

xyz = 'X=set(range(10**5)); Y=set(range(10)); Z=set(range(5,15))' 

timeit('len(X-Y-Z)', setup=xyz, number=100)
# 0.3884289239649661

timeit('len(X)-len(X&(Y|Z))', setup=xyz, number=100)
# 0.0001103340182453394

Obwohl die Ergebnisse gleich sind, gibt es einen 3520-fachen Unterschied in der Ausführungszeit.

Wenn der Inhalt von X, Y, Z gleich ist

Als nächstes sei X, Y, Z das gleiche Element von $ 10 ^ 5 $.

from timeit import timeit

xyz = 'X=set(range(10**5)); Y=set(range(10**5)); Z=set(range(10**5))'

timeit('len(X-Y-Z)', setup=xyz, number=100)
# 0.28364974400028586

timeit('len(X)-len(X&(Y|Z))', setup=xyz, number=100)
# 1.1718004010035656

Nächstes Mallen(X)-len(X&(Y|Z))War langsamer.X&(Y|Z)Entspricht der ursprünglichen Menge, und es wird davon ausgegangen, dass die Anzahl der Elemente im Ergebnis zugenommen hat. Andererseits wurde "len (X-Y-Z)" auf etwa 1/3 verkürzt, wahrscheinlich weil im Stadium von "X-Y" ein leerer Satz erhalten wurde.

Differenzsatz gegenüber Produktsatz

Vereinfachen Sie das Problem und vergleichen Sie nur die Unterschiede und Produktvorgänge. Die andere Seite der Berechnung ist eine leere Menge, und die linke und rechte Seite werden ausgetauscht.

from timeit import timeit

xy = 'X=set(range(10**5)); Y=set()'

timeit('X-Y', setup=xy, number=100)
# 0.16930873499950394
timeit('Y-X', setup=xy, number=100)
# 1.7047044821083546e-05

timeit('X&Y', setup=xy, number=100)
# 1.0746996849775314e-05
timeit('Y&X', setup=xy, number=100)
# 1.502997474744916e-05

Selbst in der Differenzmenge ist es schnell, wenn die Anzahl der Elemente im Ergebnis gering ist. Anscheinend ist der Geschwindigkeitsunterschied nicht der Inhalt der Berechnung.

Generierung des Sets

Siehe Python-Dokumentation set.difference

Gibt eine neue Menge mit Elementen zurück, die in der Menge enthalten sind und nicht in allen anderen enthalten sind.

ein. Messen wir daher die Generierungszeit einer Menge mit einer großen Anzahl von Elementen.

from timeit import timeit

timeit('set(X)', setup='X=set(range(10**5))', number=100)
# 0.16229172004386783

Wenn die Anzahl der Elemente im Ergebnis groß war, dauerte es schließlich nur lange, bis die zurückgegebene Menge generiert wurde.