Understanding JavaScript/TypeScript Memoization

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

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

What Is a Pure Function?

Memoization can only be done in pure functions. A pure function must meet 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 that use random numbers.
  • Functions that use DateTime 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 due for several reasons:

• Code is more declarative. Also, pure functions focus on how different inputs are related to outputs.
• Code is more easily tested, and finding bugs is easier when compared to impure functions.

Pure Functions Example

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

The imperative version of the function factorial is pure too. In both cases, when the input is the same, the output will be the same.

Another interesting example of pure functions are the following:

Memoization in Recursive Functions

Memoization is a programming technique that allows the output of a pure function to be stored in cache, so the same function call does not need to be computed again. For example, 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), execution may take a while the first time, but the second time, runtime will be reduced.

Memoization Example

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

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

So, a basic implementation of memoizing a decorator in JavaScript is shown below:

1. We define the cache in which the execution’s result will be stored. We use a map to store these results.
2. The decorator returns a new function that has the same behavior as the original function, but memoization is implemented.
3. The key of the key-value map is generated using stringify and args from the original function.
4. The execution of the original function (fn(...args)) decides whether there is a store in the cache.
5. The value is stored in the cache (whether there is pre-calculated previously).
6. The result is returned.

How to Use the Memoized Decorator

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

In this case, the add function is the original function without memoization, and the addMemoized function is a new function that implements memoization using the decorator pattern.

Demo Using Memoization

Now, I’m going to show you a real demo using memoization. Imagine a horribly programmed algorithm that indicates if an array has a unique value (as the Array.prototype.some).

The following step runs the original code and the memoized code to compare the time used in each function. It is very important to remember that the original code is not modified, except for the addition of memoization.

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

The arrays are generated at the beginning of the script:

Finally, when the user clicks a button, the functions are executed.

1. No Memoization

2. Memoization

The result is shown in the following animation: