NTH Blog

Functions are an integral part of programming. They help add modularity and reusability to our code.

It’s quite common to divide our program into chunks using functions which we can call later to perform some useful action.

Sometimes, a function can become expensive to call multiple times (say, a function to calculate the factorial of a number). But there’s a way we can optimize such functions and make them execute much faster: caching.

For example, let’s say we have a function to return the factorial of a number:

function factorial(n) {
  // Calculations: n * (n-1) * (n-2) * ... (2) * (1)
  return factorial;
}

Great, now let’s find factorial(50). The computer will perform calculations and return us the final answer, sweet!

When that’s done, let’s find factorial(51). The computer again performs a number of calculations and gets us the result, but you might have noticed that we’re already repeating a number of steps that could have been avoided. An optimized way would be:

factorial(51) = factorial(50) * 51

But our function performs the calculations from scratch every time it’s called:

factorial(51) = 51 * 50 * 49 * ... * 2 * 1

Wouldn’t it be cool if somehow our factorial function could remember the values from its previous calculations and use them to speed up the execution?

In comes memoization, a way for our function to remember (cache) the results. Now that you’ve a basic understanding of what we’re trying to achieve, here’s a formal definition:

Memoization is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again

Memoizing in simple terms means memorizing or storing in memory. A memoized function is usually faster because if the function is called subsequently with the previous value(s), then instead of executing the function, we would be fetching the result from the cache.

Here’s what a simple memoized function might look like (and here’s a CodePen in case you want to interact with it):

// a simple function to add something
const add = (n) => n + 10;
add(9);

// a simple memoized function to add something
const memoizedAdd = () => {
  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 newAdd = memoizedAdd();
console.log(newAdd(9)); // calculated
console.log(newAdd(9)); // cached

Memoization takeaways

Some takeaways from the above code are:

memoizedAdd returns a function which is invoked later. This is possible because in JavaScript, functions are first class objects which lets us use them as higher order functions and return another function.
cache can remember its values since the returned function has a closure over it.
It’s essential that the memoized function is pure. A pure function will return the same output for a particular input no mater how many times it’s called, which makes the cache work as expected.

Writing your own `memoize` function

The previous code works fine but what if we wanted to turn any function into a memoized function?

Here’s how to write your own memoize function (codepen):

// a simple pure function to get a value adding 10
const add = (n) => n + 10;
console.log('Simple call', add(3));

// a simple memoize function that takes in a function
// and returns a memoized function
const memoize = (fn) => {
  let cache = {};
  return (...args) => {
    let n = args[0]; // just taking one argument here
    if (n in cache) {
      console.log('Fetching from cache');
      return cache[n];
    } else {
      console.log('Calculating result');
      let result = fn(n);
      cache[n] = result;
      return result;
    }
  };
};

// creating a memoized function for the 'add' pure function
const memoizedAdd = memoize(add);
console.log(memoizedAdd(3)); // calculated
console.log(memoizedAdd(3)); // cached
console.log(memoizedAdd(4)); // calculated
console.log(memoizedAdd(4)); // cached

Now that’s great! This simple memoize function will wrap any simple function into a memoized equivalent. The code works fine for simple functions and it can be easily tweaked to handle any number of arguments as per your needs. Another alternative is to make use of some de-facto libraries such as:

Lodash’s _.memoize(func, [resolver])
ES7 @memoize decorators from decko

Memoizing recursive functions

If you try passing in a recursive function to the memoize function above or _.memoize from Lodash, the results won’t be as expected since the recursive function on its subsequent calls will end up calling itself instead of the memoized function thereby making no use of the cache.

Just make sure that your recursive function is calling the memoized function. Here’s how you can tweak a textbook factorial example (codepen):

// same memoize function from before
const memoize = (fn) => {
  let cache = {};
  return (...args) => {
    let n = args[0];
    if (n in cache) {
      console.log('Fetching from cache', n);
      return cache[n];
    } else {
      console.log('Calculating result', n);
      let result = fn(n);
      cache[n] = result;
      return result;
    }
  };
};

const factorial = memoize((x) => {
  if (x === 0) {
    return 1;
  } else {
    return x * factorial(x - 1);
  }
});

console.log(factorial(5)); // calculated
console.log(factorial(6)); // calculated for 6 and cached for 5

A few points to note from this code:

The factorial function is recursively calling a memoized version of itself.
The memoized function is caching the values of previous factorials which significantly improves calculations since they can be reused factorial(6) = 6 * factorial(5)

Is memoization same as caching?

Yes, kind of. Memoization is actually a specific type of caching. While caching can refer in general to any storing technique (like HTTP caching) for future use, memoizing specifically involves caching the return values of a function.

When to memoize your functions

Although it might look like memoization can be used with all functions, it actually has limited use cases:

In order to memoize a function, it should be pure so that return values are the same for same inputs every time
Memoizing is a trade-off between added space and added speed and thus only significant for functions having a limited input range so that cached values can be made use of more frequently
It might look like you should memoize your API calls however it isn’t necessary because the browser automatically caches them for you. See HTTP caching for more detail
The best use case I found for memoized functions is for heavy computational functions which can significantly improve performance (factorial and fibonacci are not really good real world examples)
If you’re into React/Redux you can check out reselect which uses a memoized selector to ensure that calculations only happen when a change happens in a related part of the state tree.

How to use Memoize to cache JavaScript function results and speed up your code

Memoization takeaways

Writing your own `memoize` function

Memoizing recursive functions

Is memoization same as caching?

When to memoize your functions

Further reading

How to use Memoize to cache JavaScript function results and speed up your code

Memoization takeaways

Writing your own memoize function

Memoizing recursive functions

Is memoization same as caching?

When to memoize your functions

Further reading

Writing your own `memoize` function