Originally published at www.carloscaballero.io on February 8, 2019.

What means Memoization?

The definintion of memoization from the wikipedia is the following:

In computing, memoization or memoisation is an optimization technique used
primarily to speed up computer programs by storing the results of expensive
function calls and returning the cached result when the same inputs occur
again.

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

The memoization only can be used in pure functions, so the first point is known
that is a pure function

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

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

The pure functions are being used in the web develop due to several benefits.
Although, the pure functions are not only use in the web develop. Well, the main
pure function’s benefits are:

Your code is more declarative which is focus in what must to do and doest not in how must to do. Also, the functions are focus in how different inputs are related to outputs.
The code is more testability, and find bugs is more easy that in impure functions.

But, in the real life there are side-effects and it is a good part of the code
(for example, when you access to the database or communicate 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 functions and when you can
use memoization in your code.

Pure functions example

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

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

Another interesting examples of pure functions are the following:

Memoization in recursive functions

The memoization is the programming technique which allows doesn’t recalculated
the value of the pure function. I.e, the pure functions returns the same value
when have the same inputs. So, the value return can be store 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 and more times the time will be reduced!

In this case, if you note the recursive factorial version, you can note that
this version execute several times the function factorial which can be cache
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
known technique in declarative languages.

Memoization Example! — Live code!

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

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

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

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

Define the cache in which the execution’s result will be store. We use a object as map to store this results.
The decorator returns a new function which has the same behaviour that original function but memoization is implemented.
The key of the key-value map is generated using the stringify and args from the original function.
The result of the new function will be
The execution of the original function (fn(...args)) whether there is not store in the cache.
The value stored in the cache (whether there is pre-calculated previously).
The result is returned.

How to used our `memoized` decorator ?

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

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 deam using memoization. Imagine a complex
algorithm that indicate you if an array has a unique value (as the
Array.prototype.some) but horribly programmed.

The following step is 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.

The array are generated at the begin of the script:

And finally, when the user click in a button the functions are execute.

No memoization

Memoization

The result is shown in the following animation:

Conclusions

The memoization has been widely developed in web development using TypeScript
or JavaScript. The following list of resources must be the starting point to
use them in your projects.

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

The GitHub project is https://github.com/Caballerog/blog/memoization