Ich bemerkte einen seltsamen Performance-Hit von einem kleinen Refactoring, das eine Schleife durch einen Aufruf des eingebauten max innerhalb einer rekursiven Funktion ersetzte.
Hier ist die einfachste Reproduktion, die ich produzieren konnte:
%Vor% Sowohl f1 als auch f2 berechnen faktoriell mit der Standard Rekursion, aber mit einer unnötigen Maximierung (nur damit ich max in einer Rekursion verwenden kann, während die Rekursion einfach bleibt):
Es ist ohne Memo-Implementierung implementiert, daher gibt es eine exponentielle Anzahl von Anrufen.
Die Implementierung mit max(iterable) ist mehr als doppelt so langsam wie die mit der Schleife.
Seltsamerweise zeigte ein direkter Vergleich von (Bearbeiten: egal, siehe @TimPeters Antwort). Wenn ich max vs loop nicht den Effekt max(a, b) anstelle von max(iterable) verwende, verschwindet die Performance-Abweichung.
Dies ist wirklich unfair für die max -Funktion aufgrund des Generatorausdrucks, den du fütterst.
Für jeden Aufruf von f2 muss ein neuer Abschluss für n erstellt werden, eine neue Funktion muss erstellt werden (so werden Generatorausdrücke und Listenausdrücke seit Python 3 implementiert, siehe < a href="https://www.python.org/dev/peps/pep-0289/#the-details"> "Die Details" von PEP 289 ), die das Code-Objekt, das die gene- exp. Dann wird diese Funktion, die iterativ andere Funktionen aufruft, erneut aufgerufen.
Ein kleiner Ausschnitt des betreffenden Byte-Codes:
%Vor% Sie sehen natürlich keine Anweisungen wie diese in f1 , da sie nur Anrufe tätigen.
Wenn Sie dann Ihre max Funktion, f2 , eine signifikante Anzahl von Malen aufrufen, wie Sie es tun, wenn Sie die Fakultät von 30 rekursiv berechnen, dann ist der Overhead nur stapelt sich .
Eine Listenverfassungsversion der Funktionssache leidet ziemlich genau unter dem gleichen Problem. Es ist ein bisschen schneller, weil List Comprehensions schneller als Generator-Ausdrücke sind.
Wenn ich
max(a, b)anstelle vonmax(iterable)verwende, verschwindet der Leistungsunterschied.
Genau, es werden in diesem Fall keine Funktionen für jeden Anruf erstellt, so dass Sie nicht sehen, dass sich dieser Stapel anhäuft. Sie liefern hier einfach die Argumente.
Dies als "eine Antwort" bekannt geben, weil eine nützliche Formatierung in Kommentaren unmöglich ist:
%Vor%Was zeigt, dass die Rekursion ein Ablenkungsmanöver ist. Es ist allgemein wahr, wie diese Ergebnisse zeigen, dass ein Genxp langsamer als ein Listcomp ist, was wiederum langsamer ist als die Verwendung von keinem. Da Ihr Code mehr als nur max macht, sind die Timing-Unterschiede nicht so extrem - aber da wenig mehr als nur ein Maximum ist, ist die Geschwindigkeit des max Teil ist dennoch hoch signifikant.
Tags und Links python performance python-3.x python-internals