I made a video version of this post! Check it out on YouTube if you prefer consuming your tutorial content that way.

Introduction

Memoization is an optimization technique used in many programming languages to reduce the number of redundant, expensive function calls. This is done by caching the return value of a function based on its inputs. In this post, we’ll create a suboptimal, but hopefully educationally-informative, JavaScript function memoizer!

First, an Expensive Function to Memoize

Here’s a function for us to memoize. It finds the square of a number in a very inefficient way.

const inefficientSquare = (num) => {
  let total = 0;
  for (let i = 0; i < num; i++) {
    for (let j = 0; j < num; j++) {
      total++;
    }
  }
  return total;
};

We can run this function with the same value and, each time, it’ll take a while to execute.

const start = new Date();
inefficientSquare(40000);
console.log(new Date() - start);
// 1278

const start2 = new Date();
inefficientSquare(40000);
console.log(new Date() - start2);
// 1245

Over one second each time, yikes!

Writing Pseudocode for our Memoizer

Let’s reason through our memoizer before we write any code.

• Takes a reference to a function as an input
• Returns a function (so it can be used as it normally would be)
• Creates a cache of some sort to hold the results of previous function calls
• Any future time calling the function, returns a cached result if it exists
• If the cached value doesn’t exist, calls the function and store that result in the cache

Real Code Time

Here’s an implementation of the above pseudocode outline. As mentioned in the introduction, this is suboptimal and you should not use this in production. I’ll explain why after!

// Takes a reference to a function
const memoize = (func) => {
  // Creates a cache of results
  const results = {};
  // Returns a function
  return (...args) => {
    // Create a key for results cache
    const argsKey = JSON.stringify(args);
    // Only execute func if no cached value
    if (!results[argsKey]) {
      // Store function call result in cache
      results[argsKey] = func(...args);
    }
    // Return cached value
    return results[argsKey];
  };
};

The most suboptimal part of this implementation, and why I wouldn’t recommend it be used in production code, is using JSON.stringify to create keys in our results cache. The biggest problem with JSON.stringify is that it doesn’t serialize certain inputs, like functions and Symbols (and anything you wouldn’t find in JSON).

Testing Our Memoizer on an Expensive Function

Let’s replicate our inefficientSquare example, but this time we’ll use our memoizer to cache results.

const memoize = (func) => {
  const results = {};
  return (...args) => {
    const argsKey = JSON.stringify(args);
    if (!results[argsKey]) {
      results[argsKey] = func(...args);
    }
    return results[argsKey];
  };
};

const inefficientSquare = memoize((num) => {
  let total = 0;
  for (let i = 0; i < num; i++) {
    for (let j = 0; j < num; j++) {
      total++;
    }
  }
  return total;
});

const start = new Date();
inefficientSquare(40000);
console.log(new Date() - start);
// 1251

const start2 = new Date();
inefficientSquare(40000);
console.log(new Date() - start2);
// 0

Success! The second time we call inefficientSquare with the same input it takes no time to recompute; we’re simply pulling the cached value from an object.

Only Memoize Pure Functions!

Memoization is great, but it only works if your function is pure. In other words, if your function’s returned value is dependent on more than its inputs, then your cached value for those inputs won’t always be correct. Also, if your function has side-effects, the memoizer doesn’t replicate those, it simply returns the ultimately-returned function value.

Conclusions

You should now have a good idea of how and why we use memoization! While our memoization function was suboptimal, there are plenty of third party libraries out there you can use that will do a much better. Just make sure the functions you’re memoizing are pure!