Build Memoize in JavaScript – Part IV

In the previous posts we have build Memoize using higher order functions, Proxy object and controlled the runaway cache by implementing MRU inside our Proxy objects. However, it would make more sense to have a Most Frequently Used (MFU) cache, which unlike MRU does not go by recency effect but with frequency of usage.

The basic problem remains with Map() as a cache that it does not have insertion order. So we could use Array List, forgoing our O(1) lookup. For sake of challenge and academic satisfaction, let’s write an MFU caches using a hybrid of Map (O(1) look up ) and custom class (for storing frequency).

But first a dirty trick to enable/disable debug output within out code

// Simple debug tricks
const nop = () => { };
let debug = nop; // Disable debug output
debug = console.log; // Enable debug output
view raw Debug.js hosted with ❤ by GitHub

Now Let’s write an MFUMap which extends a Map, where we will incorporate a List with key and frequency and Recency. We create a user defined class to hold them.

// Class to store frequency and recency of the key
class Frequency {
// Private fields
#frequency; // Number of times the key has been accessed
#recency; // Last timestamp of access
constructor(frequency = 1, recency = new Date()) {
this.#frequency = frequency;
this.#recency = recency.getTime() + recency.getMilliseconds();
}
// Update frequency and recency
update = () => {
this.#frequency++;
let now = new Date();
this.#recency = now.getTime() + now.getMilliseconds();
}
get frequency() { return this.#frequency; }
get recency() { return this.#recency; }
toString = () => {
return `{ frequency: ${this.#frequency}, recency: ${this.#recency} }`;
}
}
view raw Frequency.js hosted with ❤ by GitHub

Frequency class holds the frequency (number of times the key has been accessed) and recency (the last time the key was accessed). Recency is tie breaker in case we want to drop entries which has same frequency.

Now to the next… MFUMap which will extend a Map. Rather that composing a Map, we will extend it, so that we don’t have to write wrapper/forwarder functions for a Map. By extending it, we will simply override the ones we want to modify and leave the rest to go to base class Map.

Here is our skeletal MFUMap class

// We extend the map instead of composing it
// So that non-overridden functions are passed to the base
class MFUMap extends Map {
// Private properties
#frequencyMap = new Map();
#maxSize = 10;
constructor(size = 10) {
super();
this.#maxSize = size;
debug(`Initialized map with size=${size}`);
}
// Check if our map size is going beyond maxSize
#resizeMap = () => {
// Drop entries from the map
}
#updateFrequency = key => {
// Update frequency of the key here
}
// Override the get and set function of Map
set(key, value) {
let result = super.set(key, value);
// Update the frequency of the key
this.#updateFrequency(key);
return result;
}
get(key) {
let exists = super.get(key);
// Don't update non existing gets
if (exists)
this.#updateFrequency(key);
return exists;
}
}
view raw SkeletonMFU.js hosted with ❤ by GitHub

We are overriding get and set functions of Map, where we will update the frequency/recency of key usage. This will help us deciding which keys to drop when we go over maxSize.

Now let’s start filling in our MFUMap with details.
First, the UpdateFrequency code, which will be called any time the key is accessed (set/get), so that we can bump up its frequency and also set the last accessed time (tie breaker for same frequency keys).

// if key was accessed, increment its frequency
#updateFrequency = key => {
let frequencyObject = this.#frequencyMap.get(key);
// if existing key, update the frequency
if (frequencyObject)
frequencyObject.update();
else
this.#frequencyMap.set(key, frequencyObject = new Frequency());
debug(`Updated { ${key} => ${frequencyObject} }`);
// Maybe we went over the maxSize, truncate the Map
this.#resizeMap();
}

With that done, we now need to trim our MFUMap whenever it goes over maxSize. Whenever we update frequency, we call private #resize method to check if we need to trim it.

#resizeMap determines the candidate key for removal. It does that by finding out the lowest frequency key and if there are more than 1 with same frequency, it uses recency (timestamp) to elect the candidate (kind of MFU + MRU).

