Ich habe ein naives Test-Bett geschrieben, um die Leistung von drei Arten von faktorieller Implementierung zu messen: Schleifen-basiert, nicht-tail-rekursiv und tail-rekursiv.
Überraschenderweise war der schlechteste performant die Loop-Funktion («während» eine höhere Effizienz erwartet wurde, also habe ich beide zur Verfügung gestellt) fast zweimal als die Tail-rekursive Alternative.
ANTWORT: Korrektur der Schleifenimplementierung unter Vermeidung des * = Operators, der mit BigInt aufgrund seiner Interna am schlechtesten abschneidet «Schleifen» wurden am schnellsten wie erwartet
Ein weiteres «Woodoo» -Verhalten, das ich erlebt habe, war der StackOverflow Ausnahme, die nicht systematisch für die gleiche Eingabe in der Fall einer nicht-tail rekursiven Implementierung. Ich kann das umgehen StackOverlow durch progressiv Aufruf der Funktion mit größer und größer Werte ... Ich fühle mich verrückt :) Antwort: JVM muss beim Start konvergieren, dann ist das Verhalten kohärent und systematisch
Dies ist der Code:
%Vor%Was folgt, ist eine Ausgabe von der sbt-Konsole (vor der «while» -Implementierung) :
%Vor%Was folgt, ist eine Ausgabe von der sbt-Konsole (nach der Implementierung «while») :
%Vor%Was folgt ist eine Ausgabe von sbt console (nach «nach oben» Tail-Rekursion-Implementierung) die Welt kommt wieder gesund :
%Vor%Was folgt, ist eine Ausgabe von der sbt-Konsole, nachdem die BigInt-Multiplikation in «Schleifen» korrigiert wurde: Die Welt ist völlig gesund. :
%Vor%BigInt Overhead und eine dumme Implementierung von mir maskiert das erwartete Verhalten.
Danke Leute
PS .: Am Ende sollte ich diesen Beitrag zu "Eine neue Lektion über BigInts" umbenennen.
For-Loops sind eigentlich keine Loops. sie sind für Verständnisse auf einer Reihe. Wenn Sie eine Schleife wollen, müssen Sie while verwenden. (Eigentlich denke ich, dass die BigInt -Multiplikation hier schwer genug ist, also sollte es nichts ausmachen. Aber Sie werden bemerken, wenn Sie Int s multiplizieren.)
Außerdem haben Sie sich selbst verwirrt, indem Sie BigInt verwenden. Je größer Ihr BigInt ist, desto langsamer ist Ihre Multiplikation. Also zählt deine Non-Tail-Schleife hoch , während deine Tail-Rekursionsschleife runter ist, was bedeutet, dass letztere mehr große Zahlen zu multiplizieren hat.
Wenn Sie diese beiden Probleme beheben, werden Sie feststellen, dass die Vernunft wiederhergestellt ist: Schleifen und Tail-Rekursion haben die gleiche Geschwindigkeit, wobei sowohl reguläre Rekursion als auch for langsamer sind. (Die reguläre Rekursion ist möglicherweise nicht langsamer, wenn die JVM-Optimierung dies äquivalent macht)
(Die Stapelüberlaufkorrektur ist wahrscheinlich auch darauf zurückzuführen, dass die JVM inline beginnt und entweder den Aufruf selbst rekursiv ausführt oder die Schleife so weit aufrollt, dass Sie nicht mehr überlaufen.)
Schließlich erhalten Sie schlechte Ergebnisse mit for und while, weil Sie auf der rechten Seite statt der linken mit der kleinen Zahl multiplizieren. Es stellt sich heraus, dass der BigInt von Java sich mit der kleineren Zahl auf der linken Seite schneller multipliziert.
Scala statische Methoden für factorial(n) (codiert mit scala 2.12.x, java-8):
Spezifikationen:
%Vor%Benchmarks:
%Vor%Benchmark-Ergebnisse (Schleife ist viel schneller):
%Vor%Tags und Links scala performance stack-overflow tail-recursion