Memoization & its implementation in Javascript

Memoization & its implementation in Javascript

Problem

Javascript is single-threaded and synchronous. When it encounters a function that calculates a computationally expensive value, the entire program is on halt till the value is calculated. Now after a certain point, we cannot optimize the calculation time of the function, but what we can do is, store(cache) the calculated value along with the inputs that resulted in the value. So when the function receives the same input we can fetch the result from the cache.

Solution

Here I am going to explain memoization with a simple example of memoized add function. I take a simple example as I need to explain few Javascript concepts in this post that are needed to understand the implementation of memoization in Javascript.

So the function that I want to memoize is,

const addToTen = (num) => num + 10;

addToTen accepts a number "num" as an argument, adds 10 to it, and returns the result. For the scope of this post, assume that instead of just adding 10 to a number this function did some expensive calculations with "num".

Now in order to memoize this function, we would need to store the input and the calculated result so we'll use an array "cache" for that where the array index will be the "num" and we'll store the result at cache[num].

const memoizedAddToTen = () => {
    let cache = [];
    return (num) => {
        //This is the function that will check whether the addition for "num" is already calculated. If so then it will fetch the value from the cache else it will calculate the value for the "num" and store it in the cache.
    }
}

Functions are first-class citizens in Javascript which means that functions can be passed as an argument to a function and/or returned from a function. In the above example, we have a function memoizedAddToTen which returns an anonymous function(a function without a name) which we will store in addToTen.

memoizedAddToTen has an array named "cache" to store the calculated result by the anonymous function.

const memoizedAddToTen = () => {
    let cache = [];
    return (num) => {
        if(cache[num]){
            console.log("Fetching from cache...");
            return cache[num];
        }else{
            console.log("Calculating the value...");
            const result = num + 10;
            cache[num] = result;
            return result;
        }
    }
}

In the anonymous function, we check whether the result for the "num" is already present in the cache array, if so then we don't calculate the value and return the value from the cache. In case the value is not present in the cache then we calculate the value, add it to the cache, so that we don't have to calculate if the same "num" is passed in future function calls, and then we return the calculated value.

Now comes the fun part of how to consume this memoized function.

const addTen = memoizedAddToTen();

First, we store the anonymous callback, returned from the memoizedAddToTen, to addTen. Now even though memoizedAddToTen has completed its execution the addTen will have access to the reference of cache array which was declared in memoizedAddToTen. This happens because of the concept of closure. A closure is the combination of a function's scope and its parent function's scope. You can find more about closure at here by Dan Abramov and here by Akshay Saini.

console.log(addTen(5)) // calculates and returns 15
console.log(addTen(25)) // calculates and returns 35
console.log(addTen(5)) // fetches result from cache as we stored result for input 5 in cache

Now we call the addTen function with the num values 5, 25, and 5. The results will be calculated for first two calls but for last call it will be fetched from the cache as the input 5 is repeated and we had stored the result for 5 in the cache.

Let's make the memoized function more usable,

const memoizedAdd = (value) => {
    let cache = [];
    return (num) => {
        if(cache[num]){
            console.log("Fetching from cache...");
        }else{
            console.log("Calculating the value...");
            const result = num + value;
            cache[num] = result;   
        }
        return cache[num];
    }
}

Now we can get a memoziedAdd function for any value that we want to add to the num. And also I moved the return from the if-else condition as we return from the cache either way, either if it already exists or after calculating and storing the result into the cache. We can even remove the result variable but I am leaving it for now.

Now the memoized function can be used as follows,

const addTen = memoizedAdd(10);

const addTwenty = memoizedAdd(20);

// Both addTen and addTwenty have different cache references, one of each call to the memoizedAdd function.

console.log(addTen(5)) // calculates and returns 15
console.log(addTen(20)) // calculates and returns 30
console.log(addTen(5)) // fetches result from cache as we stored result for input 5 in cache

console.log(addTewenty(5)) // calculates and returns 25
console.log(addTewenty(20)) // calculates and returns 40
console.log(addTewenty(5)) // fetches result from cache as we stored result for input 5 in cache

The above way of partially initializing the function with one argument and then calling the stored reference with the remaiming arguments is known as currying. Find more about currying here

So Memoization is the concept where you cache(store) the results for a given set of inputs of a computaitonally expensive function.