Программы часто тратят время на вызов функций, которые снова и снова пересчитывают одни и те же результаты. Это особенно верно для рекурсивных и математических функций. Прекрасным примером этого является генератор чисел Фибоначчи . Последовательность Фибоначчи — это серия целых чисел, начинающихся с нуля и единицы, в которой каждое значение является суммой двух предыдущих чисел в серии. Исходя из этого определения, первые десять чисел Фибоначчи: 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 ведут себя как ассоциативные массивы, они являются идеальными кандидатами на роль кэшей. Каждый раз, когда вызывается запомненная функция, ее параметры используются для индексации кэша. Если данные присутствуют, то они могут быть возвращены без выполнения всей функции. Однако если данные не кэшируются, то функция выполняется, и результат добавляется в кэш.
В следующем примере оригинальная функция Фибоначчи переписана, чтобы включить памятку. В этом примере самоисполняющаяся анонимная функция возвращает внутреннюю функцию f (), которая используется в качестве функции Фибоначчи. Когда возвращается функция f (), его закрытие позволяет ему продолжать доступ к объекту «memo», в котором хранятся все его предыдущие результаты. Каждый раз, когда выполняется f (), он сначала проверяет, существует ли результат для текущего значения «n». Если это так, то кэшированное значение возвращается. В противном случае выполняется исходный код Фибоначчи. Обратите внимание, что «memo» определяется за пределами функции f (), поэтому он может сохранять свое значение при нескольких вызовах функций. Напомним, что исходная рекурсивная функция была вызвана более 40 миллиардов раз для вычисления 50- го числа Фибоначчи. Благодаря внедрению запоминания это число снижается до 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;
})();
Обработка нескольких аргументов
В предыдущем примере функция принимала единственный аргумент. Это сделало реализацию кеша довольно тривиальной. К сожалению, большинство функций требуют нескольких аргументов, что усложняет индексацию кеша. Чтобы запоминать функцию с несколькими аргументами, либо кэш должен стать многомерным, либо все аргументы должны быть объединены в один индекс.
В многомерном подходе кэш становится иерархией объектов вместо одного объекта. Каждое измерение затем индексируется одним параметром. В следующем примере реализован многомерный кеш для функции Фибоначчи. В этом примере функция принимает дополнительный аргумент «x», который ничего не делает. Каждый раз, когда вызывается функция, код проверяет, существует ли измерение «x», и инициализирует его, если он не существует. С этого момента измерение «x» используется для кэширования значений «n». В результате функция вызывает fibonacci («foo», 3), а fibonacci («bar», 3) не рассматривается как один и тот же результат.
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 », который содержит аргументы, которые были переданы. «Arguments» — это тип объекта, известный как объект типа Array . Он похож на массив, но не может использоваться для индексации кэша. Следовательно, он должен быть сначала преобразован в фактический массив. Это можно сделать с помощью метода array slice (). Представление массива может затем использоваться для индексации кэша, как показано ранее. В следующем примере показано, как это сделать. Обратите внимание, что дополнительная переменная, «slice», определяется как ссылка на метод array slice (). Сохраняя эту ссылку, можно избежать издержек многократного вычисления Array.prototype.slice (). Метод call () затем используется для применения slice () к «аргументам».
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;
})();
Аргументы кеширующих объектов
Представленная здесь схема запоминания плохо обрабатывает аргументы объекта. Когда объекты используются в качестве индекса, они сначала преобразуются в строковое представление, такое как «[объект объекта]». Это приводит к тому, что несколько объектов неправильно отображаются в одно и то же место в кэше. Это поведение может быть исправлено путем выполнения строкового преобразования аргументов объекта перед индексацией. К сожалению, это также замедляет процесс запоминания. В следующем примере создается общая запоминаемая функция, которая принимает объект в качестве параметра. Обратите внимание, что аргумент объекта строковый с использованием 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));
}
}
Ограничения
Есть несколько вещей, которые следует иметь в виду при реализации запоминания. Во-первых, при сохранении старых результатов запомненные функции потребляют дополнительную память. В примере Фибоначчи дополнительное потребление памяти не ограничено. Если использование памяти является проблемой, то следует использовать кэш фиксированного размера. Издержки, связанные с запоминанием, также могут сделать его непрактичным для функций, которые выполняются быстро или выполняются нечасто.
Самым большим ограничением запоминания является то, что оно может быть автоматизировано только с помощью функций, которые являются прозрачными . Функция считается ссылочно прозрачной, если ее выход зависит только от ее входных данных и не вызывает побочных эффектов. Вызов ссылочно-прозрачной функции может быть заменен ее возвращаемым значением без изменения семантики программы. Функция Фибоначчи ссылочно прозрачна, потому что она зависит исключительно от значения «n». В следующем примере функция foo () не является ссылочно прозрачной, потому что она использует глобальную переменную «bar». Поскольку «bar» может быть изменен вне foo (), нет гарантии, что возвращаемое значение останется тем же для каждого входного значения. В этом примере два вызова функции foo () возвращают значения два и три, даже если одинаковые аргументы передаются обоим вызовам.
var bar = 1;
function foo(baz) {
return baz + bar;
}
foo(1);
bar++;
foo(1);
То, что нужно запомнить
- Запоминание может потенциально повысить производительность, кэшируя результаты предыдущих вызовов функций.
- Мемоизированные функции хранят кеш, который индексируется их входными аргументами. Если аргументы существуют в кеше, возвращается кэшированное значение. В противном случае функция выполняется и вновь вычисленное значение добавляется в кэш.
- Аргументы объекта должны быть приведены в строку перед использованием в качестве индекса.
- Мемоизация может автоматически применяться к ссылочно прозрачным функциям.
- Мемоизация не может быть идеальной для нечасто вызываемых или быстро выполняемых функций.