Memoization In JavaScript

Memoization is very common technique in programming, which consist of storing result of a function for later usage. You can call it like memorization for functions to distinguish from regular of the word memorization. Memorization is remembering result for functions. We will optimize our program and our computation may be long. Instead of repeating function invocation, We could just do it once and store the result somewhere. The same invocation happens in the new program instead of computation again. We can just go to store where the result is located and We can use it instead. It would be much quicker because it will be ready for computed and just stored somewhere. Basically it works as cache. The cache for functions and the functions result. We can invoke functions and discarding this result we can store it somewhere and invocation will work when we we need it in the future. When we say same invocation, it means that the arguments are passed to this function must be the same. If they are different, it would be a different result.

const sum = (a, b) => a + b;
console.log(sum(2,7))
console.log(sum(2,7))
//output: 9
//output: 9
const cache = {
"2,7":9
}

Let’s dive in and break down this code!

1- We have a sum function which takes two arguments (a , b) and its added two arguments;

2- If we print console.log(sum(2,7)) it we will get the result (9) in output. If we repeat that we invoke and execute this function again. It means it will call the function again and do the computation again and add those arguments again. But we don’t want to invoke the function over and over again. Instead we want to write a function and get the same result without repeatedly invoking the function.

3- Avoiding invoking the first function (sum), We can create a simple object called cache. We could basically say that when you see the arguments “2” & ”7" return(9) instead of going an invoking function over and over again. If we invoke the function above this function(sum) would have known instead of going and computing on function (sum), it would go cache and just check the arguments if they match like(2,7) and return 9. Every entry exists in this cache the function would avoid computing that and return right away immediately the result.

Normally, You would not do it by your hand. You don’t add this cache here as we did. It’s just for example to understand to logic of memoization. It’s better to use an existing solution.

But before we move forward I want to talk about complexity. When we see a function which is long and takes a longer time the execute and we want to reduce that time. When a function takes longer we say it’s computationally expensive. If a function is computationally expensive, we may want to reduce that. We may need to increase the memory usage in this case. Because instead of just doing it with computation, we need some place in the memory and we need to store the arguments for which the result will be memorized there. We need additional space for the case if we need more arguments than any other functions would invoke with different combinations of arguments or functions in our program. The memory space can grow and We need to make a decision if we want to optimize this function to execute faster or make the function shorter for certain results stored in memory. But in this case we need to have this memory. Normally we will not have any problem with space in memory because these days we have a lot of space in memory at our disposal, much more than in the past. Actually memorization technique is a great way to apply for functions which takes some time to some substantial time to execute. If you have a function you have to remember the results that you use for memoization. This technique is related somehow to another technique or algorithm rather than dynamic programming. There are a certain group or certain set of problems to use it in this way how you remember some invocations. In dynamic programming you may use memorization You may also use other techniques like tabulation to remember certain things in order to construct the final result. This makes sure that if those computations repeat in your execution then you can combine them and get the final result.

According the Memorization on Stack overflow

You’d normally use memoization to reduce the cost of repeatedly computing a result that will always be the same. Any performance improvement comes at the expense of allocating memory for the cached results.

A simple example in code:

var cachedResult;
function doHeavyCalculation()
{
if (typeof(cachedResult) !== 'undefined')
return cachedResult;

// no cached result available. calculate it, and store it.
cachedResult = /* do your computation */;
return cachedResult;
}

There are JavaScript frameworks that support memoizing any function, and they basically provide this boilerplate code for you in a reusable fashion by decorating a function.

The Fibonacci Series

Conventionally, many of the implementations of memoization you’ll find have used the well-known Fibonacci series to demonstrate how it can help with recursive solutions to problems.

In case you’re a little rusty on your high-school math, the Fibonacci series looks a little like this: 1,1,2,3,5,8,13,21,34.. etc.

Here, each number after the second, is the sum of the two numbers that appeared before it. Eg. 3 (let’s call this ‘x’) = x-1 (ie. 2) + x-2 (ie. 1). A classic fibonacci problem might therefore be to discover what the 20th number in the series is.

Below you can see an implementation of a base function for calculating Fibonacci numbers that relies on recursion in order to generate the correct result.

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

/*console profiling test*/
var fibTest = memoize(fib);
//first call
console.time("non-memoized call");
console.log(fibTest(20)); //varies (eg.10946)
console.timeEnd("non-memoized call");

//let's see how much better memoization fares..
console.time("memoized call");
console.log(fibTest(20));
//0ms in most cases (if already cached)
console.timeEnd("memoized call");

Software Engineer | Ruby on Rails | JavaScript | HTML5 | CSS | PostgreSQL | React | Redux