Functions are the building block of any programming language but in javascript, functions are even more special
In javascript, functions are First-class function i.e the functions can be assigned to any other variable or passed as an argument or can be returned by another function.
As we know that the whole point of functions is that we don't write again and again for a particular logic and we can just store that logic in the function and can just use that function instead and every time this function runs this whole logic is executed every time. but if this function has very heavy computational logic and every time we run this function we have to wait for that logic to compute the value.
Even If the input is the same twice. function logic will run twice to calculate the same result again
you see this just wastage of computational power.
what if there is a way that for a particular input we just have to run the logic only once and then we can use that result value every time we need that value. Instead of recalculating it again every time.
lucky for us that's possible and we call it Memoization
what exactly is Memoization?
Memoization is an optimization technique of storing previously executed computations. Whenever the program needs the result of these computations, the program will not have to execute that computation again. Instead, it will reuse the result of the previously executed computation. This way the program will not have to repeat expensive computations.
Explaining memoization to a 5-year-old
Let me explain memoization with a really simple and 90's example. It's the era of landline and instead of contact apps, I used to have a small dairy where I write important numbers every time I have to call someone I have to open that dairy look for that person's number in my diary.
but there were some numbers that I usually call on daily, for example, my dad so I memorized his number now whenever I have to call my dad I don't have to look into the phone book and find his number I can just directly dial his number via my memory.
So think of looking into the phone as a computation every time we need a number we need to do that computation but there are some numbers which we beforehand that they are important we are going to use them more often than others some memorize them think of this as memoization that computation
I hope now to have a better understanding of what memoization exactly
Let's talk about the concepts that make memoization possible in javascript
Closure - A closure is a combination of a function bundled together (enclosed) with references to its surrounding state (the lexical environment). In JavaScript, closures are generated every time a function is created, at the time a function is created.
If you wants to learn more about closure you should check out this video by Akshay Saini
High order function - A high order function accepts another function as an argument or returns a function as its output.
How memorization works?
So, whenever a function is being called it will do all the computation/work it is required to do and then cache the result in memory before the final return. So on the next call of that function, we will check if that input’s result is stored or not in our memory then we will proceed with the required computation or just return the result from storage if it exists.
Let's write some memoized functions
I am writing a simple square function and we are assuming there would be some have computational logic to calculate that sum and we console.log "heavy computational Logic ran" whenever that function ran
function square(a) {
console.log("heavy computational Logic ran ");
return a * a;
}
square(2);
square(2);
The output for the above code snippet would be.
heavy computational Logic ran
heavy computational Logic ran
As you can see heavy computational logic ran twice even for the same input. now memorize this square function to see if we can decrease the number of times this heavy computational logic ran.
function memoizer() {
let cache = {};
return function (a) {
if (cache[a]) {
console.log("retured from the cached value");
return cache[a];
}
console.log("heavy computational Logic ran ");
let squaredNumber = a * a;
cache[a] = squaredNumber;
return squaredNumber;
};
}
let memoizedSquare = memoizer();
memoizedSquare(2);
memoizedSquare(2);
The output for the above code snippet would be as you can see we only ran the heavy computation to calculate the square only once and store that value and used that stored value when the same input is provided instead of recalculation the value this can optimize our code and give us better performance in the real world
heavy computational Logic ran
retured from the cached value
Once memorized you never need to run heavy computation to calculate results for the same input in the current program.
Testing Memoization by performance
For demo purposes instead of console.logging that "heavy computational Logic ran" I have put a very heavy while loop to show you the difference between the not-memorized code and memorized code
Not-memoized code
function square(a) {
let i = 0;
//heavy computation
while (i < 9999) {
let j = 0;
while (j < 9999) {
j++;
}
i++;
}
return a * a;
}
Time taken for the first call and second call
First call: 0.09999999403953552ms
Second call: 0.09999999403953552ms
Memoized code
function memoizer() {
let cache = {};
return function (a) {
if (cache[a]) {
return cache[a];
}
let i = 0;
while (i < 9999) {
let j = 0;
while (j < 9999) {
j++;
}
i++;
}
let squaredNumber = a * a;
cache[a] = squaredNumber;
return squaredNumber;
};
}
let memoizedSquare = memoizer();
console.time("First call");
memoizedSquare(2);
console.timeEnd("First call");
console.time("Second call");
memoizedSquare(2);
console.timeEnd("Second call");
Time taken for the first call and second call
First call: 0.10000002384185791ms
Second call: 0.09999999403953552ms
As we can see in the memorized code the time taken for the second call is reduced significantly now assume the same performance enhancement in your app you memorize you frequently and highly computational Functions
so exactly are we doing in memorization?
All we’re doing is creating an object, checking for existing values that match the user input, and storing new key-value pairs if they don’t exist in our object.
It’s best to implement memoization on functions that are pure and involve heavy, repetitive calculations.
conclusion
Memoization is a programming concept and can be applied to any programming language. Its fundamental goal is to optimize your program. In memoization, we prevent our functions from calling functions that re-calculate the same output over and over again. So, memoization helps to reduce the amount of time taken in the execution of programs.
