What is memoization?

Memoization is an optimization technique used in many programming languages to reduce the expensive function calls. This can be achieved by caching the return value of functions based on their input.

Usages

Firstly let's try to create an expensive function which will give us a visual of what scenario memoization can be useful for us.

const expensiveFunction = (num) => {
    let total = 0;
    for(let i = 0; i < num; i++) {
        for(let j = 0;j<num;j++) {
            total++;
         }    
    }
    return total;
}

In the above function, we are calculating the square of a number in a very expensive way. Now let's calculate how much time it takes to return the value.

const start = new Date()
expensiveFunction(3000000)
console.log(new Date() - start);

Here no matter how many times we pass the same argument. It will take the same amount of time. This seems irrelevant since our function has calculated the result once with this argument.

Now comes the memorizer which is going to cache the result and return the result from the cache value in case of the same argument is passed to the function. Let's create a memorizer in js.

Implementation

const memorizer = (fn) => {
    const cache = {}
    return (...args) => {
        const key = JSON.stringify(args) //
        if(!cache[key]) {
            cache[key] = fn(...args)
        }
        return cache[key]
    }
}

That’s all our memorizer function is ready to be implemented in our expensiveFunction . Let me explain this function to you. Here we are creating an object name cache which is going to store the arguments. Here we are also doing JSON.stringify to create a unique key which we can store in a cache object. Then we are checking if the key is not available already then our function will run and calculate the value else it will just return the cache value which is available in our cache object.

In the above snippets, I have shown you one way to create a memorizer. Similarly, here you can also use map data structure which I will show you at the end of this post.

const expensiveFunction = memorizer((num) => {
    let total = 0;
    for(let i = 0; i < num; i++) {
        for(let j = 0;j<num;j++) {
            total++;
         }    
    }
    return total;
});

Now we can test this out. If you run this above function and try to run it by passing the same value you will notice First time it will take some time. But after the first time, it gives you the result instantly.

Memorization can also be used especially with the recursion function because it can reduce the number of redundant calculations that are performed. Let's have an example that we can use to memorize a recursive function.

function fib(n) {
  if (n < 2) {
    return n;
  }
  return fib(n - 1) + fib(n - 2);
}

const memoizedFib = memorizer(fib);
console.log(memoizedFib(10));

Here, When we call memoizedFib(10), the memoized version of the function is used to calculate the 10th Fibonacci number. Because the memoized function caches the results of previous calculations, the computation is much faster than it would be with the original fib function.

Second Method using a Map.

function memoize(fn) {
    let cache = new Map();
    return function(...args) {
        const key = JSON.stringify(args)
        if (cache.has(key)){
            return cache.get(key);
        }
        const output = fn(...args);
        cache.set(key, output);
        return output;        
    }
}

It is almost similar to the above implementation. The only thing is we have used map which will give more efficient results than the previous one. Apart from this, you can use some third-party libraries which will give more optimized functions to memorize your function.

This is all for memorization. Hope you like it.

Happy Coding 👍