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.
Write memoize(fn). It returns a function that calls fn with the same arguments and returns its result, but remembers every result: a later call with the same arguments returns the remembered result without calling fn again.
Two calls count as the same when they have the same number of arguments and each argument matches the one in the same position, compared the way a Map compares keys: 1 and "1" are different, two objects with the same contents are different, and an object is always the same as itself.
Results of undefined are remembered too. Each memoized function has its own cache.
const add = memoize((a, b) => {
console.log("adding", a, b);
return a + b;
});
add(1, 2); // logs "adding 1 2", returns 3
add(1, 2); // returns 3, logs nothing
add(1, 3); // logs "adding 1 3": different arguments
add("1", 2); // logs "adding 1 2" again and returns "12": "1" isn't 1
const fn = spy((a, b) => a + b);
const add = memoize(fn);
expect(add(1, 2)).toBe(3);
expect(add(1, 2)).toBe(3);
expect(add(1, 2)).toBe(3);
expect(fn).toHaveBeenCalledTimes(1);
const fn = spy((a, b) => a + b);
const add = memoize(fn);
expect(add(1, 2)).toBe(3);
expect(add(1, 3)).toBe(4);
expect(fn).toHaveBeenCalledTimes(2);
const fn = spy((x) => typeof x);
const kind = memoize(fn);
expect(kind(1)).toBe("number");
expect(kind("1")).toBe("string");
const fn = spy((...args) => args.length);
const count = memoize(fn);
expect(count("a,b")).toBe(1);
expect(count("a", "b")).toBe(2);
const fn = spy((user) => user.name);
const getName = memoize(fn);
const ada = { name: "Ada" };
getName(ada);
getName(ada);
expect(fn).toHaveBeenCalledTimes(1);
getName({ name: "Ada" });
expect(fn).toHaveBeenCalledTimes(2);
const fn = spy((...args) => args.length);
const count = memoize(fn);
expect(count(1)).toBe(1);
expect(count(1, undefined)).toBe(2);
expect(count()).toBe(0);
const fn = spy(() => undefined);
const nothing = memoize(fn);
nothing("x");
nothing("x");
expect(fn).toHaveBeenCalledTimes(1);
const double = memoize((x) => x * 2);
const square = memoize((x) => x * x);
expect(double(5)).toBe(10);
expect(square(5)).toBe(25);
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. 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.