What is Memoization?
Memoization is an optimisation technique base on remembering results returned by a function called with same arguments.
If we have a pure function that consume intensive computation, then we can use memoization.
The memoization will help us store the output value that has already been achieved and then the next time the function is called with the same input value it can simply return the stored value without going through all the computations.
Without memoisation computations are excessive, and time consumed for the following function is 4727 ms :
Thanks to memoization we gain a lot in performance, and the time consumed decreased to 1ms :
There are a couple of patterns for implementing memoization:
- Function as an object
- Higher Order Function
Function as an Object
Function as an object (which it is actually) where we store the cached value (instead of using global variable) is our first way of memoization, as shown in the example bellow:
We see that we the result is cached in the function as long as the process is alive.
Same goes for Fibonacci function
And same behavior when we have multiple arguments
Higher Order Function Memoization
Higher Order Function is our second way for memoizing, as we see in this example where we enclose our function to memoize inside a Higher Order Function:
The third way of memoization that we can use and also the fastest way is using closure. For example we can memoize a recursive function from the first call by setting it as an inner function that will have a closure.
We can find the code used in the above examples here.