Книга: JavaScript. Подробное руководство, 6-е издание

8.8.4. Мемоизация

8.8.4. Мемоизация

В разделе 8.4.1 была определена функция нахождения факториала, которая сохраняет ранее вычисленные результаты. В функциональном программировании такого рода кэширование называется мемоизацией (memorization). В следующем примере демонстрируется функция memoize() высшего порядка, которая принимает функцию в виде аргумента и возвращает ее мемоизованную версию:

// Возвращает мемоизованную версию функции f. Работает, только если все возможные
// аргументы f имеют отличающиеся строковые представления,
function memoize(f) {
  var cache = {}; // Кэш значений сохраняется в замыкании,
  return function() {
    // Создать строковую версию массива arguments для использования
    // в качестве ключа кэша.
    var key = arguments.length + Array.prototype.join.call(arguments,",")
    if (key in cache) return cache[key];
    else return cache[key] = f.apply(this, arguments);
  };
}

Функция memoize() создает новый объект для использования в качестве кэша и присваивает его локальной переменной, благодаря чему он остается доступным (через замыкание) только для возвращаемой функции. Возвращаемая функция преобразует свой массив arguments в строку и использует ее как имя свойства объекта-кэша. Если значение присутствует в кэше, оно просто возвращается в качестве результата. В противном случае вызывается оригинальная функция, вычисляющая значение для заданной комбинации значений аргументов; полученное значение помещается в кэш и возвращается. Следующий фрагмент демонстрирует, как можно использовать функцию memoize():
// Возвращает наибольший общий делитель двух целых чисел, используя
// алгоритм Эвклида: http://en.wikipedia.org/wiki/Euclidean_algorithm
function gcd(a.b) { // Проверка типов а и b опущена
  var t; // Временная переменная для обмена
  if (а < b) t=b, b=a, a=t; // Убедиться, что а >= b
  while(b ! = 0) t=b, b = a%b, a=t; // Это алгоритм Эвклида поиска НОД
  return а;
}
var gcdmemo = memoize(gcd);
gcdmemo(85, 187) // => 17
// Обратите внимание, что при мемоизации рекурсивных функций желательно,
// чтобы рекурсия выполнялась в мемоизованной версии, а не в оригинале,
var factorial = memoize(function(n) {
  return (n <= 1) ? 1 : n * factorial(n-1);
});
factorial(5) // => 120. Также поместит в кэш факториалы для чисел 4, 3, 2 и 1.

Оглавление книги