Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
/**
* 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);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment