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)

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