Leistung: Rekursion vs. Iteration in Javascript

24

Ich habe kürzlich einige Artikel (z. B. http://dailyjs.com/2012/09/14/functional-programming/ ) über die funktionalen Aspekte von Javascript und die Beziehung zwischen Schema und Javascript gelesen (letzteres wurde durch das erste beeinflusst, das ist eine funktionale Sprache, während die OO-Aspekte von Self (einer auf Prototyping basierenden Sprache) geerbt werden.

Meine Frage ist jedoch spezifischer: Ich habe mich gefragt, ob es Metriken zur Leistung von Rekursion vs. Iteration in Javascript gibt.

Ich weiß, dass in einigen Sprachen (wo die Design-Iteration eine bessere Leistung erbringt) der Unterschied minimal ist, da der Interpreter / Compiler die Rekursion in eine Iteration umwandelt. Ich vermute jedoch, dass dies bei Javascript wahrscheinlich nicht der Fall ist, da es zumindest teilweise funktionsfähig ist Sprache.

javascript functional-programming recursion mastazi
quelle
3
Machen Sie Ihren eigenen Test und finden Sie es sofort heraus unter jsperf.com
TehShrike
mit dem Kopfgeld und einer Antwort, die TCO erwähnt. Es sieht so aus, als ob ES6 die Gesamtbetriebskosten spezifiziert, aber bisher wird sie von niemandem implementiert, wenn wir glauben, dass kangax.github.io/compat-table/es6 Vermisse ich etwas?
Matthias Kauer

Antworten:

28

JavaScript führt keine Schwanzrekursionsoptimierung durch. Wenn Ihre Rekursion also zu tief ist, kann es zu einem Call-Stack-Überlauf kommen. Iteration hat solche Probleme nicht. Wenn Sie der Meinung sind, dass Sie zu viele Rekursionen durchführen werden und eine Rekursion wirklich benötigen (zum Beispiel, um eine Überflutung durchzuführen), ersetzen Sie die Rekursion durch Ihren eigenen Stapel.

Die Rekursionsleistung ist wahrscheinlich schlechter als die Iterationsleistung, da Funktionsaufrufe und -rückgaben die Beibehaltung und Wiederherstellung des Zustands erfordern, während die Iteration einfach zu einem anderen Punkt in einer Funktion springt.

Triang3l
quelle
Ich frage mich nur ... Ich habe ein bisschen Code gesehen, in dem ein leeres Array erstellt und die rekursive Funktionssite einer Position im Array zugewiesen wird, und dann wird der im Array gespeicherte Wert zurückgegeben. Ist es das, was Sie mit "Ersetzen Sie die Rekursion durch Ihren eigenen Stapel" meinen? ZB: var stack = []; var factorial = function(n) { if(n === 0) { return 1 } else { stack[n-1] = n * factorial(n - 1); return stack[n-1]; } }
Mastazi
@mastazi: Nein, dies wird zusammen mit dem internen Aufruf einen nutzlosen Aufrufstapel erzeugen. Ich meinte so etwas wie das Queue-basierte Flood-Fill von Wikipedia .
Triang3l
Es ist erwähnenswert, dass eine Sprache keine TCO durchführt, eine Implementierung jedoch. Die Art und Weise, wie Leute JS optimieren, bedeutet, dass TCO in einigen Implementierungen auftreten könnte
Daniel Gratzer,
1
@mastazi Ersetzen Sie die elsein dieser Funktion mit else if (stack[n-1]) { return stack[n-1]; } elseund Sie haben Memoization . Wer auch immer diesen Fakultätscode geschrieben hat, hatte eine unvollständige Implementierung (und sollte wahrscheinlich stack[n]überall anstelle von verwendet haben stack[n-1]).
Izkata
Vielen Dank, @Izkata, ich mache oft solche Optimierungen, aber bis heute kannte ich den Namen nicht. Ich hätte CS statt IT
studieren sollen ;-)
20

Update : Seit ES2015 hat JavaScript die Gesamtbetriebskosten ( TCO) , sodass ein Teil des nachstehenden Arguments nicht mehr gültig ist .

Obwohl Javascript keine Tail-Call-Optimierung bietet, ist Rekursion oft der beste Weg. Und mit freundlichen Grüßen, außer in Randfällen, werden Sie keine Call-Stack-Überläufe bekommen.

Die Leistung muss beachtet werden, aber auch die vorzeitige Optimierung. Wenn Sie der Meinung sind, dass Rekursion eleganter ist als Iteration, dann entscheiden Sie sich dafür. Wenn sich herausstellt, dass dies Ihr Engpass ist (der möglicherweise niemals sein wird), können Sie ihn durch eine hässliche Iteration ersetzen. In den meisten Fällen liegt der Engpass jedoch in den DOM-Manipulationen oder allgemeiner in der E / A, nicht im Code selbst.

Rekursion ist immer eleganter 1 .

1 : Persönliche Meinung.

