Memoization
Learn to memoize an expensive function by caching its results.
Memoization
Memoization remembers the result of an expensive function and, when the same input arrives again, returns the cached value instead of recomputing. You can use a Map or a plain object as the cache.
A cache lookup that finds the value is a cache hit; one that does not is a cache miss. On a miss the function runs and its result is stored; on a hit the function is skipped.
Exercise Memoize function
Write a function named memoize. It takes fn and returns a cached wrapper. The wrapper uses a Map for the cache; args.join("|") works as the key.
Show example solution
Create a Map cache; check with has, return with get, store with set.
Example solution:
function memoize(fn) {
const cache = new Map();
return function(...args) {
const key = args.join("|");
if (cache.has(key)) return cache.get(key);
const result = fn(...args);
cache.set(key, result);
return result;
};
}Pure functions
Memoization only works on pure functions — functions that always return the same output for the same input. Caching a function that depends on the date, a random number, or an external source will produce wrong results.
Before memoizing, make sure the function is side-effect free and deterministic.
Test yourself
-
Cache lookup
if (cache.____) return cache.get(key);Show answer
if (cache.has(key)) return cache.get(key); -
Which function is suitable for memoization?
- A random number generator
- A function varying by date
- A database fetch function
- A function returning the same result for the same input
Show answer
A function returning the same result for the same input — Correct! Pure, deterministic functions are good candidates for memoization.
-
Match the cache terms
- cache hit
- found in cache
- cache miss
- not in cache
- pure function
- same input, same output
- cache key
- cache lookup key