// Check and trim our cache size
#resizeMap = () => {
if (this.size <= this.#maxSize)
return false;
debug(`Resizing map: ${this.size} > ${this.#maxSize}`);
// Elements required to determine candidates
let minKey;
let minFrequency = Number.MAX_VALUE;
let minTime;
// Find the lowest frequency key
for (let [key, value] of this.#frequencyMap) {
let entryFrequency = value.frequency;
let entryTime = value.recency;
// Find the lowest frequency key
if (entryFrequency < minFrequency) {
minFrequency = entryFrequency;
minKey = key;
minTime = entryTime;
} else {
// If there are multiple keys with same frequency
// Choose the least recency key
if (entryFrequency == minFrequency) {
if (entryTime < minTime) {
minFrequency = entryFrequency;
minKey = key;
minTime = entryTime;
}
}
}
}
debug(`Deleting { ${minKey} => { frequency: ${minFrequency}, recency: ${minTime} }`);
this.delete(minKey);
this.#frequencyMap.delete(minkey);
return true;
}
view raw ResizeMap.js hosted with ❤ by GitHub

Now that we are set, all we need to do is override the Map’s get/set to call our #updateFrequency and let it #resizeMap if necessary

set(key, value) {
let result = super.set(key, value);
// Update the frequency of the key
this.#updateFrequency(key);
return result;
}
get(key) {
let exists = super.get(key);
// Don't update non existing gets
if (exists)
this.#updateFrequency(key);
return exists;
}
}
view raw getset.js hosted with ❤ by GitHub

There! We are set. We have implemented a Most Frequency Used (MFU) cache with Most Recently Used (MRU) for tie-breaker and we can limit the cache size of for Memoize.

Here is the complete list of MFUMap along with Frequency class

/**
* Some debug helpers
*/
const nop = () => { };
let debug = nop; // Disable debug output
debug = console.log; // Enable debug output
// Class to store frequency and recency of the key
class Frequency {
// Private fields
#frequency; // Number of times the key has been accessed
#recency; // Last timestamp of access
constructor(frequency = 1, recency = new Date()) {
this.#frequency = frequency;
this.#recency = recency.getTime() + recency.getMilliseconds();
}
// Update frequency and recency
update = () => {
this.#frequency++;
let now = new Date();
this.#recency = now.getTime() + now.getMilliseconds();
}
get frequency() { return this.#frequency; }
get recency() { return this.#recency; }
toString = () => {
return `{ frequency: ${this.#frequency}, recency: ${this.#recency} }`;
}
}
/**
* MFU class
*/
// We extend the map instead of composing it
// So that non-overridden functions are passed to the base
class MFUMap extends Map {
#frequencyMap = new Map();
#maxSize = 10;
constructor(size = 10) {
super();
this.#maxSize = size;
debug(`Initialized map with size=${size}`);
}
// Check and trim our cache size
#resizeMap = () => {
if (this.size <= this.#maxSize)
return false;
debug(`Resizing map: ${this.size} > ${this.#maxSize}`);
// Elements required to determine candidates
let minKey;
let minFrequency = Number.MAX_VALUE;
let minTime;
// Find the lowest frequency key
for (let [key, value] of this.#frequencyMap) {
let entryFrequency = value.frequency;
let entryTime = value.recency;
// Find the lowest frequency key
if (entryFrequency < minFrequency) {
minFrequency = entryFrequency;
minKey = key;
minTime = entryTime;
} else {
// If there are multiple keys with same frequency
// Choose the least recency key
if (entryFrequency == minFrequency) {
if (entryTime < minTime) {
minFrequency = entryFrequency;
minKey = key;
minTime = entryTime;
}
}
}
}
debug(`Deleting { ${minKey} => { frequency: ${minFrequency}, recency: ${minTime} }`);
this.delete(minKey);
return true;
}
// if key was accessed, increment its frequency
#updateFrequency = key => {
let frequencyObject = this.#frequencyMap.get(key);
// if existing key, update the frequency
if (frequencyObject)
frequencyObject.update();
else
this.#frequencyMap.set(key, frequencyObject = new Frequency());
debug(`Updated { ${key} => ${frequencyObject} }`);
// Maybe we went over the maxSize, truncate the Map
this.#resizeMap();
}
set(key, value) {
let result = super.set(key, value);
// Update the frequency of the key
this.#updateFrequency(key);
return result;
}
get(key) {
let exists = super.get(key);
// Don't update non existing gets
if (exists)
this.#updateFrequency(key);
return exists;
}
}
view raw MFUMap.js hosted with ❤ by GitHub

Here is the isPrime function we want to Memoize with MFUMap

// 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)
return false;
return true;
}
view raw isPrime.js hosted with ❤ by GitHub

Let Memoize with MFUMap

