Мемоизация в JavaScript

Иногда наши рекурсивные или часто вызываемые функции очень сильно «тормозят» выполнение программы, потому что результаты промежуточных вычислений нигде не сохраняются, а вычисляются заново. Решить проблему может мемоизация.

Из википедии:

Мемоизация — сохранение результатов выполнения функций для предотвращения повторных вычислений. Это один из способов оптимизации, применяемый для увеличения скорости выполнения компьютерных программ. Перед вызовом функции проверяется, вызывалась ли функция ранее: если не вызывалась, функция вызывается и результат её выполнения сохраняется; если вызывалась, используется сохранённый результат.

Классическим примером для иллюстрации является функция, вычисляющая последовательность чисел Фибоначчи:

function fibonacci(n) {
  if (n === 0 || n === 1)
    return n;
  else
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Для больших чисел n количество вызовов функции растёт очень быстро. Уже для n=50 это порядка 40 миллиардов вызовов.

Используя идею мемоизации, то есть кеширования промежуточного результата, можно добиться уменьшения количества вызовов для n=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;
})();

Если функция имеет дело с несколькими аргументами, то нужно хранить в кеше их все. Вместо того,  чтобы каждый раз писать «мемоизированную» версию функции, можно использовать функцию-обёртку вроде такой:

function memoized (fn, keymaker) {
   var lookupTable = {},
   key;
   keymaker || (keymaker = function (args) {
      return JSON.stringify(args)
   });
   return function () {
      var key = keymaker.call(this, arguments);
      return lookupTable[key] || (
         lookupTable[key] = fn.apply(this, arguments)
      )
   }
}

Используется она очень просто:

var memoizedFibonacci = memoized( function (n) {
  if (n === 0 || n === 1)
    return n;
  else
    return memoizedFibonacci (n - 1) + memoizedFibonacci (n - 2);
});

memoizedFibonacci (50);

Мемоизация полезна, когда вы передаёте в функцию заранее известный набор аргументов и когда результат функции будет всегда одинаковым при одинаковых аргументах. Если же функция не даёт одинакового результата при тех же аргументах, то мемоизация будет бесполезна.

Код большинства примеров взят из статьи   Implementing Memoization in Javascript