Memoization is an optimization technique that can be used to reduce the runtime for calculations by saving previous input to something called cache and returning results from it.
-> Let’s make it simple,
• Suppose you have to work at a Medical dispensary for one day instead of your uncle. It’s your first day in that shop & at the very first hour a customer comes and asks you for “Paracetamol tablets”, now as it’s your first day you don’t know about the placements of medicine in that big shop(aha! uncle is rich 🤑 LOL).
• Now you will start searching shop for that medicine,
there may be a best case that the first drawer you opened is full with Paracetamol tabs
and also there may be a worst case that after searching for the whole shop you find those tabs in the last drawer.
• Let’s go with the worst case, now searching for the whole shop consumes much time, then you give that medicine to that buyer.
but now you know that Paracetamol tabs are present in that particular drawer (you memorized it, you stored it somewhere)
• Now if some other person would come and ask for Paracetamol tabs, without searching and spending more time, you can easily take the medicine from that memorized drawer and you give it to the buyer in no time.
-> Similarly,
To understand this awesome yet tricky concept, let’s dive into the code.
Here, I have written a simple function which triggers the loop and runs it ’n’ number of time, where ’n’ is the input. And every time the for loop runs it will add index to the sum, and then returns sum.
Now this is good code for some small inputs, but if the input is large then this will be much costly.
Suppose, I want this loop to run 1Million times, So, I have to write code
console.time();
console.log(calc(1000000));
console.timeEnd(); //this line will print runtime in 'ms'
console.time();
console.log(calc(1000000));
console.timeEnd(); //this line will print runtime in 'ms'
Running this will take what time logged in console is attached below:
For the same input, loop will run 1 Million times whenever we pass input 1Million, and that’s not good for software, it’s not cost effective.
So we will use MEMOIZATION technique, where we will store the output value, when input is 1Million (or anything).
console.time();
console.log(ans(100000000));
console.timeEnd();
console.time();
console.log(ans(100000000));
console.timeEnd();
Here we can see that time taken to calculate for 1Million first time is large in ‘ms’ but for the next time , it’s as small as negligible.
I hope it helps :)
Top comments (0)