💾memoize(f)
make a function/method "remember" its return values.
JS ⟩ technique ⟩ memoize ⟩ by decorator ⟩ 💾 memoize(f)
(a decorator)
make a function/method "remember" it's return values.
replit:memoize(f)
// ⭐️ caching decorator for memoization
// memoize (multi-argument) function/method
function memoize(f, {
// ⭐️ default hash function: (join all arguments)
// ex: 1,2,3 --> '1,2,3' (string as key)
hash = (...args) => args.join(),
// ⭐️ log caching details
log = true,
}={}) {
// ⭐️ prepare cache to store return values of f
let cache = new Map();
// ⭐️ decorated function
// -------------------------------------------------
// ⭐️ must use "function expression".
// ❗ "arrow function" won't do for a method.
return function(...args) {
// ⭐️ get hashed key from arguments
let key = hash(args);
if (log) console.log(`${f.name}(${key})`);
// ⭐️ if already cached, return the cached value immediately.
if (cache.has(key)) {
let value = cache.get(key);
if (log) console.log(` • cache: get f(${key}) → ${value}`);
return value;
}
// ⭐️ otherwise: 1. evaluate 2. cache 3. return.
// ❗ must pass `this` context to `f` if `f` is method
let value = f.call(this, ...args); // 1.
cache.set(key, value); // 2.
if (log) console.log(` • cache: set f(${key}) ← ${value}`);
return value; // 3.
};
}
// export
module.exports = { memoize };
// index.js
const { log } = console;
const { memoize } = require('./memoize.js');
// case 1: object with method
// ----------------------------------------------
let worker = {
// ⭐️ a "slow" method
slow(a, b) {
// ... massive computation
return a + b;
}
};
// ⭐️ "memoize" and "reassign" the method
// ❗ `this` remains "unbound" here.
worker.slow = memoize(worker.slow, {log: true});
// case 2: factorial
// ----------------------------------------------
function factorial(n) {
// base case:
if (n < 2) return 1;
// recursive case:
return n * factorial(n-1);
}
// ⭐️ "memoize" and "reassign" the function
factorial = memoize(factorial);
[
// ❗ `this` === worker (bound at runtime)
worker.slow(3, 5), // 8
worker.slow(1, 2), // 3
worker.slow(3, 5), // 8
factorial(4), // 24
factorial(5), // 120
factorial(3), // 6
].forEach(x => log(x));
// log
// ---------------------------
// slow(3,5)
// • cache: set f(3,5) ← 8
// slow(1,2)
// • cache: set f(1,2) ← 3
// slow(3,5)
// • cache: get f(3,5) → 8
// factorial(4)
// factorial(3)
// factorial(2)
// factorial(1)
// • cache: set f(1) ← 1
// • cache: set f(2) ← 2
// • cache: set f(3) ← 6
// • cache: set f(4) ← 24
// factorial(5)
// factorial(4)
// • cache: get f(4) → 24
// • cache: set f(5) ← 120
// factorial(3)
// • cache: get f(3) → 6
Last updated