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

Функции могут использовать объекты для запоминания результатов предыдущих операций, что позволяет избежать ненужной работы. Эта оптимизация называется запоминание. Объекты и массивы JavaScript очень удобны для этого.

Давайте разберемся в этом, написав программу для вычисления чисел Фибоначчи.

var fibonacci = function (n) {
    return n < 2 ? n : fibonacci(n − 1) + fibonacci(n − 2);
};

for (var i = 0; i <= 10; i += 1) {
    console.log('// ' + i + ': ' + fibonacci(i));
}

В приведенном выше сценарии вычисление числа Фибоначчи не оптимизировано, поскольку функция Фибоначчи выполняется больше требуемого количества раз.

Он вызывается нами 11 раз внутри цикла for и каждый раз сам по себе возвращает значения, которые, вероятно, уже были недавно вычислены.

Мы сохраним наши запомненные результаты в массиве memo, который мы можем скрыть в замыкании. Когда наша функция вызывается, она сначала проверяет, известен ли ей результат. Если да, то она может немедленно вернуть его:

var fibonacci = (function (  ) {
    var memo = [0, 1];
    var fib = function (n) {
        var result = memo[n];
        if (typeof result !== 'number') {
            result = fib(n − 1) + fib(n − 2);
            memo[n] = result;
        }
        return result;
    };
    return fib;
}( ));

В этом случае функции будут вызываться сами по себе только 29 раз, а цикл for — 11 раз. Давайте рассмотрим еще один простой пример мемоизации:

// a simple function to add something
let addNum = (n) => (n + 1);
addNum(10);
// a simple memoized function to add something
let cachedAddNum = () => {
  let cache = {};
  return (n) => {
    if (n in cache) {
      console.log('Fetching from cache');
      return cache[n];
    }
    else {
      console.log('Calculating result');
      let result = n + 10;
      cache[n] = result;
      return result;
    }
  }
}
// returned function from memoizedAdd
const add = cachedAddNum();
console.log(add(10)); // calculated
console.log(add(10)); // cached

Примечание. Запоминать можно только чистую функцию.

Чистая функция – это та, которая

Возвращает один и тот же вывод для одного и того же ввода каждый раз.
Не зависит и не изменяет состояние переменных за пределами своей области.

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

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

Примечание. Запоминать можно только чистую функцию.

Вопросы по теме