What Is Memoization?
The definition of memoization from 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.” — Wikipedia
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.
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.
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:
- 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.
- 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.
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.
Another interesting example of pure functions is the following:
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
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.
- Define the cache in which the execution’s result will be stored. We use an object as
mapto store this result.
- The decorator returns a new function which has the same behavior as the original function but memoization is implemented.
- The key of the key-value map is generated using the
stringifyand args from the original function.
resultof 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).
result is returned.
How To Use the Memoized Decorator?
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.
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.
The arrays are generated at the begin of the script:
And finally, when the user clicks on a button the functions are executed.
- No memoization:
The result is shown in the following animation:
Fast-Memoize use this graph to compare different implementations of memoize:
- The GitHub project.