Improve website performance - Javascript Memoization

Memoization

What is Memoization?

Memoization is a technique used in programming to write optimizied code. This is very useful in use cases when the system is performing very CPU intensive tasks repeatedly.

What are the use Cases for Memoization?

Memoization can be useful when the system is performing same task again and again like

1. API output caching - This is not recommended though as it requires a cache invalidation mechanism which is tricky to implement.

2. Calling a recursive function e.g. Fibonacci series.

One thing to note here is, memoization works well in case of pure function only.

What is a Pure function ?

A function which produces the same output for the same given input every time.

Lets understand this with the Fibonacci series example.

Below program is written without memoization where result of previously executed function is not cached. So each time the program calls the Fibonacci function, it calculates results every time.

Now, below is the improved memoized version of above example. System will take more time for the first time. Rest of the calls get completed almost instantaneously. 

	function fibonacci(num){
	if(num<=2){
	return 1;
	}
	return fibonacci(num-1) + fibonacci(num-2);
	}

view raw fibo.js hosted with ❤ by GitHub

Now, let's rewrite the same program with the caching result of an already executed function into one local variable. Now, every time the Fibonacci function gets called it first checks if there is any caching result available or not. If  that function with the given input already had executed in the past it will simply return an already cached result.

	function fibonacciWithMemoization(num, cachedResult = []) {
	if (cachedResult[num] != null) {
	return cachedResult[num];
	}
	let result;
	if (num <= 2) {
	result = 1;
	} else {
	result = fibonacciWithMemoization(num - 1, cachedResult) + fibonacciWithMemoization(num - 2, cachedResult);
	}
	cachedResult[num] = result;
	return result;
	}

view raw fiboWithMemo.js hosted with ❤ by GitHub

Another use case for memoization could be a function which produces square of given input number. To mimic CPU intensive task we are providing big number to calculate square and we are using addition instead of multiplication to increase complexity

In below example, we are not caching any value. So, when this program get executed, it will take same time each time.

	function square(num) {
	let sqr = 0;
	for (let i = 0; i < num; i++) {
	for (let j = 0; j < num; j++) {
	sqr += 1;
	}
	}
	return sqr;
	};
	let squareStartTime = Date.now(); // set starting milliseconds;
	console.log(`Start Time ${squareStartTime}`);
	console.log(square(100000));
	console.log(`End time ${Date.now()}`);
	let totalTimeElased = Date.now() - squareStartTime;
	console.log(`Total Time elapsed ${totalTimeElased}`);
	console.log('Total time elapsed in Square function without Memoizatino - First Call', Math.floor(totalTimeElased / 1000));
	squareStartTime = Date.now();
	console.log(square(100000));
	totalTimeElased = Date.now() - squareStartTime;
	console.log('Total time elapsed in Square function without Memoizatino - Second Call', Math.floor(totalTimeElased / 1000));
	squareStartTime = Date.now();
	console.log(square(100000));
	totalTimeElased = Date.now() - squareStartTime;
	console.log('Total time elapsed in Square function without Memoizatino - Third Call', Math.floor(totalTimeElased / 1000));

view raw square.js hosted with ❤ by GitHub

Now, we can rewrite above code using cached result this will improve performance first time onwards that is first time it will take time what it is needed to calculate but first time onwards it will return cached value. 

	const cachedResult = [];
	function squareWithMemo(num) {
	if (cachedResult[num] != null) {
	return cachedResult[num];
	}
	let sqr = 0;
	for (let i = 0; i < num; i++) {
	for (let j = 0; j < num; j++) {
	sqr = sqr + 1;
	}
	}
	cachedResult[num] = sqr;
	return sqr;
	};
	let squareStartTimeWithMemo = Date.now(); // set starting milliseconds;
	console.log(squareWithMemo(100000));
	totalTimeElased = Date.now() - squareStartTimeWithMemo;
	let totalTimeElased = Date.now() - squareStartTime;
	console.log('Total time elapsed in Square function Memoized - First Call', Math.floor(totalTimeElased / 1000));
	squareStartTimeWithMemo = Date.now();
	console.log(squareWithMemo(100000));
	totalTimeElased = Date.now() - squareStartTimeWithMemo;
	console.log('Total time elapsed in Square function Memoized - Second Call', Math.floor(totalTimeElased / 1000));
	squareStartTimeWithMemo = Date.now();
	console.log(squareWithMemo(100000));
	totalTimeElased = Date.now() - squareStartTimeWithMemo;
	console.log('Total time elapsed in Square function Memoized - Third Call', Math.floor(totalTimeElased / 1000));

view raw squareMemo.js hosted with ❤ by GitHub

Repository link for above program can be found here