Caching

Caching is an important algorithmic tool. It can greatly increase calculation speeds; saving computed values for reuse. A Fibonacci sequence algorithm can be reduced from $O(2^N)$ all the way down to $O(N)$, which is an incredible improvement.

Memoization §

Memoization is a very simple caching method. Build your function as normal. Then everytime you compute a step, cache it. For example, to apply memoization to fib:

let fibCache = [];
function fib(num) {
  if (fibCache[n]) return fibCache[n];
  const result = num < 2 ? num : fib(num - 2) + fib(num - 1);
  fibCache[num] = result;
  return result;
}

Every time we compute a new number, we add that to fibCache. This way, if we are computing a very large number, then we won’t have to go down the tree multiple times; just access it from the cache;

Tabulation §

Tabulation is another form of caching. Unlike memoization however, tabulation is bottom-up. Where in memoization we try to compute the largest one, then the second and third, and so on, in tabulation it’s reversed.

Instead, we start from the smallest, and work our way up until we reach our target. For example:

function fib(num) {
  let nums = [0, 1];
  for (let i = 2; i < n; i++) nums[i] = nums[i - 2] + nums[i - 1];
  return nums.at(-1);
}

Which one? §

If not every single value needs to be computed, memoization; in tabulation all the values need to be computed. For example, if you were writing a function to square a number, it wouldn’t make sense to use tabulation. If you requested square(5), there’s no point in calculating square(4), square(3), and so on…

If you do though, tabulation is generally faster to implement, as it uses loops without function overhead. However, memoization is easier to implement, it’s way more straightforward for complex problems.