Memoization is a powerful technique in programming to increase the efficiency of your code by caching the results of expensive function calls. This technique is particularly useful in JavaScript for functions that are called frequently with the same arguments. Today, I will walk you through implementing a generic memoization function in JavaScript and show its benefits using two example functions.
Implementing a generic memoize function
We need a function that takes a function as an argument and returns a new function that caches the results of the original function. The new function will check if the arguments have been called before and return the cached result if so. Otherwise, it will call the original function and cache the result.
function memoize<T extends (...args: any[]) => any>(func: T): T {
const cache: Record<string, ReturnType<T>> = {};
return function (...args: Parameters<T>): ReturnType<T> {
const key = JSON.stringify(args);
if (key in cache) {
console.log(`Fetching from cache for args: ${key}`);
console.time(`Computing time for args: ${key}`);
const result = cache[key];
console.timeEnd(`Computing time for args: ${key}`);
return result;
} else {
console.time(`Computing time for args: ${key}`);
const result = func(...args);
console.timeEnd(`Computing time for args: ${key}`);
cache[key] = result;
return result;
}
} as T;
}I’ve added timings to the console to show the difference in performance between the original function and the memoized function. The pattern at play here is to simply set a cache object outside of the returned function and check if the arguments have been called before. If so, return the cached result. Otherwise, call the original function and cache the result. The memoize function returns a new function that has access to the cache object and the original function.
Example 1: Add Pokemon
It’s a go to of mine to use Pokemon as an example whenever I start mapping out how a design pattern works, I think it’s because that game series has a whole load of different elements that can be used to show how a pattern works. So. Anyway. Pokemon: (I haven’t even played a Pokemon game since high school, seriously, wtf.)
function pokemeno(pokemon: string): string {
return `Details for ${pokemon}`;
}
const memoizedPokemeno = memoize(pokemeno);
console.log(memoizedPokemeno("Pikachu"));
console.log(memoizedPokemeno("Charizard"));
console.log(memoizedPokemeno("Pikachu"));Logging this will give something like these results:
Computing time for args: ["Pikachu"]: 0.045ms
Details for Pikachu
Computing time for args: ["Charizard"]: 0.004ms
Details for Charizard
Fetching from cache for args: ["Pikachu"]
Computing time for args: ["Pikachu"]: 0.002ms
Details for PikachuJust look at the performance gains.
Only kidding, that first call to Pikachu likely has a load of overhead, setting up the function, setting up the cache and so on so it will take a little longer. But the second call to Pikachu is much faster.
This is because the result is cached and the function doesn’t need to be called again.
Example 2: Power Set
I love a good power set. If you don’t know what a power set is, it is a set of all possible subsets of a set.
For example, the power set of the set {1, 2, 3} is {{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.
The power set of a set with n elements has 2^n elements. A power set is an algorithm with exponential complexity, defined as O(2n).
This is a great example of a function that can be optimised with memoization so let’s take a look at the code:
function powerSet(arr: number[]): number[][] {
const result = [[]];
for (const value of arr) {
const subsets = [];
for (const subset of result) {
subsets.push([...subset, value]);
}
result.push(...subsets);
}
return result;
}
const memoizedPowerSet = memoize(powerSet);
console.log("First call with [1, 2, 3]:");
console.log(memoizedPowerSet([1, 2, 3]));
console.log("Second call with [1, 2, 3]:");
console.log(memoizedPowerSet([1, 2, 3]));
console.log("Call with a larger set [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]:");
console.log(memoizedPowerSet([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]));
console.log("Repeat call with the larger set:");
console.log(memoizedPowerSet([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]));Calling this will give something like these results:
First call with [1, 2, 3]:
Computing time for args: [[1,2,3]]: 0.067ms
[
[], [ 1 ],
[ 2 ], [ 1, 2 ],
[ 3 ], [ 1, 3 ],
[ 2, 3 ], [ 1, 2, 3 ]
]
Second call with [1, 2, 3]:
Fetching from cache for args: [[1,2,3]]
Computing time for args: [[1,2,3]]: 0.005ms
[
[], [ 1 ],
[ 2 ], [ 1, 2 ],
[ 3 ], [ 1, 3 ],
[ 2, 3 ], [ 1, 2, 3 ]
]
Call with a larger set [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]:
Computing time for args: [[1,2,3,4,5,6,7,8,9,10]]: 0.199ms
[
[], [ 1 ], [ 2 ],
[ 1, 2 ], [ 3 ], [ 1, 3 ],
[ 2, 3 ], [ 1, 2, 3 ], [ 4 ],
[ 1, 4 ], [ 2, 4 ], [ 1, 2, 4 ],
[ 3, 4 ], [ 1, 3, 4 ], [ 2, 3, 4 ],
[ 1, 2, 3, 4 ], [ 5 ], [ 1, 5 ],
[ 2, 5 ], [ 1, 2, 5 ], [ 3, 5 ],
[ 1, 3, 5 ], [ 2, 3, 5 ], [ 1, 2, 3, 5 ],
[ 4, 5 ], [ 1, 4, 5 ], [ 2, 4, 5 ],
[ 1, 2, 4, 5 ], [ 3, 4, 5 ], [ 1, 3, 4, 5 ],
[ 2, 3, 4, 5 ], [ 1, 2, 3, 4, 5 ], [ 6 ],
[ 1, 6 ], [ 2, 6 ], [ 1, 2, 6 ],
[ 3, 6 ], [ 1, 3, 6 ], [ 2, 3, 6 ],
[ 1, 2, 3, 6 ], [ 4, 6 ], [ 1, 4, 6 ],
[ 2, 4, 6 ], [ 1, 2, 4, 6 ], [ 3, 4, 6 ],
[ 1, 3, 4, 6 ], [ 2, 3, 4, 6 ], [ 1, 2, 3, 4, 6 ],
[ 5, 6 ], [ 1, 5, 6 ], [ 2, 5, 6 ],
[ 1, 2, 5, 6 ], [ 3, 5, 6 ], [ 1, 3, 5, 6 ],
[ 2, 3, 5, 6 ], [ 1, 2, 3, 5, 6 ], [ 4, 5, 6 ],
[ 1, 4, 5, 6 ], [ 2, 4, 5, 6 ], [ 1, 2, 4, 5, 6 ],
[ 3, 4, 5, 6 ], [ 1, 3, 4, 5, 6 ], [ 2, 3, 4, 5, 6 ],
[ 1, 2, 3, 4, 5, 6 ], [ 7 ], [ 1, 7 ],
[ 2, 7 ], [ 1, 2, 7 ], [ 3, 7 ],
[ 1, 3, 7 ], [ 2, 3, 7 ], [ 1, 2, 3, 7 ],
[ 4, 7 ], [ 1, 4, 7 ], [ 2, 4, 7 ],
[ 1, 2, 4, 7 ], [ 3, 4, 7 ], [ 1, 3, 4, 7 ],
[ 2, 3, 4, 7 ], [ 1, 2, 3, 4, 7 ], [ 5, 7 ],
[ 1, 5, 7 ], [ 2, 5, 7 ], [ 1, 2, 5, 7 ],
[ 3, 5, 7 ], [ 1, 3, 5, 7 ], [ 2, 3, 5, 7 ],
[ 1, 2, 3, 5, 7 ], [ 4, 5, 7 ], [ 1, 4, 5, 7 ],
[ 2, 4, 5, 7 ], [ 1, 2, 4, 5, 7 ], [ 3, 4, 5, 7 ],
[ 1, 3, 4, 5, 7 ], [ 2, 3, 4, 5, 7 ], [ 1, 2, 3, 4, 5, 7 ],
[ 6, 7 ], [ 1, 6, 7 ], [ 2, 6, 7 ],
[ 1, 2, 6, 7 ],
... 924 more items
]
Repeat call with the larger set:
Fetching from cache for args: [[1,2,3,4,5,6,7,8,9,10]]
Computing time for args: [[1,2,3,4,5,6,7,8,9,10]]: 0.006ms
[
[], [ 1 ], [ 2 ],
[ 1, 2 ], [ 3 ], [ 1, 3 ],
[ 2, 3 ], [ 1, 2, 3 ], [ 4 ],
[ 1, 4 ], [ 2, 4 ], [ 1, 2, 4 ],
[ 3, 4 ], [ 1, 3, 4 ], [ 2, 3, 4 ],
[ 1, 2, 3, 4 ], [ 5 ], [ 1, 5 ],
[ 2, 5 ], [ 1, 2, 5 ], [ 3, 5 ],
[ 1, 3, 5 ], [ 2, 3, 5 ], [ 1, 2, 3, 5 ],
[ 4, 5 ], [ 1, 4, 5 ], [ 2, 4, 5 ],
[ 1, 2, 4, 5 ], [ 3, 4, 5 ], [ 1, 3, 4, 5 ],
[ 2, 3, 4, 5 ], [ 1, 2, 3, 4, 5 ], [ 6 ],
[ 1, 6 ], [ 2, 6 ], [ 1, 2, 6 ],
[ 3, 6 ], [ 1, 3, 6 ], [ 2, 3, 6 ],
[ 1, 2, 3, 6 ], [ 4, 6 ], [ 1, 4, 6 ],
[ 2, 4, 6 ], [ 1, 2, 4, 6 ], [ 3, 4, 6 ],
[ 1, 3, 4, 6 ], [ 2, 3, 4, 6 ], [ 1, 2, 3, 4, 6 ],
[ 5, 6 ], [ 1, 5, 6 ], [ 2, 5, 6 ],
[ 1, 2, 5, 6 ], [ 3, 5, 6 ], [ 1, 3, 5, 6 ],
[ 2, 3, 5, 6 ], [ 1, 2, 3, 5, 6 ], [ 4, 5, 6 ],
[ 1, 4, 5, 6 ], [ 2, 4, 5, 6 ], [ 1, 2, 4, 5, 6 ],
[ 3, 4, 5, 6 ], [ 1, 3, 4, 5, 6 ], [ 2, 3, 4, 5, 6 ],
[ 1, 2, 3, 4, 5, 6 ], [ 7 ], [ 1, 7 ],
[ 2, 7 ], [ 1, 2, 7 ], [ 3, 7 ],
[ 1, 3, 7 ], [ 2, 3, 7 ], [ 1, 2, 3, 7 ],
[ 4, 7 ], [ 1, 4, 7 ], [ 2, 4, 7 ],
[ 1, 2, 4, 7 ], [ 3, 4, 7 ], [ 1, 3, 4, 7 ],
[ 2, 3, 4, 7 ], [ 1, 2, 3, 4, 7 ], [ 5, 7 ],
[ 1, 5, 7 ], [ 2, 5, 7 ], [ 1, 2, 5, 7 ],
[ 3, 5, 7 ], [ 1, 3, 5, 7 ], [ 2, 3, 5, 7 ],
[ 1, 2, 3, 5, 7 ], [ 4, 5, 7 ], [ 1, 4, 5, 7 ],
[ 2, 4, 5, 7 ], [ 1, 2, 4, 5, 7 ], [ 3, 4, 5, 7 ],
[ 1, 3, 4, 5, 7 ], [ 2, 3, 4, 5, 7 ], [ 1, 2, 3, 4, 5, 7 ],
[ 6, 7 ], [ 1, 6, 7 ], [ 2, 6, 7 ],
[ 1, 2, 6, 7 ],
... 924 more items
]It’s a fairly contrived example, but it shows the power of memoization.
The first call to the function takes a little longer, but the second call is much faster.
The third call is even faster, even though it is a larger set.
This is because the result is cached and the function doesn’t need to be called again.
Example 3 (Bonus): Fibonacci
Ah, Fibonnaci. What foray into programming would be complete without a Fibonacci example?
I’m not going to go into the details of the Fibonacci sequence, but it is a great example of a function that can be optimised with memoization.
Let’s take a look at the code:
function fibonacci(n: number): number {
if (n <= 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
const memoizedFibonacci = memoize(fibonacci);
console.log("First call with 10:");
console.log(memoizedFibonacci(10));
console.log("Second call with 10:");
console.log(memoizedFibonacci(10));
console.log("Call with a larger number 40:");
console.log(memoizedFibonacci(40));
console.log("Repeat call with the larger number:");
console.log(memoizedFibonacci(40));Running this should yield results similar to:
First call with 10:
Computing time for args: [10]: 0.091ms
55
Second call with 10:
Fetching from cache for args: [10]
Computing time for args: [10]: 0.002ms
55
Call with a larger number 40:
Computing time for args: [40]: 775.169ms
102334155
Repeat call with the larger number:
Fetching from cache for args: [40]
Computing time for args: [40]: 0.003ms
102334155As you can see, by the time we are calling the function with a larger number, the performance gains are huge. The first call to fibonacci(40) takes 775.169ms, but the second call takes only 0.003ms.
This is because the result is cached and the function doesn’t need to be called again.
These kinds of caching algorithms are in use all over the place and you likely don’t realise that the magic sauce under these kinds of functions is memoization.
It’s a great tool to have in your toolbelt and can be used to optimise a whole load of different functions. If you’ve used hooks such as useMemo or useCallback in React, you’ve used memoization.
If you’ve used reselect in Redux, you’ve used memoization. If you’ve used lodash.memoize, you’ve used memoization. It’s a powerful tool that can be used to optimise a whole load of different functions and now you know how to roll your own!
Thanks for reading, and happy coding!