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

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

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

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

function fib(n) {
  if (n <= 1) {
    return n;
  }
    return fib(n - 1) + fib(n - 2);
 }

Эта функция работает путем рекурсивного вызова самой себя с различными значениями для n. При первом вызове она вычислит числа Фибоначчи для n = 0 и n = 1. При втором вызове он вычислит числа Фибоначчи для n = 1 и n = 2. И так далее.

При каждом вызове функции она должна заново вычислить числа Фибоначчи для n - 1 и n - 2. Однако многие из этих значений уже были вычислены в предыдущих вызовах функции. Например, при вычислении числа Фибоначчи для n = 5 функция должна вычислить значения для n = 3 и n = 4, хотя они уже были вычислены при вычислении n = 4.

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

Мы можем мемоизировать функцию fib, добавив кэш в качестве глобальной переменной:

var cache = {};

function fib(n) {
   if (n <= 1) {
     return n;
   }

   if (!(n in cache)) {
     cache[n] = fib(n - 1) + fib(n - 2);
   }

  return cache[n];
}

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

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

Среди других распространенных случаев использования мемоизации — кэширование результатов запросов к базе данных, вызовов API и вычислительно дорогих функций.

Одним из потенциальных недостатков мемоизации является то, что она может занимать много памяти, если функция вызывается с большим количеством различных входных данных. В нашем примере с Фибоначчи кэш потенциально может вырасти и содержать результаты каждого вычисления Фибоначчи от 0 до n. При очень больших значениях n это может занять значительный объем памяти.

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

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

Другой пример мемоизации — использование закрытия для создания кэша, доступного для мемоизируемой функции:

var memoize = function(fn) {
  var cache = {};

  return function(x) {

    if (cache[x] === undefined) {
      cache[x] = fn(x);
     }

    return cache[x];
   };
};

Эта реализация может быть использована для мемоизации любой функции, если она принимает только один аргумент. Чтобы использовать ее, просто оберните функцию, которая будет мемоизироваться, вызовом memoize:

var factorial = memoize(function(n) {
  if (n === 0) {
   return 1;
   }
   return n * factorial(n - 1);
});

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

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

Более эффективной реализации мемоизации можно добиться, используя объект в качестве кэша и применяя метод Function.prototype.apply для вызова мемоизированной функции с переданными аргументами:

var memoize = function(fn) {
  var cache = {};

 return function() {
     var key = JSON.stringify(arguments);

     if (cache[key] === undefined) {
        cache[key] = fn.apply(this, arguments);
     }

         return cache[key];
        };
};

Эта реализация может быть использована для мемоизации любой функции, независимо от того, сколько аргументов она принимает. Чтобы использовать ее, просто оберните функцию, которую нужно мемоизировать, вызовом memoize:

var factorial = memoize(function(n) {
  if (n === 0) {
   return 1;
   }
   return n * factorial(n - 1);
});

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

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

Последним способом реализации мемоизации в JavaScript является использование структуры данных Map:

var memoize = function(fn) {

var cache = new Map();

return function(x) {
    if (!cache.has(x)) {
                cache.set(x, fn(x));
        }

    return cache.get(x);
  };
};

Заключение

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