// Memoize is a Proxy to the actual function
const memoize = (fn, mfu = 10) => new Proxy(fn,
// Handler with traps
{
cache: new MFUMap(mfu),
max: mfu, // Our cache limit
// Our "magic" property
get(object, property, receiver) {
if (property == "cache")
return this.cache;
return Reflect.get(object, property, receiver);
},
// Intercept call to the wrapped function
apply(target, thisArg, args) {
let result = this.cache.get(args.toString());
if (result)
return result;
result = Reflect.apply(target, thisArg, args);
this.cache.set(args.toString(), result);
return result;
}
}
);
view raw MemoizeMFU.js hosted with ❤ by GitHub

We are all set to roll… let’s test it

We will Memoize isPrime with MFU size of 3 and then repeated called the smartPrime to change the frequency. Further when we call isPrime, instead of MRU, it will select keys which are most frequently used.

let number = 10;
let smartPrime = memoize(isPrime, mfu = 3);
smartPrime(1);
smartPrime(2);
smartPrime(2); // MFU
smartPrime(1); // MFU
smartPrime(3); // MRU
smartPrime(4);
console.log(smartPrime.cache);
/* Output
Initialized map with size=3
Updated { 1 => { frequency: 1, recency: 1596064558140 } }
Updated { 2 => { frequency: 1, recency: 1596064558148 } }
Updated { 3 => { frequency: 1, recency: 1596064558148 } }
Updated { 2 => { frequency: 2, recency: 1596064558150 } }
Updated { 1 => { frequency: 2, recency: 1596064558150 } }
Updated { 4 => { frequency: 1, recency: 1596064558150 } }
Resizing map: 4 > 3
Deleting { 3 => { frequency: 1, recency: 1596064558148 }
MFUMap(3) [Map] { '1' => false, '2' => true, '4' => false }
*/
view raw MFUOutput.js hosted with ❤ by GitHub

Who got dropped first? 3!
Why? Because 1 and 2 were more frequently used, even though 3 was most recently used. Makes sense?

Here is the entire code which implements

  1. debug “macros”
  2. Frequency class
  3. MFUMap
  4. isPrime function
  5. memoize Proxy
  6. Test code
/**
* Some debug helpers
*/
const nop = () => { };
let debug = nop; // Disable debug output
debug = console.log; // Enable debug output
// Class to store frequency and recency of the key
class Frequency {
// Private fields
#frequency; // Number of times the key has been accessed
#recency; // Last timestamp of access
constructor(frequency = 1, recency = new Date()) {
this.#frequency = frequency;
this.#recency = recency.getTime() + recency.getMilliseconds();
}
// Update frequency and recency
update = () => {
this.#frequency++;
let now = new Date();
this.#recency = now.getTime() + now.getMilliseconds();
}
get frequency() { return this.#frequency; }
get recency() { return this.#recency; }
toString = () => {
return `{ frequency: ${this.#frequency}, recency: ${this.#recency} }`;
}
}
/**
* MFU class
*/
// We extend the map instead of composing it
// So that non-overridden functions are passed to the base
class MFUMap extends Map {
#frequencyMap = new Map();
#maxSize = 10;
constructor(size = 10) {
super();
this.#maxSize = size;
debug(`Initialized map with size=${size}`);
}
// Check and trim our cache size
#resizeMap = () => {
if (this.size <= this.#maxSize)
return false;
debug(`Resizing map: ${this.size} > ${this.#maxSize}`);
// Elements required to determine candidates
let minKey;
let minFrequency = Number.MAX_VALUE;
let minTime;
// Find the lowest frequency key
for (let [key, value] of this.#frequencyMap) {
let entryFrequency = value.frequency;
let entryTime = value.recency;
// Find the lowest frequency key
if (entryFrequency < minFrequency) {
minFrequency = entryFrequency;
minKey = key;
minTime = entryTime;
} else {
// If there are multiple keys with same frequency
// Choose the least recency key
if (entryFrequency == minFrequency) {
if (entryTime < minTime) {
minFrequency = entryFrequency;
minKey = key;
minTime = entryTime;
}
}
}
}
debug(`Deleting { ${minKey} => { frequency: ${minFrequency}, recency: ${minTime} }`);
this.delete(minKey);
return true;
}
// if key was accessed, increment its frequency
#updateFrequency = key => {
let frequencyObject = this.#frequencyMap.get(key);
// if existing key, update the frequency
if (frequencyObject)
frequencyObject.update();
else
this.#frequencyMap.set(key, frequencyObject = new Frequency());
debug(`Updated { ${key} => ${frequencyObject} }`);
// Maybe we went over the maxSize, truncate the Map
this.#resizeMap();
}
set(key, value) {
let result = super.set(key, value);
// Update the frequency of the key
this.#updateFrequency(key);
return result;
}
get(key) {
let exists = super.get(key);
// Don't update non existing gets
if (exists)
this.#updateFrequency(key);
return exists;
}
}
// 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)
return false;
return true;
}
// Memoize is a Proxy to the actual function
const memoize = (fn, mfu = 10) => new Proxy(fn,
// Handler with traps
{
cache: new MFUMap(mfu),
max: mfu, // Our cache limit
// Our "magic" property
get(object, property, receiver) {
if (property == "cache")
return this.cache;
return Reflect.get(object, property, receiver);
},
// Intercept call to the wrapped function
apply(target, thisArg, args) {
let result = this.cache.get(args.toString());
if (result)
return result;
result = Reflect.apply(target, thisArg, args);
this.cache.set(args.toString(), result);
return result;
}
}
);
let number = 10;
let smartPrime = memoize(isPrime, mfu = 3);
smartPrime(1);
smartPrime(2);
smartPrime(2);
smartPrime(1);
smartPrime(3);
smartPrime(4);
console.log(smartPrime.cache);
view raw MFUMemoize.js hosted with ❤ by GitHub

