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)

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 )

Google photo

You are commenting using your Google 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