Ich musste einen bestimmten Prozess implementieren. Der Prozess ist wie folgt. "Entfernen Sie jedes Objekt in der Liste aus der Liste, wenn es dem neuen Objekt unterlegen ist." Was ist minderwertig? Unter der Annahme, dass das Objekt durch ein Taple dargestellt wird, ist das neue Objekt "n" und das ursprünglich in der Liste enthaltene Objekt ist "x".
[n[i] > x[i] for i in range(len(n))]
Angenommen, das Ergebnis von ist "[True, True, ..., True]" (alle True).
Es hängt jedoch vom Problem ab, ob jeder Index einen größeren oder einen kleineren Wert haben soll (dh das Programm muss sich damit befassen). Wenn beispielsweise die 1. Achse maximiert und die 2. Achse minimiert wird, sind die Bedingungen für die zu entfernenden Objekte wie folgt.
n[0] > x[0] and n[1] < x[1]
Im Folgenden werde ich diesen Prozess vorerst in Python schreiben und ihn dann Schritt für Schritt verbessern.
Deshalb ist es ein Programm, das die erläuterte Verarbeitung implementiert. Es wird angenommen, dass das Argument "Maximieren" übergibt, ob es auf jeder Achse maximiert oder minimiert ist (obwohl der Variablenname nicht gut genug ist).
filters.py
def filter00(l, n, maximize):
nl = []
for x in l:
remove = True
for i in range(len(x)):
if maximize[i]:
if n[i] > x[i]:
pass
else:
remove = False
else:
if n[i] < x[i]:
pass
else:
remove = False
if not remove:
nl.append(x)
return nl
Überprüfen Sie die Annahme, dass es gelöscht wird, und brechen Sie das Löschen ab, wenn es eine Achse gibt, für die x besser ist. Ich denke, es ist überflüssig, wenn if pass und else und remove False ist, aber ich denke, dass das Umdrehen der Bedingung oder das Nicht-Hinzufügen die Lesbarkeit verringert, also werde ich es so lassen, wie es ist (ich werde es trotzdem verbessern).
Der folgende Code für die Funktion filter00:
for i in range(len(x)):
if maximize[i]:
if n[i] > x[i]:
pass
else:
remove = False
else:
if n[i] < x[i]:
pass
else:
remove = False
maxim wird als Argument übergeben und ändert sich in der Schleife nicht. Ich halte es für einen zusätzlichen Prozess, jedes Mal einen bedingten Zweig zu erstellen. Überlegen wir uns also, ob wir "wenn maximiere [i]" herausholen können.
Die Methode besteht darin, "n [i]> x [i]" und "n [i] <x [i]" zu Lambda-Ausdrücken zu machen. Python verfügt über ein Operatormodul, das die dem Operator entsprechende Funktion ausführt. Schreiben wir sie also neu.
filters.py
import operator
def filter01(l, n, maximize):
cond = []
for m in maximize:
cond.append(operator.gt if m else operator.lt)
nl = []
for x in l:
remove = True
for i in range(len(x)):
if cond[i](n[i],x[i]):
pass
else:
remove = False
if not remove:
nl.append(x)
return nl
Übrigens habe ich den bedingten Zweig gelöscht, der sich je nach Schleife nicht ändert, aber ist er wirklich schneller? Lassen Sie uns richtig messen, nicht das Gefühl. Dieses Mal habe ich das folgende Messskript erstellt.
perf.py
import filters
import time
import random
import numpy as np
random.seed(123)
def perf(ll, n, m, f):
elapsed = []
for l in ll:
start = time.time()
f(l, n, m)
end = time.time()
elapsed.append(end - start)
print(f.__name__, np.average(elapsed))
LOOP = 100
SIZE = 1000
n = (70, 70)
m = (True, True)
ll = [[(random.randint(0, 99), random.randint(0, 99)) for _ in range(SIZE)] for _ in range(LOOP)]
perf(ll, n, m, filters.filter00)
perf(ll, n, m, filters.filter01)
Es besteht die Gefahr, dass Masakari fliegt, wenn Sie nur mit dem Durchschnittswert vergleichen. Bitte werfen Sie Masakari nicht, da das Ergebnis der vorläufigen Umfrage lautet, dass der Durchschnittswert in Ordnung ist (lacht).
Nun, Ausführungsergebnis
filter00 0.00383123636246 filter01 0.00437139987946
Unerwartet war es 5 Millisekunden zu spät. Es ist möglich, dass die Kosten für das Ändern des Vergleichs von einer Operation zu einem Funktionsaufruf die Kosten für das Entfernen des bedingten Zweigs überwogen, der sich mit der Schleife nicht ändert.
Ich wollte darüber reden, glücklich zu sein, weil der Code kürzer und schneller war, aber ich bin am Anfang gestolpert. Tatsächlich wurde diese Verbesserung durch Geschwindigkeitsprüfung nach dem Kürzen des Codes festgestellt. Da es jedoch möglich ist, den Code langsam zu halten, ist es besser, die Zip-Funktion zu verwenden, wenn mehrere Listen in einer Schleife verarbeitet werden. Ich fragte, aber ich versuchte zu sehen, wie es war.
filters.py
def filter02(l, n, maximize):
cond = []
for m in maximize:
cond.append(operator.gt if m else operator.lt)
nl = []
for x in l:
remove = True
for c, a, b in zip(cond, n, x):
if c(a, b):
pass
else:
remove = False
if not remove:
nl.append(x)
return nl
Messergebnis. Außerdem sind die Werte von filter00 und filter01 genau die gleichen wie zuvor, aber die Werte, die gemessen werden, wenn das Endergebnis des Verbesserungsprogramms erstellt wird, werden in kleinen Mengen angegeben. Nicht schlecht.
filter00 0.00383123636246 filter01 0.00437139987946 filter02 0.0029260468483
schnell. Es ist schneller als der ursprüngliche Code. Der Unterschied zwischen "filter01" und "filter02" besteht darin, ob sie sich mit Indizes auf "cond", "n", "x" beziehen oder empfangen, was die Zip-Funktion zurückgibt. Der tiefgestellte Zugriff wird als "getitem" -Methode bezeichnet, daher scheinen die Kosten für den Aufruf der Funktion weg zu sein. Während das gesagt wird, muss sogar die Zip-Funktion "getitem" aufrufen, aber ich bin daran interessiert, weil es auf der C-Ebene verarbeitet wird, aber ich werde den Code vorerst verbessern.
Inklusive Notation, die jeder liebt. Es ist zu ungeschickt, eine schlampige for-Schleife zu schreiben. Schreiben wir ordentlich mit der Einschlussnotation.
filters.py
def filter03(l, n, maximize):
cond = [operator.gt if m else operator.lt for m in maximize]
return [x for x in l if not all([c(a, b) for c, a, b in zip(cond, n, x)])]
Plötzlich zu viel! Ich werde einen Tsukkomi bekommen, also werde ich es richtig erklären. Oh, aber vorher. Erstens ist dieser Code in Bezug auf Zeilen sehr kurz, aber definitiv langsam. Wenn Sie also den schnellen Code kennen möchten, fahren Sie mit Verbesserung 5 fort.
Lassen Sie uns nun über filter03 sprechen. Diese Funktion verwendet die doppelte Einschlussnotation. Die innere Erklärung zuerst.
[c(a, b) for c, a, b in zip(cond, n, x)]
Dieser Teil ist fast der gleiche wie die in filter02 geschriebene innere Schleife. Meistens wurde in "filter02" eine bedingte Verzweigung durchgeführt und der Wert wurde in einer einzelnen Variablen "remove" festgelegt, aber in der obigen Einschlussnotation
[True, True]
Der Unterschied besteht darin, dass die Liste so zurückgegeben wird.
Hier entsteht das nervige Problem. Um zu entscheiden, ob Sie gehen oder nicht, müssen Sie es zu einem Skalar und nicht zu einer Liste machen. Verwenden Sie dazu die Funktion all. Die Funktion all ist eine Funktion, die True zurückgibt, wenn die Liste (oder iterierbar) alle True ist. Auf diese Weise können Sie die Verarbeitung dieser bedingten Verzweigung mit filter02 realisieren und im Fall von else remove auf False setzen. (Wenn Sie auf keiner Achse verlieren, ist mindestens eine der Listen falsch und das Ganze ist falsch.)
Deshalb kannte ich das Innere, diesmal ist es das Äußere.
[x for x in l if not all([c(a, b) for c, a, b in zip(cond, n, x)])]
Wie das funktioniert ist
Die äußere Einschlussnotation entspricht also dem Code, der "filter02" verarbeitet hat, um nicht abhängig vom Wert von "remove" (bestimmt durch die innere Schleife) anzuhängen.
Nun, es ist die lang erwartete Ausführungsgeschwindigkeit.
filter00 0.00383123636246 filter01 0.00437139987946 filter02 0.0029260468483 filter03 0.00512305736542
langsam. Es war viel langsamer als je zuvor. Tatsächlich scheint die Einschlussnotation aufgrund des Auftretens der Funktion & all, die funktional ausgeführt wird, einen Overhead zu haben.
Nun, es gibt bereits keinen Geschwindigkeitsvorteil, aber es gibt einen Vorteil in der Menge der Codebeschreibung, so dass ich den Code der Verbesserung 3 ein wenig weiter verbessern werde. Was mit filter03 schwer zu verstehen war, ist die doppelte Einschlussnotation, daher werde ich eine interne Funktion verwenden, um diesen Teil etwas kühler zu machen.
filters.py
def filter04(l, n, maximize):
cond = [operator.gt if m else operator.lt for m in maximize]
def dominated(x, n):
return all([c(a, b) for c, a, b in zip(cond, n, x)])
return [x for x in l if not dominated(x, n)]
Durch Ändern der Einschlussnotation (und aller Funktionen), die nach "wenn nicht" geschrieben wurde, in eine interne Funktion namens "dominiert" wurde es möglich, zu erklären, was Sie in einem Wort tun, und die Lesbarkeit hat sich verbessert.
Die Ausführungsgeschwindigkeit ist die langsamste, wie Sie sich vorstellen können.
filter00 0.00383123636246 filter01 0.00437139987946 filter02 0.0029260468483 filter03 0.00512305736542 filter04 0.00578190803528
Lassen Sie uns jetzt darauf zurückblicken.
Der Code basiert also auf diesen. Außerdem bedeutet "filter021", dass es basierend auf "filter02" geändert wurde.
filters.py
def filter021(l, n, maximize):
nl = []
for x in l:
remove = True
for a, b, m in zip(n, x, maximize):
remove = remove and (a > b if m else a < b)
if not remove:
nl.append(x)
return nl
Da die innere Schleife und der Operator nicht verwendet werden können, habe ich sie mithilfe des Operators und und des bedingten Operators kompakt gemacht.
Nun, Ausführungszeit
filter00 0.00383123636246 filter01 0.00437139987946 filter02 0.0029260468483 filter03 0.00512305736542 filter04 0.00578190803528 filter021 0.00255712985992
Am schnellsten: v:
Die Geschichte ist noch nicht vorbei. Können wir es nicht irgendwie schneller machen? Die Idee ist, den Code abhängig davon zu ändern, ob er häufig verwendet wird oder nicht (allgemein). Mit anderen Worten, selbst wenn Sie "N Variablen, Maximum und Minimum können gemischt werden" sagen, können Sie wie folgt schreiben, wenn Sie "2 Variablen, beide Achsen maximieren" in den meisten Verwendungen sagen.
filters.py
def filter02X(l, n, maximize):
if len(n) == 2 and maximize == (True, True):
return [x for x in l if not (n[0] > x[0] and n[1] > x[1])]
else:
return filter021(l, n, maximize)
Messergebnis
filter00 0.00383123636246 filter01 0.00437139987946 filter02 0.0029260468483 filter03 0.00512305736542 filter04 0.00578190803528 filter021 0.00255712985992 filter02X 0.000690214633942
Es ist eine außergewöhnliche Geschwindigkeit: v :: v: Im Fall von 2 Variablen und 3 Variablen in der Implementierung des Sprachverarbeitungssystems bedeutet dies, dass es mehr als das ist.
In diesem Artikel haben wir das solide Programm schrittweise verbessert. Die ursprüngliche Idee war, Code, der nicht Python-ähnlich ist (Code, den Leute, die andere Sprachen gelernt haben, beim Schreiben von Programmen in Python schreiben), Python-ähnlich zu machen, was ihn lesbarer und schneller macht und ihn glücklich macht. Ich wollte, aber als ich es tatsächlich maß, stellte ich fest, dass es nicht so war, also änderte ich die Geschichte ein wenig. Zusammenfassend gibt es die folgenden drei Punkte.
Es ist 3 Jahre her, seit der Artikel veröffentlicht wurde. Zu dieser Zeit war die Leistung von Numpy noch gering und ich dachte: "Die Geschwindigkeitsverbesserung, die ich in diesem Artikel geschrieben habe, jetzt frage ich mich, ob ich Numpy verwenden kann, um es noch schneller zu machen", aber ich habe es nicht berührt. Andererseits war ich verzweifelt, als ich das Programm, das die Quelle dieses Artikels war, zum ersten Mal seit einiger Zeit beibehalten hatte, verzweifelt, dass es zu langsam war, und benutzte Numpy, um es zu beschleunigen.
Es gibt etwas in filter021, das numpy ○ chi nicht vergeben kann.
Ja, es ist eine for-Anweisung.
Deshalb habe ich es gelöscht.
filters.py
def filter05(l, n, maximize):
cond = [np.greater if m else np.less for m in maximize]
npa = np.array(l)
check = np.empty(npa.shape, dtype=np.bool)
for i, c in enumerate(cond):
check[:, i] = c(n[i], npa[:, i])
#Elemente, die alle Achsen an n verlieren (bedingte Ausdrücke sind alle True), werden entfernt, andernfalls nicht entfernt
not_remove = (check.sum(axis=1) != len(n))
return [x for x, nr in zip(l, not_remove) if nr]
Ich kann es nicht löschen! Es gibt einen Grund, warum der obige Code eine Entschuldigung ist.
―― Da es für jede Achse unterschiedlich ist, ob sie maximiert oder minimiert ist (mit meiner Numpy-Potenz), kann sie nicht mit einem bedingten Ausdruck geschrieben werden.
[^ 1]: Es entspricht nicht den Spezifikationen, aber ich habe versucht, den Booleschen Index zu verwenden, aber es wurde nicht schneller.
Lassen Sie uns trotzdem die Zeit messen.
filter00 0.0037975716590881348 filter01 0.004087417125701904 filter02 0.003038032054901123 filter03 0.004926862716674804 filter04 0.005476489067077637 filter021 0.002838168144226074 filter02X 0.0006895852088928222 filter05 0.002588319778442383
Es ist ein Fehler. Der Grund, warum es nicht schneller wird, scheint der Aufwand für die Konvertierung von Listen in Numpy zu sein. Wenn len (l) >> len (n) ist, kann die for-Anweisung, die jede Achse vergleicht, ignoriert werden.
Wie oben erwähnt, kann das ursprüngliche Materialprogramm kein Numpy-Array als Eingabe annehmen, daher kann es nicht schneller gemacht werden, aber ich habe versucht zu sehen, wie schnell es wäre, wenn die Eingabe und Ausgabe ein Numpy-Array sein könnte.
filters.py
def filter06(a, n, maximize):
cond = [np.greater if m else np.less for m in maximize]
check = np.empty(a.shape, dtype=np.bool)
for i, c in enumerate(cond):
check[:, i] = c(n[i], a[:, i])
not_remove = (check.sum(axis=1) != len(n))
return a[not_remove]
Machen Sie es zu einem Numpy-Array, bevor Sie es auf die Messung anwenden.
perf.py
a = np.array(ll)
perf(a, n, m, filters.filter06)
Ergebnis. Immerhin ist es schnell, wenn es nur mit numpy abgeschlossen werden kann.
filter00 0.0037975716590881348 filter01 0.004087417125701904 filter02 0.003038032054901123 filter03 0.004926862716674804 filter04 0.005476489067077637 filter021 0.002838168144226074 filter02X 0.0006895852088928222 filter05 0.002588319778442383 filter06 0.00030982017517089844
Oder besser gesagt, die spezielle Version (filter02X) ist so schnell. Übrigens habe ich eine spezielle Version von filter05 und filter06 erstellt und gemessen, aber das Ergebnis war fast das gleiche (eher langsamer).
Ich fragte mich, ob es eine Möglichkeit gab, alles auf einmal zu tun, indem ich jede Achse von filter06 verglich, aber ich konnte den Vergleich nach Achse nicht eliminieren, aber ich fand eine Möglichkeit, die Summe nach for zu löschen.
filers.py
def filter061(a, n, maximize):
cond = [np.greater if m else np.less for m in maximize]
check = np.ones(a.shape[0], dtype=np.bool)
for i, c in enumerate(cond):
check = check & c(n[i], a[:, i])
not_remove = ~check
return a[not_remove]
Es wird ungefähr doppelt so schnell sein, wenn es gemessen wird. Ich habe versucht, die gleiche Verbesserung auf filter05 anzuwenden, aber der Konvertierungsaufwand war immer noch größer.
filter06 0.0003197813034057617 filter061 0.00017987966537475587
Wenn Sie den Vergleichsvorgang selbst invertieren und das letzte "~" entfernen, ist er 10 bis 20% schneller, aber die Lesbarkeit nimmt ab.
filters.py
def filter062(a, n, maximize):
cond = [np.less if m else np.greater for m in maximize]
not_remove = np.zeros(a.shape[0], dtype=np.bool)
for i, c in enumerate(cond):
not_remove = not_remove | c(n[i], a[:, i])
return a[not_remove]