Feels good?

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)

Build Memoize in JavaScript – Part III

In the previous two posts we have built memoize feature using two different flavours – Higher order function and Proxy. However, there is one concern in both implementations – runaway caching.

// 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)
return false;
return true;
}
// Memoize is a Proxy to the actual function
const memoize = fn => new Proxy(fn,
// Handler with traps
{
// We store previous results here
cache: {},
get(object, property, receiver) {
if (property == "length")
return Object.keys(this.cache).length;
},
// Intercept call to the wrapped function
apply(target, thisArg, args) {
if (!(args in this.cache))
this.cache[args] = Reflect.apply(target, thisArg, args);
return this.cache[args];
}
}
);
// This is a known prime
let smartPrime = memoize(isPrime);
let max = 1000000;
let primeCount = 0;
for (let number = 2; number <= max; number++)
if (smartPrime(number)) {
primeCount++;
}
console.log(`Number of primes between 0 and ${max}: ${primeCount}`);
console.log(`Cache memory: ${smartPrime.length}`);
/* Ouput
Number of primes between 0 and 1000000: 78498
Cache memory: 999999
*/
view raw RunAwayCache.js hosted with ❤ by GitHub

OOPS! Every single value we test for prime becomes permanently cached.

Can we limit the number of entries in the cache? Well, we could stop inserting values after a certain number of entries but that would not be very useful as we would catch the least recently used (LRU) results. What we would probably want to do it use most recently used (MRU) results.

Earlier we used object for cache – cache: {} which happens to be a Map internally, making it easier for us to lookup keys in O(1) time. However, we cannot know the order in which keys were inserted into the map (cache object, in our case), hence, we will need to use another data structure which will help us with that – Linked List. Yep, JavaScript Arrays are like Linked List (push, pop, shift, unshift).

The next implementation of Memoize uses a List for MRU in form of
[ {args:2, result:true}, {args:3, result:true}, {args:4, result:false} ]
and so on. We will lose our O(1) time for lookup but at least we will get most recently used cache.

