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)

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