Реализация мемоизации в JavaScript
Программы часто тратят время на вызовы функции чтобы пересчитать те же результаты снова и снова. Это явление часто наблюдается с рекурсивными и математическими функциями. Прекрасный пример — генератор чисел Фибоначчи. Последовательность Фибоначчи представляет собой ряд целых чисел с нуля или единицы. Каждое следующее значение является суммой двух предыдущих. Исходя из этого определения, первые десять чисел Фибоначчи: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34. С точки зрения программирования, n-ое число Фибоначчи, как правило, вычисляется рекурсивно с использованием следующей функции.
function fibonacci(n) {
if (n === 0 || n === 1)
return n;
else
return fibonacci(n - 1) + fibonacci(n - 2);
}
Эта функция хорошо работает при малых значениях «n». Тем не менее, производительность быстро деградирует когда n увеличивается. Это происходит потому, что рекурсивные методы вынуждены частично выполнять одну и ту же работу. Например, чтобы вычислить 50-й член последовательности Фибоначчи, рекурсивная функция должна быть вызвана более 40 миллиардов раз (40,730,022,147…)! Что еще хуже, при вычислении 51-го члена, эта работа будет почти полностью дублироваться . Этой проблемы можно бы было избежать если б функция помнила, что ранее она уже вычисляла эти значения.
Основы мемоизации
Мемоизация представляет собой метод программирования, который помогает увеличить производительность функции путем кэширования своих ранее вычисленных результатов. Поскольку объекты JavaScript ведут себя как ассоциативные массивы, они идеально подходят кэша. Каждый раз, когда memoized функция вызывается, её параметры используются для индекса кэша. Если данные присутствуют — они могут быть возвращены без вызова функции. Тем не менее, если данных нет в кэше, то функция выполняется, и результат добавляется в кэш.
В следующем примере исходная функция Fibonacci переписана, чтобы включить возможность кэширования. Здесь само-исполняемая анонимная функция возвращает внутреннюю функцию f(), которая используется в качестве функции Fibonacci. При return f(), его замыкание позволяет ему доступаться к объекту «memo», который хранит все свои предыдущие результаты. Каждый раз, когда f() выполняется — она проверяет, существует ли результат для текущего значения «n». Если нужное значение есть, то кэшированное значение возвращается. В противном случае, исходный код Fibonacci выполняется. Обратите внимание, что «memo» определена вне f (), таким образом этот объект может сохранить свое значение на протяжении множества вызовов функции. Напомним, что оригинальная рекурсивная функция была вызвана более 40 миллиардов раз для вычисления 50 чисел Фибоначчи. Реализуя memoization, это число уменьшится до 99.
var fibonacci = (function() {
var memo = {};
function f(n) {
var value;
if (n in memo) {
value = memo[n];
} else {
if (n === 0 || n === 1)
value = n;
else
value = f(n - 1) + f(n - 2);
memo[n] = value;
}
return value;
}
return f;
})();
Обращение с несколькими аргументами
В предыдущем примере, функция принимается один аргумент и кэш реализован довольно тривиально. К сожалению, большинство функций требуют несколько аргументов, что затрудняет индексацию кэша. Для memoize функции с несколькими аргументами либо кэш должен стать многомерным, либо аргументы должны быть объединены чтобы сформировать единый индекс.
При реализации многомерного кэша он становится иерархией объектов. Затем каждый объект индексируется одним параметром. Следующий пример реализует многомерный кэш для функции Fibonacci. В этом примере, функция принимает дополнительный аргумент «x», который сейчас ничего не делает. Каждый раз, когда вызывается функция, код проверяет, что «x» объект существует или инициализирует его, если он не существует. С этого момента «х» используется для кэширования значения «n».
var fibonacci = (function() {
var memo = {};
function f(x, n) {
var value;
memo[x] = memo[x] || {};
if (x in memo && n in memo[x]) {
value = memo[x][n];
} else {
if (n === 0 || n === 1)
value = n;
else
value = f(x, n - 1) + f(x, n - 2);
memo[x][n] = value;
}
return value;
}
return f;
})();
Альтернатива многомерному кэшу — один объект кэша, который индексируется комбинацией всех аргументов функции. При таком подходе, аргументы преобразуются в массив который затем используется для индексирования кэша. Каждая функция имеет встроенный в объект метод с именем «arguments», он содержит переданные аргументы. «Аrguments» — объект подобный масивам, в отличии от масивов он не может быть использован для индекса кэша. Таким образом, он должен быть сначала преобразован в фактический массив с помощью метода slice().
В следующем примере показано как это сделать. Обратите внимание, что дополнительная переменная, «slice», определяется как ссылка на массив метода slice(). Сохраняя эту ссылку можно избежать накладных расходов многократно вычисления Array.prototype.slice(). Метод call() используется чтобы применить slice() для «arguments».
var fibonacci = (function() {
var memo = {};
var slice = Array.prototype.slice;
function f(x, n) {
var args = slice.call(arguments);
var value;
if (args in memo) {
value = memo[args];
} else {
if (n === 0 || n === 1)
value = n;
else
value = f(x, n - 1) + f(x, n - 2);
memo[arguments] = value;
}
return value;
}
return f;
})();
Аргументы кэширования объектов
Эта схема мемоизации не обрабатывает аргументы объектов хорошо. Чтоб объекты использовать в качестве индекса их преобразовывают в строковое представление «[object Object]». Это приводит к неправильному отображению многомерного масива. Такое поведение может быть исправлено путем выполнения stringification для объекта аргументов перед индексацией. К сожалению, это также замедляет процесс запоминания. Следующий пример создает общую memoized функцию, которая принимает объект в качестве параметра. Обратите внимание, что объект аргументов превращается в строку с помощью JSON.stringify().
var foo = (function() {
var memo = {};
function f(obj) {
var index = JSON.stringify(obj);
if (index in memo) {
return memo[index];
} else {
// memoized function contents
return (memo[index] = function_value);
}
}
return f;
})();
Автоматическая мемоизация
Во всех предыдущих примерах функции были явно модифицированы чтобы добавить запоминание. Кроме того, можно осуществить запоминание значений не изменяя функции вообще. Таким образом можно разделить логику функции и запоминания. Это делается путем создания функции запоминания, которая принимает функцию в качестве аргумента, значения которой нужно запомнить. На примере функция memoize() принимает функцию «func» в качестве входных данных. Далее memoize() возвращает новую функцию, которая оборачивает механизм кэширования вокруг «func». Обратите внимание, что эта функция не обрабатывает аргументы объекта. Для обработки объектов существует цикл, который будет проверять каждый аргумент.
function memoize(func) {
var memo = {};
var slice = Array.prototype.slice;
return function() {
var args = slice.call(arguments);
if (args in memo)
return memo[args];
else
return (memo[args] = func.apply(this, args));
}
}
Ограничения
Есть несколько вещей, которые вы должны иметь в виду при реализации запоминания. Во-первых, за счет сохранения старых результатов, функция memoized потребует дополнительную память. В примере Фибоначчи, дополнительное потребление памяти не ограничено. Если использование памяти является проблемой, то кэш должен иметь фиксированный размер. Накладные расходы, связанные с запоминанием, могут также сделать его непрактичным для функций которые нужно выполнять быстро или нечасто.
Самое большое ограничение мемоизации является то, что оно может быть автоматизировано только с функциями референциально-прозрачными. Функция считается референциально-прозрачной если её результат зависит только от её входных данных и она не вызывает никаких побочных эффектов. Функция Фибоначчи референциально-прозрачна поскольку её результат зависит исключительно от величины «n». В следующем примере, функция foo() не референциально-прозрачна поскольку она использует глобальную переменную «bar». Так как «bar» может быть изменен вне foo() нет никакой гарантии, что возвращаемое значение останется тем же самым для каждого входного значения. В этом примере два вызова foo() возвращают значения двух и трех, хотя одни и те же аргументы передаются в обоих случаях.
var bar = 1;
function foo(baz) {
return baz + bar;
}
foo(1);
bar++;
foo(1);
Выводы
- Мемоизация может повысить производительность за счет кэширования результатов предыдущих вызовов функций.
- Memoized функция используется для хранения кэша, который индексируется входными параметрами функции. Если нужные аргументы в кэше — кэшированное значение возвращается. В противном случае функция выполняется и вновь вычисленное значение добавляется в кэш.
- Объект arguments должен быть строкой перед использованием в качестве индекса.
- Мемоизация может автоматизирована при работе с референциально-прозрачными функциями.
Источник: Sitepoint