Introduction to Memoization in JavaScript with Examples

Photo by Markus Spiske

During my first on-site coding interview I encountered a concept I had never seen before. I don’t remember the question word-for-word but it went something along the lines of:

Create a memoize function that remembers previous inputs and stores them in cache so that it won’t have to compute the same inputs more than once. The function will take an unspecified number of integer inputs and a reducer method. Refer to:

//Given reducer method: 
function add(a,b){
 return a+b
}
//Create a method called memoize such that: 
const memoizeAdd = memoize(add);
//then calling…
memoizeAdd(100,100); //returns 200
memoizeAdd(100); //returns 100
memoizeAdd(100,200) //returns 300
memoizeAdd(100,100) //returns 200 without computing

So here I am thinking… sh*t. I’ve never had to use caching before, how the heck am I going to answer this question!? Then I remembered that I’ve heard the term memoization and even USED it in my most recent React Native project. If I recall correctly, I was experiencing performance issues, searched up some possible solutions on StackOverflow, and found React.memo to be a valid solution. Still, I must’ve subconsciously overlooked the part about how memoization actually works.

Thankfully this was a VC interview so I took a few seconds to look up on google, “what the heck is a memoize function?” (well… something like that). I found the example code found below and used it as a reference to help answer the rest of the question.

// 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

First, let’s understand what memoization does. Then we’ll go over the example code shown above. Finally, we’ll check out how it helped solve the aforementioned interview question.

What memoization does

Here’s a brief and accurate explanation I found on function memoization:

“Memoization is an optimization technique where expensive function calls are cached such that the result can be immediately returned the next time the function is called with the same arguments”. — Jonathan Lehman, JavaScript Function Memoization

Note: Browser cache need not be applied in this scenario.

I might elaborate by saying something like: memoization helps speed up function calls by storing previously computed results in a JavaScript object, aka cache. In other words, every time our memoize method is executed, one of two things can occur:

1. If the input has been used before, locate it in cache and immediately return the value stored without executing any further computations.
2. Use the input to execute any necessary computations, store the results in cache, return the result.

A simple memoization example

Let’s build a simple memoize function, similar to the one shown above, in order to demonstrate.

First let’s define our function using ES6. As a parameter, it will accept a function, fn, to be used for computations.

const memoize = (fn) => {}

Next let’s declare an initial cache object.

const memoize = (fn) => {
   let cache = {}
}

Great. Now let’s actually return something. We will first implement possibility #1 — “If the input has been used before, locate it in cache and immediately return the value stored without executing any further computations.”

const memoize = (fn) => {
   let cache = {}
   return (n) => {
      if (n in cache){
         return cache[n]
      }
}

Let’s review. First of all, memoize has officially become a higher-order-function because it takes a function as input and/or returns a function as output. To elaborate further, if we call memoize, we’ll get another function that checks if a given parameter, n, is a key in cache and will return its corresponding value. What’s so special about this? Well it’s the fact that the returned function has cache in its scope where it can access or add properties! Moving forward, this can prove to be very powerful.

For right now, the cache object will remain empty so let’s implement rule #2 in order to change that — “Use the input to execute any necessary computations, store the results in cache, return the result.”

const memoize = (fn) => {
   let cache = {}
   return (n) => {
      if (n in cache){
         return cache[n]
      }else{
         let result = fn(n);
         cache[n] = result;
         return result;
      }
   }
}

Awesome! Now, if parameter n has not been stored in cache, memoize will execute computation fn(n), and the result will be stored in cache as so:

/* Given n=5 and result=15, cache will contain the 
key:value pair of: */
"5" : 15

Let’s see it in action.

First, given a function add10

const add10 = (n) => n + 10

We can declare memoizeAdd10 like

const memoizeAdd10 = memoize(add10);

Using, memoizeAdd10, we might make the following function calls

memoizeAdd10(15); //returns 25
memoizeAdd10(20); //returns 30
memoizeAdd10(25); //returns 35

After these calls, memoizeAdd10 ‘s cache will look like this:

{
   "15" : 25,
   "20" : 30,
   "25" : 35
}

And if we call something like

memoizeAdd10(15); //returns 25 without arithmetic computations

another time — instead of computing the result, memoizeAdd10 will just dive into cache, find the key “15” and return 25 without having to execute any computations. You might be thinking, “but this is just an add function that barely puts any strain on our machine, who cares?” Well sure but when algorithms grow from simple adding to recursive operations, for example, memoization can prove to be a huge advantage.

Solving our interview question

Let’s apply what we’ve learned thus far in order to solve our interview question mentioned at the beginning of the article. We can use the same memoize function defined above, except with a few tweaks:

In this example, we changed about 3 things. Let’s go over them:

1. “n” ➡️ “…args” (line3) — the return function now accepts an unspecified number of parameters which can be accessed by using the array args or the arguments object.
2. “cacheKey” (lines 4, 5, 6, 9) — we declared a variable called “cacheKey” which represents the name of the key (previously “n”) that will be used to either access the cache or declare a new cache property. This change is made in order to keep track of multiple inputs. We form cacheKey by mapping over the “args” array and returning a string of “n” and a “+”. For example, when calling memoizeAdd(10, 20, 30) the cacheKey will be “10+20+30+”.
3. “fn(n)” ➡️ “args.reduce((acc, curr) => fn(acc, curr), 0)” — due to the fact that memoizeAdd can accept any unspecified number of parameters, in order to find the sum of all parameters we can use Array.prototype.reduce.

Using our newly refurbished memoize function, after making the following function calls

memoizeAdd(10, 20, 30, 40); //returns 100
memoizeAdd(1, 2, 3, 4); //returns 10
memoizeAdd(5, 10) //returns 15

our cache will look something like:

{
   "10+20+30+40+" : 100,
   "1+2+3+4+" : 10,
   "5+10+" : 15
}

Then if we call again:

memoizeAdd(1, 2, 3, 4); //returns 10 without arithmetic computations

Our function memoizeAdd will return 10 without the need for arithmetic operations. In the end and with more sophisticated functions “fn” this technique proves to be extremely useful. However, it’s important to keep in mind when and when not to use it.

Conclusion

We have just displayed the power of function memoization in JavaScript. I hope you enjoyed reading and will consider using this method in your next project! Thanks!