[Dirección de este artículo] http://cuimingda.com/2009/02/speed-up-your-javascript-part-3.html
La recursión es uno de los enemigos que ralentiza la velocidad de ejecución de los scripts. Demasiada recursividad hará que el navegador sea cada vez más lento hasta que muera o se cierre automáticamente de manera repentina e inexplicable, por lo que debemos resolver esta serie de problemas de rendimiento en JavaScript. En el segundo artículo de esta serie, presenté brevemente cómo utilizar la tecnología de memorización para reemplazar demasiadas llamadas recursivas en funciones. La memorización es una técnica que almacena en caché los resultados de cálculos anteriores para que no necesitemos volver a calcular los resultados que ya se han calculado. Para funciones que realizan cálculos mediante recursividad, la memorización es simplemente demasiado útil. El memorizador que estoy usando actualmente fue escrito por Crockford y se usa principalmente en operaciones recursivas que devuelven números enteros. Por supuesto, no todas las funciones recursivas devuelven números enteros, por lo que necesitamos una función memoizer() más general para manejar más tipos de funciones recursivas.
función memorizador(fundamental, caché){ caché = caché || {} var shell = función(arg){ if (!(arg en caché)){ caché[arg] = fundamental(shell, arg) } return caché[arg] ; }; return shell;} Esta versión de la función es ligeramente diferente de la escrita por Crockford. Primero, se invierte el orden de los parámetros, la función original se establece como el primer parámetro y el segundo parámetro es el objeto de caché, que es opcional porque no todas las funciones recursivas contienen información inicial. Dentro de la función, transfiero el tipo de objeto de caché de una matriz a un objeto para que esta versión pueda acomodar funciones recursivas que no devuelven números enteros. En la función de shell, uso el operador in para determinar si los parámetros ya están incluidos en el caché. Esta forma de escribir es más segura que probar que el tipo no sea indefinido, porque indefinido es un valor de retorno válido. Todavía usamos la secuencia de Fibonacci mencionada antes para ilustrar:
var fibonacci = memoizer(function (recur, n) { return recur(n - 1) + recur(n - 2); }, {"0": 0, "1" :1}); de manera similar, ejecutar la función fibonacci(40) solo llamará a la función original 40 veces, en lugar de las exageradas 331,160,280 veces. La memorización es excelente para algoritmos recursivos con conjuntos de resultados estrictamente definidos. Sin embargo, existen muchos algoritmos recursivos que no son adecuados para la optimización mediante métodos de memorización.
Uno de mis profesores en la escuela siempre insistió en que cualquier situación en la que se utilizara la recursividad podría ser reemplazada por la iteración si fuera necesario. De hecho, la recursividad y la iteración se utilizan a menudo como métodos para compensarse entre sí, especialmente cuando el otro sale mal. La tecnología de convertir algoritmos recursivos en algoritmos iterativos también es independiente del lenguaje de desarrollo. Sin embargo, la importancia en JavaScript es mayor porque los recursos del entorno de ejecución son muy restrictivos. Repasemos un algoritmo recursivo típico, como la ordenación por combinación. La implementación de este algoritmo en JavaScript requiere el siguiente código:
function merge(left, right){ var result = [] while (left.length > 0 && right.length > 0) { if (izquierda[0] < derecha[0]){ resultado.push(izquierda.shift() } else { resultado.push(derecha.shift() } } return resultado.concat(izquierda ).concat); (derecha);}//Función del algoritmo de clasificación de fusión mergeSort(items){ if (items.length == 1) { return items; } var middle = Math.floor(items.length / 2) usando recursividad, left = items. slice(0, middle), right = items.slice(middle); return merge(mergeSort(left), mergeSort(right));} Llame a la función mergeSort() para procesar una matriz y podrá devolver la matriz ordenada. Tenga en cuenta que cada vez que se llama a la función mergeSort(), habrá dos llamadas recursivas. Este algoritmo no se puede optimizar mediante la memorización, porque cada resultado se calcula y se usa solo una vez, e incluso almacenar los resultados en un buffer no sirve de nada. Si utiliza la función mergeSort() en una matriz de 100 elementos, habrá un total de 199 llamadas. Una matriz de 1000 elementos realizará 1999 llamadas. En este caso, nuestra solución es convertir el algoritmo recursivo en un algoritmo iterativo, lo que significa introducir algunos bucles (para el algoritmo, puede consultar este artículo "Procesamiento de listas: ordenar de nuevo, naturalmente"):
// Utilice la implementación iterativa función de algoritmo de clasificación de fusión 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 caso de número impar de elementos para (var lim=len; lim > 1; lim = (lim+1)/2 ) { for (var j=0,k=0; k < lim; j++, k+=2){ trabajo[j] = merge(trabajo[k], trabajo[k+1]); trabajo[j] = [ ]; //en caso de un número impar de elementos } return work[0];}Esta implementación del algoritmo de clasificación por combinación utiliza una serie de bucles en lugar de recursividad para la clasificación. Dado que la ordenación por fusión primero divide la matriz en varias matrices con un solo elemento, este método realiza esta operación de manera más explícita en lugar de implícitamente utilizando una función recursiva. La matriz de trabajo se inicializa para contener una matriz de matrices de un elemento. Cada vez que se realiza el ciclo, las dos matrices se fusionan y el resultado fusionado se vuelve a colocar en la matriz de trabajo. Cuando se ejecuta la función, el resultado ordenado se devolverá a través del primer elemento de la matriz de trabajo. En esta implementación de ordenación por fusión, el algoritmo también se implementa sin utilizar ninguna recursividad. Sin embargo, esto introduce una gran cantidad de bucles, y el número de bucles se basa en la cantidad de elementos de la matriz que se van a ordenar, por lo que es posible que debamos modificarlo utilizando las técnicas analizadas en el artículo anterior para abordar esta sobrecarga adicional. .
Para resumir los principios básicos, se debe tener cuidado al utilizar la recursividad. La memorización y la iteración son dos soluciones para reemplazar la recursividad. El resultado más directo es, por supuesto, evitar el cuadro de diálogo que indica que el script está fuera de control.