[Endereço deste artigo] http://cuimingda.com/2009/02/speed-up-your-javascript-part-3.html
A recursão é um dos inimigos que diminui a velocidade de execução dos scripts. Muita recursão tornará o navegador cada vez mais lento até que ele morra ou saia automaticamente de repente e inexplicavelmente, portanto, devemos resolver essa série de problemas de desempenho em JavaScript. No segundo artigo desta série, apresentei brevemente como usar a tecnologia de memoização para substituir muitas chamadas recursivas em funções. Memoização é uma técnica que armazena em cache os resultados de cálculos anteriores para que não precisemos recalcular os resultados que já foram calculados. Para funções que realizam cálculos por meio de recursão, a memorização é simplesmente muito útil. O memoizer que estou usando atualmente foi escrito por Crockford e é usado principalmente em operações recursivas que retornam números inteiros. É claro que nem todas as funções recursivas retornam números inteiros, então precisamos de uma função memoizer() mais geral para lidar com mais tipos de funções recursivas.
function memoizer(fundamental, cache){ cache = cache || {} var shell = function(arg){ if (!(arg in cache)){ cache[arg] = fundamental(shell, arg) } return cache[arg] ; }; return shell;} Esta versão da função é ligeiramente diferente daquela escrita por Crockford. Primeiro, a ordem dos parâmetros é invertida, a função original é definida como o primeiro parâmetro e o segundo parâmetro é o objeto de cache, que é opcional porque nem todas as funções recursivas contêm informações iniciais. Dentro da função, converto o tipo do objeto de cache de um array para um objeto para que esta versão possa acomodar funções recursivas que não retornam números inteiros. Na função shell, uso o operador in para determinar se os parâmetros já estão incluídos no cache. Essa forma de escrever é mais segura do que testar se o tipo não é indefinido, porque indefinido é um valor de retorno válido. Ainda usamos a sequência de Fibonacci mencionada anteriormente para ilustrar:
var fibonacci = memoizer(function (recur, n) { return recur(n - 1) + recur(n - 2); }, {"0": 0, "1" :1}); Da mesma forma, executar a função fibonacci(40) chamará a função original apenas 40 vezes, em vez das exageradas 331.160.280 vezes. A memorização é ótima para algoritmos recursivos com conjuntos de resultados estritamente definidos. No entanto, existem de fato muitos algoritmos recursivos que não são adequados para otimização usando métodos de memoização.
Um dos meus professores na escola sempre insistiu que qualquer situação em que a recursão fosse usada poderia ser substituída por iteração, se necessário. Na verdade, a recursão e a iteração são frequentemente usadas como métodos para compensar uma à outra, especialmente quando a outra dá errado. A tecnologia de conversão de algoritmos recursivos em algoritmos iterativos também é independente da linguagem de desenvolvimento. A importância em JavaScript é maior porque os recursos do ambiente de execução são muito restritivos. Vamos revisar um algoritmo recursivo típico, como merge sort. A implementação desse algoritmo em JavaScript requer o seguinte código:
function merge(left, right){ var result = []; { if (esquerda[0] <direita[0]){ resultado.push(esquerda.shift() } else { resultado.push(direita.shift() } } retornar resultado.concat(esquerda).concat). (direita);}//Mesclar algoritmo de classificação function mergeSort(items){ if (items.length == 1) { return items } var middle = Math.floor(items.length / 2) usando recursão, left = items. slice(0, middle), right = items.slice(middle); return merge(mergeSort(left), mergeSort(right));} Chame a função mergeSort() para processar um array e você pode retornar o array classificado. Observe que cada vez que a função mergeSort() for chamada, haverá duas chamadas recursivas. Este algoritmo não pode ser otimizado usando memoização, pois cada resultado é calculado e usado apenas uma vez, e mesmo armazenar os resultados em buffer é inútil. Se você usar a função mergeSort() em um array de 100 elementos, haverá um total de 199 chamadas. Uma matriz de 1.000 elementos realizará 1.999 chamadas. Neste caso, nossa solução é converter o algoritmo recursivo em um algoritmo iterativo, o que significa introduzir alguns loops (para o algoritmo, você pode consultar este artigo "Processamento de lista: classificar novamente, naturalmente"):
// Use implementação iterativa O função de algoritmo de classificação de mesclagem mergeSort(items){ if (items.length == 1) { return items } var work = []; .push([items[i]]); } work.push([]); //no caso de número ímpar de itens para (var lim=len; lim > 1; lim = (lim+1)/2 ) { for (var j=0,k=0; k < lim; j++, k+=2){ trabalho[j] = mesclar(trabalho[k], trabalho[k+1]); ]; //no caso de número ímpar de itens } return work[0];}Esta implementação do algoritmo de classificação por mesclagem usa uma série de loops em vez de recursão para classificação. Como a classificação por mesclagem primeiro divide o array em vários arrays com apenas um elemento, esse método executa essa operação de forma mais explícita, em vez de usar implicitamente uma função recursiva. A matriz de trabalho é inicializada para conter uma matriz de matrizes de um elemento. Cada vez no loop, as duas matrizes são mescladas e o resultado mesclado é colocado de volta na matriz de trabalho. Quando a função for executada, o resultado classificado será retornado através do primeiro elemento da matriz de trabalho. Nesta implementação de merge sort, o algoritmo também é implementado sem usar qualquer recursão. No entanto, isso introduz um grande número de loops, e o número de loops é baseado no número de elementos na matriz a ser classificada, portanto, podemos precisar modificá-lo usando as técnicas discutidas no artigo anterior para lidar com essa sobrecarga adicional. .
Para resumir os princípios básicos, você deve ter cuidado ao usar a recursão. Memoização e iteração são duas soluções para substituir a recursão. O resultado mais direto é, obviamente, evitar a caixa de diálogo que faz com que o script fique fora de controle.