DEV Community

Jeremy Marx
Jeremy Marx

Posted on • Updated on

Create a memoized function in JavaScript

One of the first software development courses I ever took involved recreating the well known JavaScript library Underscore.js from scratch.
Implementing more basic ones like each or map were manageable for me, but when we reached the more advanced ones, I was unable to keep up. One of the functions that really gave me a lot of trouble was memoize. I figuratively banged my head up against the wall with this function for countless hours until one of my peers had to just show me how to do it. I was definitely overthinking it, and even after my peer explained how it worked, I didn't fully understand it.
After encountering the memoization concept while learning React and researching more algorithmic functions, I revisited the memoize function and feel like I understand the concept and implementation.

What is memoize and when should you use it?

According to the Underscore documentation, it

Memoizes a given function by caching the computed result. Useful for speeding up slow-running computations.

Memoize takes a function as an argument, which is the function we are going to memoize. Memoize returns a function, which takes in an unspecified amount of arguments. When the memoized function (the function originally passed into memoize) is called, memoize checks if the function has already been called with that particular set of arguments. If so, memoize will already have the result of that computation stored in its cache. So it will look it up and return the already computed result. If the memoized function has not yet been called with a particular set of arguments, then memoize will perform the computation, store the result in its cache, and return the result.
Why use it? Say you have a function that is really "expensive" that you will be using frequently in your program. Instead of calling it over and over, with memoize, you can save the result of a particular computation. So if the function is called with the same set of arguments more than once, you won't have to repeat the computation.

Caveats and Pre-requisites.

  1. ES6 Syntax. I'm going to use all ES6 Syntax, so all functions will be arrow functions. This has implications about the execution context of the this keyword, in addition to the syntax. I'll also be using the rest parameter as opposed to the arguments object, which will allow us to use JavaScript's built in Array methods more efficiently.
  2. Closures. My favorite definition of a closure is an inner function that has access to an outer function's scoped variables, even after the outer function has returned. This will be key in implementing our memoize function. For additional information, consult the MDN documentation.
  3. Function Methods/Apply. Functions are first class objects in JavaScript. Just like Arrays, they have prototype methods. Apply is used to change the execution context of a function. This will be key for our implementation, since we will be dealing with functions as parameters, returned functions, and using functions in different scopes. For additional information, consult the MDN documentation.
  4. Primitive vs. Complex Data Types. Our example function will only be optimized for primitive data, such as strings or numbers. Complex data is passed by reference and would require us to implement logic that would check for objects being "deeply equal" to each other. For a review on data types in JavaScript, consult the MDN documentation.

Our Memoized Function

Ordinarily, we'd use the memoization technique for far more complex functions, but for this example we are going to use a simple adding function that takes in an unspecified amount of numbers and adds them all together.

const add = (...args) => {
  return args.reduce((s, e) => {
    return s += e;
  }, 0);
}
Enter fullscreen mode Exit fullscreen mode

This function uses the rest parameter to collect all the arguments into an array and then uses the Array method reduce to add them all together.

Implementing Memoize

First, memoize takes in the function we want to memoize as a parameter. Then, we need a cache to store our previously computed results. Since we need to look up values, we'll need something with key-value pairs. So we'll go with an object literal.

const memoize = func => {
  const cache = {};
}  
Enter fullscreen mode Exit fullscreen mode

Memoize returns a function that takes in an unspecified amount of arguments.

const memoize = func => {
  const cache = {};
  return (...args) => {
  }
}
Enter fullscreen mode Exit fullscreen mode

We are going to want to look up if the memoized function has been called with a particular set of arguments or have a way to create a key with which we can store the computation in the cache. So let's turn the arguments into a string and store it in a function scoped variable.

const memoize = func => {
  const cache = {};
  return (...args) => {
     let strKey = args.join(',');
  }
}
Enter fullscreen mode Exit fullscreen mode

We use the join method to turn all the numbers into a string we can use for lookup or storage, which is our next step.

const memoize = func => {
  const cache = {};
  return (...args) => {
     let strKey = args.join(',');
     if(!cache[strKey]){
        cache[strKey] = func.apply(this, args);
      } 
       return cache[strKey];
   }
  }
}
Enter fullscreen mode Exit fullscreen mode

In our if statement, we check if the memoized function has not been called/isn't present in the cache. If that is the case, we store it in the cache using the Function prototype method apply to call the memoized function in its new scope. Remember, even though we will already be working within the global scope after the outer function is returned, we still have access to the cache because of closures.
After we perform the computation and store it, the inner function returns the result from the cache. If the the computation is already stored in the cache, the if block is skipped and the value returned.

Using Memoize

Let's put this all to use and memoize our add function from earlier.

const memoize = func => {
  const cache = {};
  return (...args) => {
  console.log(cache)
     let strKey = args.join(',');
      if(!cache[strKey]){
        console.log('adding to cache!');
        cache[strKey] = func.apply(this, args);
      } 
       console.log('fetching from cache!');
       return cache[strKey];
   }
}

const add = (...args) => {
  return args.reduce((s, e) => {
    return s += e;
  }, 0);
}

const memoizedAddFunction = memoize(add);

memoizedAddFunction(1, 2, 3);
memoizedAddFunction(1, 2, 3);
memoizedAddFunction(4, 2, 3);
memoizedAddFunction(4, 2, 3);
memoizedAddFunction(8, 2, 3);
memoizedAddFunction(1, 2, 3);
memoizedAddFunction(4, 2, 3);
memoizedAddFunction(8, 2, 3);
Enter fullscreen mode Exit fullscreen mode

And there we have it!
I encourage you to run this function in the JavaScript environment of your choice and add some more calls of the memoizedAddFunction with some more/different numbers. I've included some console logs in various places in memoize, so you can see the computations being added or fetched from the cache.
I hope this helps clarify a concept that gave me a lot trouble a few months ago in bootcamp. If you liked the article, please give me a like, share, or comment. If you REALLY liked it, help me out by buying me a cup of coffee!

Top comments (3)

Collapse
 
davwheat profile image
David Wheatley

There is a MAJOR flaw with this design.

If you call memoizedAddFunction(1, 2, 3, 4), you'll get 10 as expected.

If you then decide to call memoizedAddFunction(123, 4), you'll still get 10!

This is because you used .join('') instead of .join(',') or .join(' ').

Ideally, you should use some unique hash of the array items instead of the items themselves, as this would break very badly if you wanted to memoize a function that accepted strings as input.

Collapse
 
jeremydmarx813 profile image
Jeremy Marx

join method now passing in a comma as a separator, so the function should work as planned. Thanks for the great feedback!

Collapse
 
jeremydmarx813 profile image
Jeremy Marx

That is a fair point, I will look in to another way to create the key on the cache.