Memoization

Memoization

Memoization is an optimization technique that consists of caching (storing) the result of a function for given arguments, so that if it is called again with the same arguments it is not recomputed: the stored value is returned. It is a particular case of caching applied to pure functions (those that always return the same thing for the same input).

The idea with a Map and a closure

We store the results in a Map that lives in a closure, private to the cached function:

function memoize(fn) {
  const cache = new Map();
  return function (n) {
    if (cache.has(n)) {
      return cache.get(n); // cache hit!
    }
    const result = fn(n);
    cache.set(n, result);
    return result;
  };
}

The classic case: Fibonacci

The naive recursive Fibonacci is O(2ⁿ) because it recomputes the same values over and over. With memoization it becomes linear, O(n):

function fibonacci(n) {
  if (n < 2) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}
const fastFib = memoize(function (n) {
  if (n < 2) return n;
  return fastFib(n - 1) + fastFib(n - 2);
});

console.log(fastFib(40)); // instant; the naive one would take ages

Memoizing has a cost in memory: you are trading time for space. Use it when recomputations are expensive and the arguments repeat.

Examples

Count how many times it actually runs

function memoize(fn) {
  const cache = new Map();
  return function (n) {
    if (cache.has(n)) return cache.get(n);
    const r = fn(n);
    cache.set(n, r);
    return r;
  };
}
let calls = 0;
const square = memoize((n) => { calls++; return n * n; });
console.log(square(5));
console.log(square(5));
console.log(square(5));
console.log("Real computations:", calls); // 1, thanks to the cache