Auf der Suche nach einer wirklich schnellen Implementierung der Fakultätsfunktion in JavaScript. Irgendwelche Vorschläge?
94
Auf der Suche nach einer wirklich schnellen Implementierung der Fakultätsfunktion in JavaScript. Irgendwelche Vorschläge?
Antworten:
Sie können nach (1 ... 100) suchen! auf WolframAlpha , um die faktorielle Sequenz vorab zu berechnen.
Die ersten 100 Zahlen sind:
Wenn Sie die Werte dennoch selbst berechnen möchten, können Sie Memoization verwenden :
Bearbeiten: 21.08.2014
Lösung 2
Ich dachte, es wäre nützlich, ein funktionierendes Beispiel für eine faule iterative Fakultätsfunktion hinzuzufügen , die große Zahlen verwendet , um ein genaues Ergebnis mit Memoisierung und Cache als Vergleich zu erhalten
Ich gehe davon aus, dass Sie eine Art Verschluss verwenden würden , um die Sichtbarkeit von Variablennamen einzuschränken.
Ref : BigNumber Sandbox : JsFiddle
quelle
function factorial (n) { for (var i = f.length; i <= n; i++) f.push(f[i - 1].multiply(i.toString())); return f[n]; }
auch meine Antwort zu sehen , bei der die neuere integrierte VersionBigInt
anstelle einer Bibliothek eines Drittanbieters verwendet wird.Sie sollten eine Schleife verwenden.
Hier sind zwei Versionen, die durch 10.000-malige Berechnung der Fakultät 100 verglichen werden.
Rekursiv
Iterativ
Live unter: http://jsfiddle.net/xMpTv/
Meine Ergebnisse zeigen:
- Rekursiv ~ 150 Millisekunden
- Iterativ ~ 5 Millisekunden ..
quelle
rval = rval * i;
könnten Sie schreibenrval *= i;
Ich denke immer noch, dass Margus 'Antwort die beste ist. Wenn Sie jedoch auch die Fakultäten von Zahlen im Bereich von 0 bis 1 (dh die Gammafunktion) berechnen möchten, können Sie diesen Ansatz nicht verwenden, da die Nachschlagetabelle unendliche Werte enthalten muss.
Sie können jedoch die Werte der Fakultäten approximieren, und dies ist ziemlich schnell, schneller als sich selbst rekursiv aufzurufen oder zumindest zu schleifen (insbesondere, wenn die Werte größer werden).
Eine gute Näherungsmethode ist die von Lanczos
Hier ist eine Implementierung in JavaScript (portiert von einem Taschenrechner, den ich vor Monaten geschrieben habe):
Sie können jetzt coole Sachen wie
factorial(0.41)
usw. machen, aber die Genauigkeit kann ein wenig abweichen, schließlich ist es eine Annäherung an das Ergebnis.quelle
var d3d4 = Math.exp((z + 0.5) * Math.log(z + 5.5) - z - 5.5); return d1 * d2 * d3d4;
. Auf diese Weise können Sie Fakultäten bis zu 169 berechnen! statt derzeit nur 140!. Dies ist ziemlich nahe an der maximal darstellbaren Fakultät unter Verwendung desNumber
Datentyps, der 170! Ist.Die Nachschlagetabelle ist der naheliegende Weg, wenn Sie mit natürlichen Zahlen arbeiten. Um eine Fakultät in Echtzeit zu berechnen, können Sie sie mit einem Cache beschleunigen und die zuvor berechneten Zahlen speichern. Etwas wie:
Sie können einige Werte vorberechnen, um sie noch schneller zu machen.
quelle
Hier ist meine Lösung:
Es ist der einfachste Weg (weniger Zeichen / Zeilen), den ich gefunden habe, nur eine Funktion mit einer Codezeile.
Bearbeiten:
Wenn Sie wirklich einige Zeichen speichern möchten, können Sie eine Pfeilfunktion (21 Byte) verwenden :
quelle
f=n=>n?f(n-1)*n:1
...Nur eine Zeile mit ES6
Code-Snippet anzeigen
quelle
factorial = n => n <= 1 ? 1 : factorial(n - 1) * n
kurze und einfache rekursive Funktion (Sie könnten dies auch mit einer Schleife tun, aber ich denke nicht, dass dies einen Unterschied in der Leistung bewirken würde):
Für ein sehr großes n könnten Sie die Stirlings-Näherung verwenden - aber das gibt Ihnen nur einen ungefähren Wert.
EDIT: Ein Kommentar, warum ich dafür eine Abwertung bekomme, wäre schön gewesen ...
EDIT2: Dies wäre die Soulution mit einer Schleife (was die bessere Wahl wäre):
Ich denke , die beste Lösung , um die im Cache gespeicherten Werte zu verwenden wäre, als Margus und die Verwendung erwähnte Stirlings Näherung für größere Werte (vorausgesetzt man muss wirklich schnell und muß nicht sein , dass genau auf so großen Zahlen).
quelle
Siehe, der Memoizer, der jede einzelne Argumentfunktion übernimmt und sie auswendig lernt. Es stellt sich heraus, dass es geringfügig schneller ist als die Lösung von @ xPheRe , einschließlich der Begrenzung der Größe des Caches und der damit verbundenen Überprüfung, da ich Kurzschlüsse usw. verwende.
Ungefähr 25x schneller auf meinem Computer in Chrome als in der rekursiven Version und 10% schneller als bei xPheRe.
quelle
Ich bin auf diesen Beitrag gestoßen. Inspiriert von allen Beiträgen hier habe ich meine eigene Version entwickelt, die zwei Funktionen enthält, die ich zuvor noch nicht besprochen habe: 1) Eine Überprüfung, um sicherzustellen, dass das Argument eine nicht negative Ganzzahl ist. 2) Eine Einheit aus dem Cache erstellen und die Funktion, es zu einem eigenständigen Codebit zu machen. Zum Spaß habe ich versucht, es so kompakt wie möglich zu machen. Einige mögen das elegant finden, andere mögen es für schrecklich dunkel halten. Wie auch immer, hier ist es:
Sie können den Cache entweder vorab füllen oder ihn im Laufe der Anrufe füllen lassen. Aber das Anfangselement (für Tatsache (0) muss vorhanden sein, sonst wird es brechen.
Genießen :)
quelle
Schnellste Fakultätsfunktion
Ich denke, dass diese schleifenbasierte Version die schnellste Fakultätsfunktion sein könnte.
Und hier ist meine Argumentation:
for
Schleifen undwhile
Schleifen eine ähnliche Leistung haben,for
sieht eine Schleife ohne Initialisierungsausdruck und Endausdruck seltsam aus. wahrscheinlich besser zu schreibenfor(; n > 0;)
alswhile(n > 0)
n
undr
verwendet werden, so in der Theorie weniger Parameter bedeuten weniger Zeit damit verbracht das Zuweisen von Speichern
Null ist. Ich habe Theorien gehört, dass Computer Binärzahlen (0 und 1) besser prüfen können als andere Ganzzahlenquelle
Mit ES6 ist das sehr einfach
const factorial = n => n ? (n * factorial(n-1)) : 1;
Sehen Sie ein Beispiel hier
quelle
Hier ist eine Lösung:
quelle
Mit ES6 können Sie es schnell und kurz erreichen:
quelle
Der Code zur Berechnung der Fakultät hängt von Ihren Anforderungen ab.
In Bezug auf die Punkte 1 und 4 ist es oft nützlicher, eine Funktion zum direkten Auswerten des Protokolls der Fakultät zu haben, als eine Funktion zum Auswerten der Fakultät selbst.
Hier ist ein Blog-Beitrag , in dem diese Probleme behandelt werden. Hier ist ein C # -Code für die Berechnung der Protokollfaktor , der für die Portierung auf JavaScript trivial wäre. Abhängig von Ihren Antworten auf die obigen Fragen ist es möglicherweise nicht das Beste für Ihre Bedürfnisse.
quelle
Dies ist eine kompakte schleifenbasierte Version
Oder Sie überschreiben das Math-Objekt (rekursive Version):
Oder verbinden Sie beide Ansätze ...
quelle
Unter Ausnutzung der Tatsache
Number.MAX_VALUE < 171!
können wir einfach eine vollständige Nachschlagetabelle verwenden, die aus nur 171 kompakten Array-Elementen besteht, die weniger als 1,4 Kilobyte Speicher belegen.Eine schnelle Suchfunktion mit Laufzeitkomplexität O (1) und minimalem Array-Zugriffsaufwand würde dann wie folgt aussehen:
Dies ist so präzise und schnell, wie es mit dem
Number
Datentyp möglich ist. Das Berechnen der Nachschlagetabelle in Javascript verringert - wie einige andere Antworten vermuten lassen - die Genauigkeit, wennn! > Number.MAX_SAFE_INTEGER
.Durch das Komprimieren der Laufzeittabelle über gzip wird die Größe der Festplatte von etwa 3,6 auf 1,8 Kilobyte reduziert.
quelle
Einzeilige Antwort:
quelle
Iterative Fakultät mit
BigInt
aus SicherheitsgründenDies ist ein funktionierendes Beispiel
BigInt
, da viele Antworten hierNumber
fast sofort der sicheren Grenze von (MDN) entgehen . Es ist nicht das schnellste, aber es ist einfach und somit klarer für die Anpassung anderer Optimierungen (wie ein Cache der ersten 100 Zahlen).Beispiel Verwendung
n
am Ende eines numerischen Literals wie1303n
zeigt an, dass es sich um einenBigInt
Typ handelt.BigInt
mit ,Number
wenn Sie sie ausdrücklich zwingen, und dass damit ein Verlust an Genauigkeit führen könnte.quelle
Kann mit ES6-Funktionen Code in EINE Zeile und ohne Rekursion schreiben :
Code-Snippet anzeigen
quelle
Der Vollständigkeit halber ist hier eine rekursive Version, die eine Tail-Call-Optimierung ermöglichen würde. Ich bin mir nicht sicher, ob Tail-Call-Optimierungen in JavaScript durchgeführt werden.
Um es zu nennen:
quelle
Dies ist eine iterative Lösung, die weniger Stapelspeicherplatz benötigt und zuvor berechnete Werte auf selbstmerkende Weise speichert:
Beachten Sie auch, dass ich dies dem Math-Objekt hinzufüge, das ein Objektliteral ist, sodass es keinen Prototyp gibt. Binden Sie diese einfach direkt an die Funktion.
quelle
Math.factorial(100); Math.factorial(500);
berechnet beispielsweise die 1..100-Multiplikation zweimal.Ich glaube, das Folgende ist der nachhaltigste und effizienteste Code aus den obigen Kommentaren. Sie können dies in Ihrer globalen Anwendungsarchitektur verwenden ... und sich keine Sorgen machen, es in mehrere Namespaces zu schreiben (da es sich um eine Aufgabe handelt, die wahrscheinlich nicht viel erweitert werden muss). Ich habe 2 Methodennamen (je nach Präferenz) eingefügt, aber beide können verwendet werden, da sie nur Referenzen sind.
quelle
n * (n-1) * (n-2) * ... * 1
statt umgekehrt beginnen, verlieren Sie bis zu 4 Stellen Genauigkeit für n >> 20.Dadurch werden die ersten 100 Werte im laufenden Betrieb zwischengespeichert, und es wird keine externe Variable in den Bereich für den Cache eingefügt. Dabei werden die Werte als Eigenschaften des Funktionsobjekts selbst gespeichert. Wenn Sie also wissen, dass
factorial(n)
sie bereits berechnet wurden, können Sie dies bezeichnen Sie es einfach alsfactorial[n]
, was etwas effizienter ist. Das Ausführen dieser ersten 100 Werte dauert in modernen Browsern weniger als eine Millisekunde.quelle
21! > Number.MAX_SAFE_INTEGER
, dass es daher nicht sicher als 64-Bit-Float dargestellt werden kann.Hier ist eine Implementierung, die sowohl positive als auch negative Fakultäten berechnet. Es ist schnell und einfach.
quelle
Hier ist eine, die ich selbst gemacht habe. Verwenden Sie keine Zahlen über 170 oder unter 2.
quelle
i
und führt viel zu vieleNumber
Konvertierungen durch und gibt falsche Ergebnisse für 0! (Wie Sie sagten, aber warum?).Hier ist mein Code
quelle
factorial(0)
. Wenn Sie Ihre Multiplikation mit n * (n-1) * (n-2) * ... * 1 anstatt umgekehrt beginnen, verlieren Sie bis zu 4 Stellen Genauigkeit für n >> 20. @prime:170! > Number.MAX_VALUE
und ist am besten vertreten mitInfinity
.Die zwischengespeicherte Schleife sollte am schnellsten sein (zumindest bei mehrmaligem Aufruf).
quelle
Nachdem ich die Eingaben anderer Mitglieder überprüft hatte (mit Ausnahme der Protokollempfehlungen, obwohl ich diese möglicherweise später implementieren werde), habe ich ein Skript zusammengestellt, das ziemlich einfach ist. Ich begann mit einem einfachen ungebildeten JavaScript-OOP-Beispiel und baute eine kleine Klasse für den Umgang mit Fakultäten auf. Ich habe dann meine Version der oben vorgeschlagenen Memoization implementiert. Ich habe auch die Kurzfaktor-Faktorisierung implementiert, jedoch eine kleine Fehleranpassung vorgenommen. Ich habe "n <2" in "n <3" geändert. "n <2" würde immer noch n = 2 verarbeiten, was eine Verschwendung wäre, da Sie für 2 * 1 = 2 iterieren würden; Dies ist meiner Meinung nach eine Verschwendung. Ich habe es in "n <3" geändert; denn wenn n 1 oder 2 ist, gibt es einfach n zurück, wenn es 3 oder mehr ist, wird es normal ausgewertet. Da die Regeln gelten, habe ich meine Funktionen natürlich in absteigender Reihenfolge der angenommenen Ausführung angeordnet. Ich habe die Option bool (true | false) hinzugefügt, um einen schnellen Wechsel zwischen gespeicherter und normaler Ausführung zu ermöglichen (Sie wissen nur nie, wann Sie auf Ihrer Seite wechseln möchten, ohne den "Stil" ändern zu müssen) Die Variable für gespeicherte Fakultäten wird mit den 3 Startpositionen festgelegt, wobei 4 Zeichen verwendet werden und verschwenderische Berechnungen minimiert werden. Alles nach der dritten Iteration, mit der Sie zweistellige Mathematik plus verarbeiten. Ich denke, wenn Sie ein Stickler genug wären, würden Sie auf einer Fakultätstabelle (wie implementiert) laufen. Nehmen Sie 4 Zeichen und minimieren Sie verschwenderische Berechnungen. Alles nach der dritten Iteration, mit der Sie zweistellige Mathematik plus verarbeiten. Ich denke, wenn Sie ein Stickler genug wären, würden Sie auf einer Fakultätstabelle (wie implementiert) laufen. Nehmen Sie 4 Zeichen und minimieren Sie verschwenderische Berechnungen. Alles nach der dritten Iteration, mit der Sie zweistellige Mathematik plus verarbeiten. Ich denke, wenn Sie ein Stickler genug wären, würden Sie auf einer Fakultätstabelle (wie implementiert) laufen.
Was habe ich danach geplant? lokaler & | Sitzungsspeicher, um einen fallweisen Cache der erforderlichen Iterationen zu ermöglichen, wobei im Wesentlichen das oben erwähnte "Tabellen" -Problem behandelt wird. Dies würde auch massiv datenbank- und serverseitigen Speicherplatz sparen. Wenn Sie sich jedoch für localStorage entscheiden, würden Sie im Wesentlichen Speicherplatz auf dem Computer Ihres Benutzers beanspruchen, um einfach eine Liste von Zahlen zu speichern und den Bildschirm schneller aussehen zu lassen. Über einen langen Zeitraum mit einem immensen Bedarf wäre dies jedoch langsam. Ich denke, sessionStorage (Löschen nach Tab-Blättern) wäre eine viel bessere Route. Kombinieren Sie dies möglicherweise mit einem selbstausgleichenden Server / lokal abhängigen Cache? Benutzer A benötigt X Iterationen. Benutzer B benötigt Y-Iterationen. X + Y / 2 = Erforderlich lokal zwischengespeicherter Betrag. Dann erkennen Sie einfach die Benchmarks für Ladezeit und Ausführungszeit und spielen mit ihnen, bis sie sich an die Optimierung für die Site selbst anpassen. Vielen Dank!
Edit 3:
quelle
undefined
für 0!. ES6 ermöglicht das ErsetzenisNumeric
durchNumber.isInteger
. Zeilen wiefactorials[0][factorials[1]]=factorials[0][factorial_index]*(factorials[1]+1);
sind völlig unlesbar.Hier ist eine, die neuere Javascript-Funktionen zum Füllen , Zuordnen , Reduzieren und Konstruieren (und zur Fettpfeilsyntax) verwendet:
Bearbeiten: aktualisiert, um n === 0 zu behandeln
quelle
n === 0
.Math.factorial = n => Array.from({ length: n }).reduce((product, _, i) => product * (i + 1), 1)
quelle