What is memoization?
It is a programming technique that is used to increase the efficiency of function by storing the previous values that function has already been calculated.
It increases the program efficiency by caching the results of the function calls. We often waste time by calling the function again and again with the same parameter that had already been calculated. So we can store that calculated value and when the function is invoked with the same parameter then we just need to return that cached value.
Example 1: In this example, we’ll see the working of memoization:
Javascript
<script> function mul(num1, num2) { for (let i = 0; i < 10000000; i++) { } return num1 * num2; } console.log(mul(2, 3)); console.log(mul(2, 3));</script> |
Output:
6 6
Explanation: In this case, we are calculating the multiplication of two numbers but the function is taking time because of the for loop. And we are calling the function with the same parameters again and again. This is time wastage because we have already calculated the results of mul(2,3) and we are again calling it with the same parameter.
So, in this case, we can use the memoization technique to store the value of mul(2,3), and again when we will call the function with the same parameter then we will return the cached value.
Example 2: Let’s see how much time does our function took to calculate the value of mul(2,3).
Javascript
<script> function mul(num1, num2) { for (let i = 0; i < 10000000; i++) { } return num1 * num2; } console.time("Time taken"); console.log(mul(2, 3)); console.timeEnd("Time taken");</script> |
Output:
6 Time taken: 14.60ms
The function took 14.60 ms to calculate the multiplication of (2,3)
With the help of the memoization technique, we can increase the efficiency of the function by storing the value that function has already been calculated so that when we invoked the function with the same parameter then we will just return the cached value.
Example 3: Now let’s say how we can use the memoization technique to reduce the time taken to execute the function with the same parameter again and again.
Javascript
<script> function memoizeFunction(func) { let obj = {}; return function (a, b) { const x = a.toString() + b.toString(); if (!obj[x]) { obj[x] = func(a, b); } return obj[x]; } } function mul(num1, num2) { for (let i = 0; i < 10000000; i++) { } return num1 * num2; } console.time("First time time taken"); let func = memoizeFunction(mul); console.log(func(2, 3)); console.timeEnd("First time time taken"); console.time("Second time time taken"); func = memoizeFunction(mul); console.log(func(2, 3)); console.timeEnd("Second time time taken"); console.time("Third time time taken"); func = memoizeFunction(mul); console.log(func(2, 3)); console.timeEnd("Third time time taken");</script> |
Output:
6 First time, time taken: 24.73ms 6 Second time, time taken:22,17ms 6 Third time, time taken:8.30ms
NOTE: The amount of time it takes to complete a task may vary from time to time.
Explanation: In this case, we have used memoized function to cached the value that we have already been calculated. For the first time when we called func(2,3) then it will convert the parameter into string form and then stored it inside the object obj with the calculated value.
And when we called the func with the same parameter then at first it will check whether it already exists in the object obj or not. If it already exists then it will not calculate it again and will just return its value stored inside the object obj.
As we can see from the output that time to calculate the multiplication of 2 and 3 has decreased each time when we called the function with the same parameter.
Time is taken each time:
24.73 ms 22.17 ms 8.30 ms
So it’s clear from the output that the memoization technique helped in reducing the time each time we called the function with the same parameter again and again.
Example 4: Let’s see another example of using the memoization technique when calculating the Fibonacci number.
Javascript
<script> function memoizeFunction(func) { let obj = {}; return function (a) { const x = a.toString(); if (!obj[x]) { obj[x] = func(a); } return obj[x]; } } function fibonacci(n) { if (n === 0 || n === 1) return n; else return fibonacci(n - 1) + fibonacci(n - 2); } console.time("First time, time taken"); let func = memoizeFunction(fibonacci); console.log(func(10)); console.timeEnd("First time, time taken"); console.time("Second time, time taken"); func = memoizeFunction(fibonacci); console.log(func(10)); console.timeEnd("Second time, time taken"); console.time("Third time, time taken"); func = memoizeFunction(fibonacci); console.log(func(10)); console.timeEnd("Third time, time taken");</script> |
Output:
55 First time, time taken: 0.62ms 55 Second time, time taken: 0.28ms 55 Third time, time taken: 0.20ms
Advantages:
- With the help of memoization, we didn’t need to re-calculate the value again and again
- It helps in reducing the time taken to execute the function when we called the function with the same parameter again and again
- It improves the performance
Disadvantages:
- It uses memory to speed up the execution of the function
- It puts extra burdens on the program
- Space overheads
