Build Memoize in JavaScript – Part I

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
*/

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
*/

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.

Memoize Series

  1. Build Memoize in JavaScript – Part I (Higher order function)
  2. Build Memoize in JavaScript – Part II (Proxy Object)
  3. Build Memoize in JavaScript – Part III (MRU cache)
  4. Build Memoize in JavaScript – Part IV (MFU cache)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s