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.