Optimize the hell out of your Javascript programs with Memoization.
Many moons ago when I started learning algorithms, I had just learned recursion and was feeling like a Jedi. You know what they say?: “if all you have is a hammer, everything looks like a nail”. I was trying to solve every task imaginable with some form of recursion. Turns out it was a terrible idea.
I got a rude awakening when I tried to solve a long sequence of Fibonacci series with Recursion, my computer just couldn’t handle it. It still couldn’t compute the result after a couple of hours. Full disclosure; it never did, I gave up, shut the whole damn thing down and started rethinking my decision to ever become a programmer. Why didn’t I just learn how to rap, I could have become the next Jay-Z you know. I had no clue what was going on.
That was the first time I ever thought about the concept of optimization.
If you are the curious type, run the un-optimized recursive Fibonacci series with a sequence up to 50…..see you tomorrow!😃
So, what is Optimization?
What is optimization and why do you need to start thinking about it even as an inexperienced developer.
An optimization algorithm is a procedure which is executed iteratively by comparing various solutions till an optimum or a satisfactory solution is found.
For example in the optimization of a design, the design objective could be simply to minimize the cost of production or to maximize the efficiency of production.
And now, what is Memoization?
I know you are tempted to think that I misspelled “memorization”. But no! , I am positive I meant memoization. Memoization is a term in computer science which means the technique or optimization pattern that speeds up the execution of a program by storing the results of complex function calls (functions that takes a lot of time and consumes lots of memory during the run of the function) and returning the result stored in memory when the same inputs or arguments occur again. It’s a form of caching.
Urgh!!, enough of the computer science jargons!. I don’t even have a CS degree why should you trust my definitions. Allow me to show you the codes.
I will stick to the Fibonacci series that nearly made me quit programming. We’ll explore an example of an un-optimized Fibonacci function and another one optimized using memoization.
Set up
To be able to visualize the difference. We’ll need a little bit of one-time setup. I am a Javascript guy, I will be using a Node environment. You could use whatever performance metrics you are familiar with.
A NodeJS code sandbox will suffice. Let’s install and require `perf-hooks`. Simply require `performance` from perf-hooks like so:
Now let’s write a function that calculates the Fibonacci sequence of nth number recursively.
This function performs well for small values of “n”. However, performance quickly degrades as “n” increases. This is because the two recursive calls repeat the same work. For example, to compute the 50th Fibonacci number, the recursive function must be called over 40 billion times (40,730,022,147 times to be specific)! We’ll see this visually later.
A memoized Fibonacci function.
In the memoized version of the Fibonacci function When f() is returned, its closure allows it to continue to access the “memo” object, which stores all of its previous results. Each time f() is executed, it first checks to see if a result exists for the current value of “n”. If it does, then the cached value is returned. Otherwise, the original Fibonacci code is executed. Note that “memo” is defined outside of f() so that it can retain its value over multiple function calls.
Comparing performance with perf-hooks.
Let’s visualize the time it takes to compute 30th Fibonacci number with both functions.
Results
You can see we already increased the time to compute by a magnitude of over 20000. That’s just for a sequence of 30 numbers. This example is quite simple and may not look similar to your everyday tasks, but if you looked deeply there are a couple of things that can be optimized in your program. Keep in mind that memoization is just one optimization method, there are countless different strategies. Don’t be the hammer guy that treats every problem like a nail.
Note also that we have barely scratched the surface of memoization, this is just to open our minds to the possibilities.
The fact that it works does not mean it can’t be improved. Go forth and optimize!
PS: The title is a bit of an exaggeration. It just happened to be the 97th title that crossed my mind😃