// 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)
return false;
return true;
}
// Memoize is a Proxy to the actual function
const memoize = (fn, mru=10) => new Proxy(fn,
// Handler with traps
{
// Instead of object, let's use a list which contains
// [ {args:2, result:true}, {args:3, result:true}, {args:4, result:false} ]
cache: [],
max: mru, // Our cache limit
// Our "magic" property
get(object, property, receiver) {
if (property == "cache")
return this.cache;
return Reflect.get(object, property, receiver);
},
// Intercept call to the wrapped function
apply(target, thisArg, args) {
// Scan the list to see if we have args cached
let exists = this.cache.find(element => {
element.args == args.toString();
});
// If exists, return the result
if (exists) {
result = exists.result;
} else {
// New result, store it at the end
result = Reflect.apply(target, thisArg, args);
this.cache.push({ args: args.toString(), result: result });
}
// Have we exceeded the limit? Drop the first element
if (this.cache.length > this.max)
this.cache.shift();
return result;
}
}
);
// Create the proxy and go thru max numbers to test for isPrime
let smartPrime = memoize(isPrime);
let max = 1000000;
let primeCount = 0;
for (let number = 2; number <= max; number++)
if (smartPrime(number)) {
primeCount++;
}
console.log(`Number of primes between 0 and ${max}: ${primeCount}`);
// Let's test 2 again
console.log("2 is prime", smartPrime(2));
console.log(`Cache size: ${smartPrime.cache.length}`);
console.log('Cache:', smartPrime.cache);
/* Output
Number of primes between 0 and 1000000: 78498
2 is prime true
Cache size: 10
Cache: [
{ args: '999992', result: false },
{ args: '999993', result: false },
{ args: '999994', result: false },
{ args: '999995', result: false },
{ args: '999996', result: false },
{ args: '999997', result: false },
{ args: '999998', result: false },
{ args: '999999', result: false },
{ args: '1000000', result: false },
{ args: '2', result: true }
]
*/
view raw MRUAsList.js hosted with ❤ by GitHub

This is cool! we not only have a Memoize Proxy, which can wrap any function to cache its results but we can also control the cache size so that we have most recently used list and conserve on memory size.

Sometimes, it makes sense to have MFU (Most Frequently Used) rather than MRU (Most Recently Used) cache. Just because we used 2 towards the end, it is kept in the list, whereas we may have tested 11 for prime 10 times, but because it was towards the beginning of the usage, it gets shifted out.

How about building an MFU Cache for our Memoize? Perhaps, next post?

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)

Build Memoize in JavaScript – Part II

In the previous post we built a memoize function, which caches the result of any pure function, thereby speeding up the execution when the result is already cachced.

Let’s try and improve our Memoize function.
There is an excellent object called Proxy, which wraps and JavaScript object and allows us to transparently intercept all its access.

First.. the Proxy object
Proxy is a wrapper to other objects and can intercept/trap access to object. This enables proxy to do things like validations, result manipulation and even inserting new “function”, which don’t exist in the object.

// Simple object
let person = {
id: 0,
name: "default",
}
// There is no validation if object is used directly
person.id = "Eich"; // We would like it to be positive integer
person.name = 3.14; // Name should ideally be non blank string
console.log(person);
// Let's setup Proxy handler with validations
const handler = {
set(object, property, value, receiver) {
// id should be positive integer
if (property == "id") {
if (typeof value != 'number' || value < 0)
throw "id should be a positive number";
}
// name should be a non blank string
if (property == "name") {
if (typeof value != 'string' || value.trim() == "")
throw "name should be a non blank string";
}
// Passed all validations, so assign to real object
return Reflect.set(object, property, value, receiver);
}
}
// Use a Proxy to person object
const PersonProxy = new Proxy(person, handler);
// These should give errors
PersonProxy.id = "Brendan";
PersonProxy.name = 1;
console.log(PersonProxy);
view raw SimpleProxy.js hosted with ❤ by GitHub


There! We are intercepting access to the object using a Proxy. While in this case we are trapping property setter, we can intercept other things as well. For example, call to the target function.

If we can intercept function call (e.g. isPrime), we can intercept the return value and cache it in the proxy, so next time if we find the same args, we don’t even have to call the target function and the proxy itself can return the cached value.

So, let’s rewrite our Memoize function as a Proxy

// 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;
}
// Memoize is a Proxy to the actual function
const memoize = fn => new Proxy(fn,
// Handler with traps
{
// We store previous results here
cache: {},
// Intercept call to the wrapped function
apply(target, thisArg, args) {
// Do we have result in Proxy itself?
if (!(args in this.cache))
this.cache[args] = Reflect.apply(target, thisArg, args);
return this.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)}`);
view raw MemoizeProxy.js hosted with ❤ by GitHub

There we have it! We are caching the result in the Proxy object itself and returning without calling the target function. Apart from function call, we can also intercept other access like property getter/setter or deletion. However, we don’t need that in this case.

However, both our Memoize implementation have one problem… Infinite caching for infinite time. What if the user checks one millions primes? What will happen to our cache? Yep, it would contain one million entries, which may or may not be used again.

We need to build smart cache along with our Memoize feature. Maybe next post?

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)

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)