[Adresse de cet article] http://cuimingda.com/2009/02/speed-up-your-javascript-part-3.html
La récursion est l'un des ennemis qui ralentit la vitesse d'exécution des scripts. Trop de récursivité rendra le navigateur de plus en plus lent jusqu'à ce qu'il meure ou se ferme automatiquement de manière soudaine et inexplicable, nous devons donc résoudre cette série de problèmes de performances en JavaScript. Dans le deuxième article de cette série, j'ai brièvement présenté comment utiliser la technologie de mémorisation pour remplacer trop d'appels récursifs dans les fonctions. La mémorisation est une technique qui met en cache les résultats des calculs précédents afin que nous n'ayons pas besoin de recalculer les résultats déjà calculés. Pour les fonctions qui effectuent des calculs par récursion, la mémorisation est tout simplement trop utile. Le mémoizer que j'utilise actuellement a été écrit par Crockford et est principalement utilisé dans les opérations récursives qui renvoient des entiers. Bien sûr, toutes les fonctions récursives ne renvoient pas des entiers, nous avons donc besoin d'une fonction memoizer() plus générale pour gérer davantage de types de fonctions récursives.
function memoizer(fondamental, cache){ cache = cache || {} var shell = function(arg){ if (!(arg in cache)){ cache[arg] = fondamental(shell, arg) } return cache[arg] ; }; return shell;} Cette version de la fonction est légèrement différente de celle écrite par Crockford. Premièrement, l'ordre des paramètres est inversé, la fonction d'origine est définie comme premier paramètre et le deuxième paramètre est l'objet cache, ce qui est facultatif car toutes les fonctions récursives ne contiennent pas d'informations initiales. À l'intérieur de la fonction, je convertis le type de l'objet cache d'un tableau en un objet afin que cette version puisse prendre en charge les fonctions récursives qui ne renvoient pas d'entiers. Dans la fonction shell, j'utilise l'opérateur in pour déterminer si les paramètres sont déjà inclus dans le cache. Cette façon d'écrire est plus sûre que de tester que le type n'est pas indéfini, car indéfini est une valeur de retour valide. Nous utilisons toujours la séquence de Fibonacci mentionnée précédemment pour illustrer :
var fibonacci = memoizer(function (recur, n) { return recur(n - 1) + recur(n - 2); }, {"0": 0, "1" :1}); De même, l'exécution de la fonction fibonacci(40) n'appellera la fonction d'origine que 40 fois, au lieu des 331 160 280 fois exagérées. La mémorisation est idéale pour les algorithmes récursifs avec des ensembles de résultats strictement définis. Cependant, il existe effectivement de nombreux algorithmes récursifs qui ne sont pas adaptés à une optimisation par des méthodes de mémorisation.
Un de mes professeurs à l'école a toujours insisté sur le fait que toute situation dans laquelle la récursivité était utilisée pouvait être remplacée par une itération si nécessaire. En fait, la récursivité et l’itération sont souvent utilisées comme méthodes pour se compenser, surtout lorsque l’autre tourne mal. La technologie de conversion d’algorithmes récursifs en algorithmes itératifs est également indépendante du langage de développement. L'importance de JavaScript est cependant plus grande, car les ressources de l'environnement d'exécution sont très restrictives. Passons en revue un algorithme récursif typique, tel que le tri par fusion. L'implémentation de cet algorithme en JavaScript nécessite le code suivant :
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() } } return result.concat(left ).concat); (à droite);}//Fonction de l'algorithme de tri de fusion mergeSort(items){ if (items.length == 1) { return items; } var middle = Math.floor(items.length / 2) en utilisant la récursivité, left = items. slice(0, middle), right = items.slice(middle); return merge(mergeSort(left), mergeSort(right));} Appelez la fonction mergeSort() pour traiter un tableau et vous pourrez renvoyer le tableau trié. Notez que chaque fois que la fonction mergeSort() est appelée, il y aura deux appels récursifs. Cet algorithme ne peut pas être optimisé par mémorisation, car chaque résultat est calculé et utilisé une seule fois, et même la mise en mémoire tampon des résultats ne sert à rien. Si vous utilisez la fonction mergeSort() sur un tableau de 100 éléments, il y aura un total de 199 appels. Un tableau de 1 000 éléments effectuera 1 999 appels. Dans ce cas, notre solution est de convertir l'algorithme récursif en un algorithme itératif, ce qui implique d'introduire quelques boucles (pour l'algorithme, vous pouvez vous référer à cet article "Traitement des listes : trier à nouveau, naturellement") :
// Utiliser l'implémentation itérative algorithme de tri de fusion function mergeSort(items){ if (items.length == 1) { return items; var work = []; for (var i=0, len=items.length; i < len; i++){ work .push([items[i]]); } work.push([]); //en cas de nombre impair d'éléments pour (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] = [ ]; //en cas de nombre impair d'éléments } return work[0];}Cette implémentation de l'algorithme de tri par fusion utilise une série de boucles au lieu de la récursion pour le tri. Étant donné que le tri par fusion divise d'abord le tableau en plusieurs tableaux avec un seul élément, cette méthode effectue cette opération de manière plus explicite plutôt qu'implicitement en utilisant une fonction récursive. Le tableau de travail est initialisé pour contenir un tableau de tableaux à un élément. À chaque fois dans la boucle, les deux tableaux sont fusionnés et le résultat fusionné est remis dans le tableau de travail. Lorsque la fonction est exécutée, le résultat trié sera renvoyé via le premier élément du tableau de travail. Dans cette implémentation du tri par fusion, l'algorithme est également implémenté sans utiliser de récursion. Cependant, cela introduit un grand nombre de boucles, et le nombre de boucles est basé sur le nombre d'éléments du tableau à trier, nous devrons donc peut-être le modifier en utilisant les techniques évoquées dans l'article précédent pour gérer cette surcharge supplémentaire. .
Pour résumer les principes de base, vous devez être prudent lorsque vous utilisez la récursivité. La mémorisation et l'itération sont deux solutions pour remplacer la récursion. Le résultat le plus direct est bien sûr d'éviter la boîte de dialogue qui incite le script à devenir incontrôlable.