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.
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
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.
- Define the cache in which the execution’s result will be store. We use a object as
mapto 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
stringifyand args from the original function.
resultof 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).
How to used our
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 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
The result is shown in the following animation:
The memoization has been widely developed in web development using
Fast-Memoize use this graph to compare different implementations of memoize:
- The GitHub project is https://github.com/Caballerog/blog/memoization
Originally published at www.carloscaballero.io on February 8, 2019.