[Адрес этой статьи] http://cuimingda.com/2009/02/speed-up-your-javascript-part-3.html
Рекурсия — один из врагов, замедляющих скорость выполнения сценариев. Слишком большая рекурсия будет делать браузер все медленнее и медленнее, пока он не умрет или не завершится автоматически внезапно и необъяснимо, поэтому мы должны решить эту серию проблем с производительностью в JavaScript. Во второй статье этой серии я кратко рассказал, как использовать технологию мемоизации для замены слишком большого количества рекурсивных вызовов в функциях. Мемоизация — это метод, который кэширует результаты предыдущих вычислений, чтобы нам не нужно было пересчитывать те результаты, которые уже были рассчитаны. Для функций, выполняющих вычисления посредством рекурсии, мемоизация слишком полезна. Мемоайзер, который я сейчас использую, был написан Крокфордом и в основном используется в рекурсивных операциях, возвращающих целые числа. Конечно, не все рекурсивные функции возвращают целые числа, поэтому нам нужна более общая функция memoizer() для обработки большего количества типов рекурсивных функций.
function memoizer(fundamental,cache){cache =cache || {} varshell = function(arg){ if (!(arg в кеше)){cache[arg] = фундаментальный(shell, arg) } returncache[arg] ; }; return Shell;} Эта версия функции немного отличается от написанной Крокфордом. Во-первых, порядок параметров меняется на обратный, в качестве первого параметра задается исходная функция, а вторым параметром является объект кэша, что необязательно, поскольку не все рекурсивные функции содержат исходную информацию. Внутри функции я привожу тип объекта кэша из массива к объекту, чтобы эта версия могла поддерживать рекурсивные функции, которые не возвращают целые числа. В функции оболочки я использую оператор in, чтобы определить, включены ли параметры уже в кеш. Этот способ записи безопаснее, чем проверка того, что тип не является неопределенным, поскольку undefined является допустимым возвращаемым значением. Мы по-прежнему используем упомянутую ранее последовательность Фибоначчи для иллюстрации:
var fibonacci = memoizer(function (recur, n) { return recur(n - 1) + recur(n - 2); }, {"0": 0, "1" :1}); Аналогично, выполнение функции fibonacci(40) вызовет исходную функцию только 40 раз вместо преувеличенных 331 160 280 раз. Мемоизация отлично подходит для рекурсивных алгоритмов со строго определенными наборами результатов. Однако действительно существует множество рекурсивных алгоритмов, которые не подходят для оптимизации с помощью методов мемоизации.
Один из моих школьных профессоров всегда настаивал на том, что любую ситуацию, в которой используется рекурсия, при необходимости можно заменить итерацией. Фактически, рекурсия и итерация часто используются как методы компенсации друг друга, особенно когда другой идет не так. Технология преобразования рекурсивных алгоритмов в итеративные также не зависит от языка разработки. Однако важность в JavaScript выше, поскольку ресурсы среды выполнения очень ограничены. Давайте рассмотрим типичный рекурсивный алгоритм, такой как сортировка слиянием. Для реализации этого алгоритма в JavaScript требуется следующий код:
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); (справа);}//Алгоритм сортировки слиянием function mergeSort(items){ if (items.length == 1) { return items } var middle = Math.floor(items.length / 2) с использованием рекурсии, left = items. срез(0, средний), правый = items.slice(средний); return merge(mergeSort(left), mergeSort(right));} Вызовите функцию mergeSort() для обработки массива, и вы сможете вернуть отсортированный массив. Обратите внимание, что при каждом вызове функции mergeSort() происходит два рекурсивных вызова. Этот алгоритм нельзя оптимизировать с помощью мемоизации, поскольку каждый результат вычисляется и используется только один раз, и даже буферизация результатов бесполезна. Если вы используете функцию mergeSort() для массива из 100 элементов, всего будет 199 вызовов. Массив из 1000 элементов выполнит 1999 вызовов. В этом случае наше решение состоит в том, чтобы преобразовать рекурсивный алгоритм в итеративный алгоритм, что означает введение некоторых циклов (по алгоритму вы можете обратиться к этой статье «Обработка списков: повторная сортировка, естественно»):
// Использовать итеративную реализацию Алгоритм сортировки слиянием function mergeSort(items){ if (items.length == 1) { return items = []; for (var i=0, len=items.length; i < len; i++){ work; .push([items[i]]); } work.push([]); //в случае нечетного количества элементов for (var lim=len; lim > 1; lim = (lim+1)/2 ) { for (var j=0,k=0; k < lim; j++, k+=2){ работа[j] = merge(work[k], работа[k+1]); работа[j] = [ ]; //в случае нечетного количества элементов } return work[0];}Эта реализация алгоритма сортировки слиянием использует серию циклов вместо рекурсии для сортировки. Поскольку сортировка слиянием сначала разбивает массив на несколько массивов, содержащих только один элемент, этот метод выполняет эту операцию более явно, а не неявно, используя рекурсивную функцию. Рабочий массив инициализируется и содержит массив одноэлементных массивов. Каждый раз в цикле два массива объединяются, и результат объединения возвращается в рабочий массив. Когда функция будет выполнена, отсортированный результат будет возвращен через первый элемент рабочего массива. В этой реализации сортировки слиянием алгоритм также реализован без использования рекурсии. Однако это приводит к появлению большого количества циклов, а количество циклов зависит от количества элементов в сортируемом массиве, поэтому нам может потребоваться изменить его, используя методы, описанные в предыдущей статье, чтобы справиться с этими дополнительными накладными расходами. .
Подводя итог основным принципам, следует проявлять осторожность при использовании рекурсии. Мемоизация и итерация — два решения для замены рекурсии. Наиболее прямой результат, конечно, заключается в том, чтобы избежать диалогового окна, которое предлагает сценарию выйти из-под контроля.