[Adresse dieses Artikels] http://cuimingda.com/2009/02/speed-up-your-javascript-part-3.html
Rekursion ist einer der Feinde, der die Ausführungsgeschwindigkeit von Skripten verlangsamt. Zu viel Rekursion führt dazu, dass der Browser immer langsamer wird, bis er stirbt oder plötzlich und aus unerklärlichen Gründen automatisch beendet wird. Daher müssen wir diese Reihe von Leistungsproblemen in JavaScript lösen. Im zweiten Artikel dieser Serie habe ich kurz vorgestellt, wie man mithilfe der Memoisierungstechnologie zu viele rekursive Aufrufe in Funktionen ersetzt. Bei der Memoisierung handelt es sich um eine Technik, die die Ergebnisse früherer Berechnungen zwischenspeichert, sodass wir bereits berechnete Ergebnisse nicht erneut berechnen müssen. Für Funktionen, die Berechnungen durch Rekursion durchführen, ist das Auswendiglernen einfach zu nützlich. Der Memoizer, den ich derzeit verwende, wurde von Crockford geschrieben und wird hauptsächlich in rekursiven Operationen verwendet, die ganze Zahlen zurückgeben. Natürlich geben nicht alle rekursiven Funktionen Ganzzahlen zurück, daher benötigen wir eine allgemeinere Funktion memoizer(), um mehr Arten rekursiver Funktionen verarbeiten zu können.
Funktion Memoizer(Fundamental, Cache){ Cache = Cache ||. {} var Shell = Funktion(Arg){ if (!(Arg im Cache)){ Cache[Arg] = Fundamental(Shell, Argument) ; }; return shell;} Diese Version der Funktion unterscheidet sich geringfügig von der von Crockford. Zunächst wird die Reihenfolge der Parameter umgekehrt, die ursprüngliche Funktion wird als erster Parameter festgelegt und der zweite Parameter ist das Cache-Objekt. Dies ist optional, da nicht alle rekursiven Funktionen Anfangsinformationen enthalten. Innerhalb der Funktion habe ich den Typ des Cache-Objekts von einem Array in ein Objekt umgewandelt, damit diese Version rekursive Funktionen unterstützen kann, die keine Ganzzahlen zurückgeben. In der Shell-Funktion verwende ich den in-Operator, um festzustellen, ob die Parameter bereits im Cache enthalten sind. Diese Schreibweise ist sicherer als zu testen, ob der Typ nicht undefiniert ist, da undefiniert ein gültiger Rückgabewert ist. Zur Veranschaulichung verwenden wir immer noch die zuvor erwähnte Fibonacci-Folge:
var fibonacci = memoizer(function (recur, n) { return recur(n - 1) + recur(n - 2); }, {"0": 0, "1" :1}); Ebenso wird beim Ausführen der Funktion fibonacci(40) die ursprüngliche Funktion nur 40 Mal aufgerufen, statt der übertriebenen 331.160.280 Mal. Die Memoisierung eignet sich hervorragend für rekursive Algorithmen mit streng definierten Ergebnismengen. Es gibt jedoch tatsächlich viele rekursive Algorithmen, die nicht für die Optimierung mithilfe von Memoisierungsmethoden geeignet sind.
Einer meiner Professoren in der Schule bestand immer darauf, dass jede Situation, in der Rekursion verwendet wurde, bei Bedarf durch Iteration ersetzt werden könne. Tatsächlich werden Rekursion und Iteration häufig als Methoden verwendet, um sich gegenseitig zu kompensieren, insbesondere wenn die andere Methode schief geht. Die Technologie zur Umwandlung rekursiver Algorithmen in iterative Algorithmen ist auch unabhängig von der Entwicklungssprache. Die Bedeutung bei JavaScript ist jedoch größer, da die Ressourcen der Ausführungsumgebung so restriktiv sind. Sehen wir uns einen typischen rekursiven Algorithmus wie Merge Sort an. Die Implementierung dieses Algorithmus in JavaScript erfordert den folgenden Code:
function merge(left, right){ var result = [] while (left.length > 0 && right.length > 0) { if (left[0] < right[0]){ result.push(left.shift()); } else { result.push(right.shift()); (right);}//Merge-Sortieralgorithmus-Funktion mergeSort(items){ if (items.length == 1) { return items; } var middle = Math.floor(items.length / 2) using recursion , left = items. Slice(0, middle), right = items.slice(middle); return merge(mergeSort(left), mergeSort(right));} Rufen Sie die Funktion mergeSort() auf, um ein Array zu verarbeiten, und Sie können das sortierte Array zurückgeben. Beachten Sie, dass es bei jedem Aufruf der Funktion mergeSort() zwei rekursive Aufrufe gibt. Dieser Algorithmus kann nicht durch Memoisierung optimiert werden, da jedes Ergebnis nur einmal berechnet und verwendet wird und selbst das Puffern der Ergebnisse keinen Nutzen hat. Wenn Sie die Funktion mergeSort() für ein Array mit 100 Elementen verwenden, gibt es insgesamt 199 Aufrufe. Ein Array mit 1000 Elementen führt 1999 Aufrufe durch. In diesem Fall besteht unsere Lösung darin, den rekursiven Algorithmus in einen iterativen Algorithmus umzuwandeln, was bedeutet, dass einige Schleifen eingeführt werden müssen (Informationen zum Algorithmus finden Sie in diesem Artikel „Listenverarbeitung: Natürlich noch einmal sortieren“):
// Iterative Implementierung verwenden Sortieralgorithmus zusammenführen Funktion mergeSort(items){ if (items.length == 1) { return items; var i=0, len=items.length; i < len; i++){ work .push([items[i]]); } work.push([]); //bei ungerader Anzahl von Elementen für (var lim=len; lim > 1; lim = (lim+1)/2 ) { for (var j=0,k=0; k < lim; j++, k+=2){ work[j] = merge(work[k], work[k+1] } work[j] = [ ]; //bei ungerader Anzahl von Elementen } return work[0];}Diese Implementierung des Merge-Sortieralgorithmus verwendet eine Reihe von Schleifen anstelle einer Rekursion zum Sortieren. Da Merge Sort das Array zunächst in mehrere Arrays mit nur einem Element aufteilt, führt diese Methode diesen Vorgang expliziter aus, anstatt implizit eine rekursive Funktion zu verwenden. Das Arbeitsarray wird so initialisiert, dass es ein Array aus Ein-Element-Arrays enthält. Jedes Mal in der Schleife werden die beiden Arrays zusammengeführt und das zusammengeführte Ergebnis wird zurück in das Arbeitsarray gestellt. Wenn die Funktion ausgeführt wird, wird das sortierte Ergebnis über das erste Element im Arbeitsarray zurückgegeben. In dieser Implementierung der Zusammenführungssortierung wird der Algorithmus auch ohne Verwendung einer Rekursion implementiert. Dies führt jedoch zu einer großen Anzahl von Schleifen, und die Anzahl der Schleifen basiert auf der Anzahl der zu sortierenden Elemente im Array. Daher müssen wir es möglicherweise mithilfe der im vorherigen Artikel beschriebenen Techniken ändern, um diesen zusätzlichen Overhead zu bewältigen .
Um die Grundprinzipien zusammenzufassen: Sie sollten bei der Verwendung von Rekursion vorsichtig sein. Memoisierung und Iteration sind zwei Lösungen, um die Rekursion zu ersetzen. Das direkteste Ergebnis besteht natürlich darin, das Dialogfeld zu vermeiden, das dazu führt, dass das Skript außer Kontrolle gerät.