July 29, 2020 – Digital Concept Visuals

Memoize or Memorize? Memoize!

From Wikipedia “In computing memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.”

So basically, memoization is caching results of function calls. Obviously, this should be done ONLY for those functions which return the same result for same input.

It’s actually pretty easy to implement this. Let’s take a look at how we can implement this in a compute intensive function like calculating primes.

So let’s first write a simple prime program

	// Check if given number is prime
	const isPrime = number => {
	// Divide number by all numbers from 2 to sqrt(number)
	// If divisible, then its not a prime
	let div;
	for (div = 2; div < Math.sqrt(number); div++)
	if (number % div == 0) {
	console.log(`Looped ${div} times`);
	return false;
	}
	console.log(`Looped ${div} times`);
	return true;
	}

	// This is a known prime
	console.log(isPrime(1299827));
	console.log(isPrime(1299827));

	/* Output

	Looped 1141 times
	1299827 is prime: true
	Looped 1141 times
	1299827 is prime: true

	*/

view raw SimplePrime.js hosted with ❤ by GitHub

Simple Prime

As we can see, when the function is called twice for the same input, it goes thru the same numbers of execution cycles to compute whether it’s prime or not. What we can do is store the result for that number in some map and then return it without computing it again.

Here is modified isPrime with result caching.

	// We store previous results here
	const cache = {};

	// Check if given number is prime
	const isPrime = number => {

	// Check cache if we have previous result
	if (number in cache) {
	console.log(`Found ${number} in cache: ${cache[number]}`);
	return cache[number];
	}

	if (number < 2) return false;

	// Divide number by all numbers from 2 to sqrt(number)
	// If divisible, then its not a prime
	let div;
	for (div = 2; div < Math.sqrt(number); div++)
	if (number % div == 0) {
	console.log(`Looped ${div} times`);
	cache[number] = false;
	return false;
	}
	console.log(`Looped ${div} times`);
	cache[number] = true;
	return true;
	}

	// This is a known prime
	let number = 1299827;
	console.log(`${number} is prime: ${isPrime(number)}`);
	console.log(`${number} is prime: ${isPrime(number)}`);

	/* Output
	Looped 1141 times
	1299827 is prime: true
	Found 1299827 in cache: true
	1299827 is prime: true
	*/

view raw PrimeWithCache.js hosted with ❤ by GitHub

As we can see, the second time we call isPrime with the same input, it returns the value from cache, saving time of executing the for loop. This is Memoization.

However, we would have to write our own code for Memoization every time. Can’t we build a standalone Memoization and “plug it” on different functions?

Of course we can!


	// Check if given number is prime
	const isPrime = number => {

	if (number < 2) return false;

	// Divide number by all numbers from 2 to sqrt(number)
	// If divisible, then its not a prime
	let div;
	for (div = 2; div < Math.sqrt(number); div++)
	if (number % div == 0) {
	console.log(`Looped ${div} times`);
	return false;
	}
	console.log(`Looped ${div} times`);
	return true;
	}

	const memoize = fn => {
	// We store previous results here
	const cache = {};

	// Return a function to be called
	return memoized = (…args) => {

	// If result not in cache, first cache it
	if (!(args in cache))
	cache[args] = fn(…args);

	// Now return it
	return cache[args];
	}
	}

	// This is a known prime
	let number = 1299827;
	const smartPrime = memoize(isPrime);
	console.log(`${number} is prime: ${smartPrime(number)}`);
	console.log(`${number} is prime: ${smartPrime(number)}`);

	/* Output
	Looped 1141 times
	1299827 is prime: true
	1299827 is prime: true
	*/

view raw SImpleMemoize.js hosted with ❤ by GitHub

Yay! We have created a “plug in” called memoize, which we can use to wrap any pure function (one which has no side effects and returns the same result for same inputs).

Wait a minute… if we call smartPrime with thousands of different values, won’t it eat up memory in the cache? Unfortunately, yes!

In the next blog post, we will see how to build Memoize using JavaScript Proxy object and how to keep the cache size in control by keeping only the MRU (Most Recently Used) and MFU (Most Frequently Used) entries.