The JS Bifrost — Memoization it is!
A programmatic practice of making iterative or recursive functions more optimized
Welcome to The JS Bifrost, your pathway to a rock-solid foundation for a God-level JavaScript. Here is the next up in the series that throws light on memoization - let’s do it the dynamic programming way.
In computing, memoization 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. - sources: Wikipedia.
In a simpler words, Memoization is nothing but caching or storing the results in a memory.
Without Memoization
Fibonacci is the best example to illustrate the memoization concept. Let’s create the function which finds out Fibonacci of 10.
This function is suitable for smaller values of ’n’. As you increase the value of ’n’, the performance decreases.
As you see in the logs below, to find out the Fibonacci of 10, the function is called 177 times. This is because the fibo() function is getting called multiple times to compute the same result for the same value.
Consider, if value of ‘n’ is 4, then it’ll calculate fibo(3) and fibo(2), then fibo(3) calculate fibo(2) and fibo(1) and so on. I first thought, if ’n’ is 4 it’ll calculate only fibo(4), fibo(3), fibo(2) and fibo(1) with time complexity O(n) but nay !! The real time complexity for this is O(2^n).
Let’s deep dive and check how to optimize this using memoization.
With Memoization
The problem of re-computing the same result for the same value can be resolved if the function remembers the result that it had computed previously.
See in the above example, we have created one “cache” variable in the self-executing anonymous function which returns an inner function f(). When f() is returned, its closure allows it to continue to access the “cache” object, which stores all of its previous results.
If the function executes with any value of ’n’, it will first check its results in the cache at line no. 6. If it exists, then it will return the results from the cache. Otherwise, it will execute the original Fibonacci function in the else part.
As you see in the logs below, to find out the Fibonacci of 10, the function is called only 19 times. Because the function f() will execute only once for any value of ’n’ and time complexity with this approach is O(n), not O(2^n). Awesome right :)
Another example of memoization that finds the sum of ’n’ numbers where the function consistently receives the same arguments.
As you see in the above example and in the console logs, when it invokes the function for the first time to find out the sum of ’n’ number, it calculates and stores its results into the cache.
Later when it receives the same argument, it returns the result from the cache instead of re-computing the same, which saves the time and improves the performance.
When and How to use memoization
- Use memoization when the application performs heavy, time-consuming tasks, therefore storing the result might help you to save some processing time.
- Use it when the function receives the same arguments multiple times, which calculates the same results each time. With memoization, it saves time from re-calculating it.
- Try to divide big functions into the smaller ones to achieve the benefits of memoization.
- Don’t do memoization if you don’t see increase in the performance after implementing it, this will save some memory space too.
Conclusion
With memoization, we stop functions being called multiple times to calculate the same results for the same values and improves the performance by saving the time from re-calculating it over and over again.
Those who can not remember the past are condemned to repeat it. - George Santayana.
Stick around for more from our ‘The JS Bifrost’ Series.
Resources
https://www.sitepoint.com/implementing-memoization-in-javascript/
https://www.freecodecamp.org/news/understanding-memoize-in-javascript-51d07d19430e/
