Memoization means saving a function's result for the arguments it was called with, so that calling it again with the same arguments returns the saved result instead of running the function again. The saved results are the function's cache. When a call finds its result there, that's a cache hit; when it doesn't, it's a miss, and the function runs and its result is saved. Memoizing trades memory for time, so it pays off for functions that are slow and get called with the same arguments again and again.
It's like writing the answer to a long sum in the margin, so the next time someone asks, you read it off instead of working it out. Take countPrimes(n), which counts the prime numbers below n and is slow when n is large. Here's what a memoized version does over four calls, next to a lighter variant that remembers only its most recent call:
| Call | Memoized: remembers every call | Remembers only the last call |
|---|---|---|
countPrimes(1000000) | Miss: runs, returns 78498, and saves it. | Miss: runs, returns 78498, and saves it. |
countPrimes(1000000) | Hit: returns the saved 78498 without running. | Hit: returns the saved 78498 without running. |
countPrimes(2000000) | Miss: runs, returns 148933, and saves it too. | Miss: runs, returns 148933, and saves it in place of 78498. |
countPrimes(1000000) | Hit: 78498 is still saved. | Miss: only the result for 2000000 is saved, so it runs again. |
Every saved result, with the arguments it was saved for, stays in memory until the cache lets go of it, and a cache that never does grows with every new argument. Memoize helpers deal with that in different ways: some let you clear the cache, some cap its size and drop the least recently used result when it's full, and the variant in the last column keeps only one. That one suits a value recomputed again and again from inputs that rarely change. React's useMemo works that way: it keeps the value from the last render and recomputes it only when one of its dependencies has changed.
A cache finds results by a key worked out from the arguments. Lodash's _.memoize uses the first argument as the key unless you pass a resolver, a function that turns the arguments into a key. Without one, a memoized power(base, exponent) called as power(2, 3) and then power(2, 10) returns 8 both times: both calls have the key 2. Lodash compares keys the way a Map does, so an object matches only the very same object: a different object with the same contents is a miss, and changing an object's contents doesn't make it miss. Other helpers build the key from every argument.
Only memoize pure functions: ones whose result depends on nothing but their arguments, and that don't change anything outside themselves. A hit skips the function entirely. If getPrice(id) reads a price that has since changed, the memoized version keeps returning the old one, and a function that logs something or sends a request doesn't do it on a hit.
For an async function, the result is a promise, so the promise is what gets saved. A second call with the same arguments gets the same promise, even while it's still pending, so two parts of a page asking for the same user share one request. A promise that rejects would be saved too, and every later call would get the same failure, unless the cache forgets keys whose promise rejects.
Besides useMemo, you meet memoization in React's memo, which skips re-rendering a component whose props haven't changed, in selector libraries such as Reselect, and in recursive algorithms that would otherwise solve the same smaller problem many times.
A cache keeps results you've already worked out, so asking for them again is fast: the return value of a slow function, a response you fetched, an image you decoded. Memory isn't free, so a cache has a capacity, the most entries it may hold. When it's full and a new entry arrives, an old one has to go. Throwing an entry out to make room is called evicting it.
LRU stands for least recently used. An LRU cache evicts the entry that has gone untouched the longest, where touching an entry means reading it or writing it. The bet is that what you used a moment ago you'll want again soon, and what you haven't touched in a while you probably won't.
Picture a desk with room for two books. Whenever you open a book, it goes on top of the pile. When you need a third book and the desk is full, the one at the bottom, the one you haven't opened for the longest, goes back on the shelf.
Here's a cache with room for two entries. The middle column lists what it holds after each step, most recently used first:
| Step | The cache after it | Why |
|---|---|---|
Add a | a | There's room. |
Add b | b, a | The newest entry is the most recently used. |
Read a | a, b | Reading a makes it the most recently used, so b is now the oldest. |
Add c | c, a | The cache is full, so b, the least recently used, is evicted. |
Read b | c, a | A miss: b was evicted, so there's nothing to return, and nothing moves. |
Change a's value | a, c | Writing counts as a use too. a was already there, so nothing is evicted. |
Look at the third step. Had a not been read, a would have been the oldest entry and been evicted instead of b. That's what makes it least recently used rather than first in, first out: every use moves an entry back to the front of the line.
You meet LRU caches wherever memory is limited and the same things get asked for again: memoized functions that would otherwise grow forever, caches of fetched data or decoded images, and the popular npm package lru-cache.
Write memoize(fn, options). It returns a function that caches fn's results by key. options is optional, and so are both of its fields, resolver and maxSize.
The key is resolver(...args), called with the same this and arguments as the memoized function. Without a resolver, the key is the first argument. Keys are compared the way a Map compares them.
On a miss, call fn with the caller's this and all the arguments, cache the result (even undefined), and return it. On a hit, return the cached result without calling fn.
maxSize, a positive whole number, is the most results the cache may hold. When a new key arrives and the cache is full, first drop the least recently used entry: the one whose key was last stored or hit longest ago. Without maxSize, the cache has no limit.
const getUser = memoize((id) => ({ id }), { maxSize: 2 });
getUser(1);
getUser(2);
getUser(1); // hit: 1 is now the most recently used
getUser(3); // the cache is full, so 2 is dropped
getUser(2); // miss: fn runs again
const area = memoize((w, h) => w * h, { resolver: (w, h) => w + "x" + h });
area(2, 3); // 6
area(2, 4); // 8: a different key
const fn = spy((a, b) => a + b);
const add = memoize(fn);
expect(add(1, 2)).toBe(3);
expect(add(1, 99)).toBe(3);
expect(fn).toHaveBeenCalledTimes(1);
const fn = spy((user) => user.name.toUpperCase());
const shout = memoize(fn, { resolver: (user) => user.id });
expect(shout({ id: 1, name: "ada" })).toBe("ADA");
expect(shout({ id: 1, name: "someone else" })).toBe("ADA");
expect(shout({ id: 2, name: "alan" })).toBe("ALAN");
expect(fn).toHaveBeenCalledTimes(2);
const resolver = spy((w, h) => w + "x" + h);
const obj = { area: memoize((w, h) => w * h, { resolver }) };
expect(obj.area(2, 3)).toBe(6);
expect(resolver.calls[0].args).toEqual([2, 3]);
expect(resolver.calls[0].this).toBe(obj);
const fn = spy(function (a, b) {
return this.base + a + b;
});
const obj = { base: 10, sum: memoize(fn) };
expect(obj.sum(1, 2)).toBe(13);
expect(fn.calls[0].this).toBe(obj);
expect(fn.calls[0].args).toEqual([1, 2]);
const fn = spy((x) => typeof x);
const kind = memoize(fn);
expect(kind(1)).toBe("number");
expect(kind("1")).toBe("string");
kind({});
kind({});
expect(fn).toHaveBeenCalledTimes(4);
const fn = spy(() => undefined);
const nothing = memoize(fn);
nothing("a");
nothing("a");
expect(fn).toHaveBeenCalledTimes(1);
const fn = spy((n) => n * 10);
const times10 = memoize(fn, { maxSize: 2 });
times10(1);
times10(2);
times10(3);
expect(fn).toHaveBeenCalledTimes(3);
times10(2);
times10(3);
expect(fn).toHaveBeenCalledTimes(3);
times10(1);
expect(fn).toHaveBeenCalledTimes(4);
const fn = spy((n) => n * 10);
const times10 = memoize(fn, { maxSize: 2 });
times10(1);
times10(2);
times10(1);
times10(3);
expect(fn).toHaveBeenCalledTimes(3);
times10(1);
expect(fn).toHaveBeenCalledTimes(3);
times10(2);
expect(fn).toHaveBeenCalledTimes(4);
const fn = spy((n) => n);
const same = memoize(fn);
for (let i = 0; i < 1000; i++) same(i);
for (let i = 0; i < 1000; i++) same(i);
expect(fn).toHaveBeenCalledTimes(1000);
Run tests runs every test on your code, here in your browser. The problem is solved when they all pass.
Ctrl + Enter runs the tests (⌘ + Enter on a Mac).
I'm here to help with Memoize with a key resolver and size limit. I give hints, never the solution, so you get to solve it yourself. Ask for a hint, select code to ask about it, or press Ask Tuto why on a failing test.
Your first 3 answers need no account. for free to keep asking.