Understanding JavaScript/TypeScript Memoization

A JavaScript and TypeScript tutorial

Carlos Caballero
Oct 8, 2019 · 6 min read
Image for post
Image for post

What Is Memoization?

The definition of memoization from Wikipedia is the following:

Memoization is a programming technique which allows you to reduce the function’s time cost for space cost. That is, the functions which are memoized gain speed for a higher use of memory space.

The memoization can only be used in pure functions, so the first point to know is that it is a pure function.

In the following animation, you can see the final result of applied memoization in our code.

Image for post
Image for post

What is a pure function?

A pure function is a function that meets the following criteria:

It is a function that always returns the same result when the arguments are the same. For example, the following functions are impure:

  • Functions which use random numbers.
  • Functions which use date time as seed to generate the result.

It is a function that does not produce side-effects in the application:

  • Data mutation or change application state.
  • Network request.
  • Database or file request.
  • Obtaining user input.
  • Querying the DOM.

Benefits

Pure functions are used in web development because of several benefits. Although, pure functions are not only used in web development. Well, the main pure function benefits are:

  1. Your code is more declarative, which is focused on what must be done and not on how to do it. Also, the functions are focused on how different inputs are related to outputs.
  2. The code is more testable, and finding bugs is easier than in impure functions.

But, in real life there are side-effects and it is a good part of the code (for example, when you access the database or communicate with different servers to request information about the system).

So, pure functions are a part of your code and you need to know when you can use a pure function and when you can use memoization in your code.

Pure Functions Example

Recursive functions frequently use pure functions. The most classical recursive problem is the factorial.

Image for post
Image for post

But the imperative version of the function factorial is pure too, because the pure functions are related to inputs and outputs. In both cases, when the input is the same the output will be the same.

Image for post
Image for post

Another interesting example of pure functions is the following:

Image for post
Image for post

Memoization in Recursive Functions

Memoization is the programming technique which allows you to not recalculate the value of the pure function.

I.e., the pure function returns the same value when it has the same inputs. So, the value return can be stored in the system using any cache system (for example a map or array).

So, if you calculate the value of factorial(1) you can store the return value 1 and the same action can be done in each execution. So, when you run the factorial(100), you take a while the first time but the second time and other times after that, the time will be reduced!

In this case, if you note the recursive factorial version, you can note that this version executes the function factorial several times, which can be cached in our system (using memoization), but if you use the imperative factorial version, your performance will be worse.

For this reason, memoization is a good technique to know in declarative languages.

Memoization Example— Live Code

In this section, I’m going to show you how to implement memoization using closure and the decorator pattern using JavaScript.

The decorator pattern allows you to add new features to any object in runtime using composition instead of hierarchy. The pattern goal is to avoid creating a class hierarchy of our features.

A good example to understand this pattern can be found in Addy Osmany’s blog.

So, a basic implementation of the memoize decorator in JavaScript is the following:

Image for post
Image for post
  1. Define the cache in which the execution’s result will be stored. We use an object as map to store this result.
  2. The decorator returns a new function which has the same behavior as the original function but memoization is implemented.
  3. The key of the key-value map is generated using the stringify and args from the original function.
  4. The result of the new function will be:
  • The execution of the original function (fn(...args)), whether there is none stored in the cache.
  • The value stored in the cache (whether it was pre-calculated previously).

5. The result is returned.

How To Use the Memoized Decorator?

The way to use this decorator in JavaScript is very easy:

Image for post
Image for post

In this case, the add function is the original function without memoization and the addMemoized function is the new function which has the new feature (memoization) using the decorator pattern.

A Real Demo Using Memoization

Now, I’m going to show you a real demo using memoization.

Imagine a complex algorithm that indicates to you if an array has a unique value (as the Array.prototype.some) but is horribly programmed.

Image for post
Image for post

The following step is to run the original code and the code using memoization, and compare the time use in each function. It is very important remember that the original code is not modified but the memoization feature is added.

The following function is used to measure the time used in each execution.

Image for post
Image for post

The arrays are generated at the begin of the script:

Image for post
Image for post

And finally, when the user clicks on a button the functions are executed.

  1. No memoization:
Image for post
Image for post

2. Memoization:

Image for post
Image for post

The result is shown in the following animation:

Image for post
Image for post

Conclusion

Memoization has been widely developed in web development using TypeScript or JavaScript. The following list of resources should be the starting point for using them in your projects.

Fast-Memoize use this graph to compare different implementations of memoize:

Image for post
Image for post

More theory:

Better Programming

Advice for programmers.

Thanks to Zack Shapiro

Carlos Caballero

Written by

Hi! My name is Carlos Caballero and I’m PhD. in Computer Science from Málaga, Spain. Teaching developers and degree/master computer science how to be experts!

Better Programming

Advice for programmers.

Carlos Caballero

Written by

Hi! My name is Carlos Caballero and I’m PhD. in Computer Science from Málaga, Spain. Teaching developers and degree/master computer science how to be experts!

Better Programming

Advice for programmers.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store