Florian Margaine
quelle
3
Ich bin damit einverstanden, dass Rekursion eleganter ist und Eleganz wichtig ist, da es sowohl Lesbarkeit als auch Wartbarkeit ist (dies ist subjektiv, aber meiner Meinung nach ist Rekursion sehr einfach zu lesen und daher wartbar). Manchmal ist jedoch die Leistung von Bedeutung. Können Sie die Behauptung unterstützen, dass Rekursion der beste Weg ist, auch in Bezug auf die Leistung?
Mastazi
3
@mastazi Wie in meiner Antwort gesagt, bezweifle ich, dass Rekursion Ihr Engpass sein wird. In den meisten Fällen handelt es sich um die DOM-Manipulation oder allgemeiner um die E / A. Und vergessen Sie nicht, dass vorzeitige Optimierung die Wurzel aller Übel ist;)
Florian Margaine
+1 für DOM-Manipulation ist meistens ein Engpass! Ich erinnere mich an ein sehr interessantes Interview mit Yehuda Katz (Ember.js) darüber.
Mastazi
1
@mike Die Definition von "verfrüht" ist "reif oder reif vor dem richtigen Zeitpunkt". Wenn Sie wissen, dass rekursives Handeln zu einem Stapelüberlauf führt, ist dies nicht verfrüht. Wenn Sie jedoch aus einer Laune heraus (ohne tatsächliche Daten) davon ausgehen, ist es verfrüht.
Zirak
2
Mit Javascript wissen Sie nicht, wie viel Stack das Programm zur Verfügung hat. Sie könnten einen winzigen Stapel in IE6 oder einen großen Stapel in FireFox haben. Rekursive Algorithmen haben selten eine feste Tiefe, es sei denn, Sie führen eine rekursive Schleife im Schema-Stil durch. Es scheint einfach nicht so, als ob eine nicht schleifenbasierte Rekursion dazu passt, vorzeitige Optimierungen zu vermeiden.
mike30
7

Ich war auch ziemlich neugierig auf diese Leistung in Javascript, daher habe ich einige Experimente durchgeführt (allerdings mit einer älteren Version von node). Ich habe einen Fakultätsrechner rekursiv gegen Iterationen geschrieben und einige Male lokal ausgeführt. Das Ergebnis schien ziemlich stark in Richtung Rekursion mit einer Steuer (erwartet) verzerrt.

Code: https://github.com/j03m/trickyQuestions/blob/master/factorial.js

Result:
j03m-MacBook-Air:trickyQuestions j03m$ node factorial.js 
Time:557
Time:126
j03m-MacBook-Air:trickyQuestions j03m$ node factorial.js 
Time:519
Time:120
j03m-MacBook-Air:trickyQuestions j03m$ node factorial.js 
Time:541
Time:123
j03m-MacBook-Air:trickyQuestions j03m$ node --version
v0.8.22
Dr.HappyPants
quelle
Sie könnten dies mit versuchen "use strict";und sehen, ob es einen Unterschied macht. (Es wird jumps anstelle der Standardanrufsequenz produzieren)
Burdock
1
Auf einer neueren Version von Node (6.9.1) habe ich sehr ähnliche Ergebnisse erhalten. Es gibt eine gewisse Steuer auf Rekursion, aber ich halte es für einen Randfall - 400 ms Unterschied für 1.000.000 Schleifen sind .0025 ms pro Schleife. Wenn Sie 1.000.000 Loops ausführen, sollten Sie dies berücksichtigen.
Kelz
6

Auf Wunsch des OP mische ich mich ein (ohne mich lächerlich zu machen, hoffentlich: P)

Ich denke, wir sind uns alle einig, dass Rekursion nur eine elegantere Art der Codierung ist. Wenn es gut gemacht wird, kann es zu einem wartbareren Code führen, was meiner Meinung nach genauso wichtig ist (wenn nicht sogar mehr), als 0,0001 ms zu sparen.

In Bezug auf das Argument, dass JS keine Tail-Call-Optimierung durchführt, trifft dies nicht mehr zu. Die Verwendung des Strict-Modus von ECMA5 ermöglicht TCO. Es war etwas, worüber ich mich vor einiger Zeit nicht besonders gefreut habe, aber jetzt weiß ich zumindest, warum arguments.calleeFehler im strengen Modus ausgelöst werden. Ich kenne den obigen Link zu einem Fehlerbericht, aber der Fehler ist auf WONTFIX gesetzt. Außerdem kommt die Standard-TCO: ECMA6 (Dezember 2013).

Instinktiv und unter Beibehaltung der Funktionalität von JS würde ich sagen, dass Rekursion in 99,99% der Fälle der effizientere Codierungsstil ist. Florian Margaine hat jedoch einen Punkt, an dem er sagt, dass der Engpass wahrscheinlich woanders zu finden ist. Wenn Sie das DOM manipulieren, konzentrieren Sie sich wahrscheinlich am besten darauf, Ihren Code so wartbar wie möglich zu machen. Die DOM-API ist wie sie ist: langsam.

Ich denke, es ist so gut wie unmöglich, eine endgültige Antwort darauf zu geben, welche Option schneller ist. In letzter Zeit haben viele jsprefs gezeigt, dass die V8-Engine von Chrome bei einigen Aufgaben, die auf FFs SpiderMonkey 4x langsamer laufen, lächerlich schnell ist und umgekehrt. Moderne JS-Engines haben alle möglichen Tricks parat, um Ihren Code zu optimieren. Ich bin kein Experte, aber ich bin der Meinung, dass beispielsweise V8 in hohem Maße für das Schließen (und die Rekursion) optimiert ist, wohingegen die JScript-Engine von MS dies nicht ist. SpiderMonkey bietet häufig eine bessere Leistung, wenn das DOM beteiligt ist ...

Kurz gesagt: Ich würde sagen, welche Technik leistungsstärker sein wird, ist wie immer in JS nahezu unmöglich vorherzusagen.

Elias Van Ootegem
quelle
3

Ohne den strikten Modus ist die Iterationsleistung normalerweise etwas schneller als die Rekursion ( zusätzlich dazu, dass die JIT mehr Arbeit leistet ). Durch die Optimierung der Schwanzrekursion werden spürbare Unterschiede im Wesentlichen beseitigt, da die gesamte Aufrufsequenz in einen Sprung umgewandelt wird.

Beispiel: Jsperf

Ich würde vorschlagen, dass Sie sich mehr Gedanken über die Klarheit und Einfachheit des Codes machen, wenn Sie zwischen Rekursion und Iteration wählen.

Klette
quelle