Memoization and caching are foundational concepts in programming.
You want to understand memoization, so you can understand concepts that build upon memoization. For example, the memo higher-order component in React, useCallback and useMemo hooks in React, selectors in Redux and much more.
In this article and video, you're going to get a detailed look into memoization with examples in JavaScript and TypeScript.
Memoization is a way to speed up performance by reducing computations.
When you first calculate a result, you save it. If you need the result for the same arguments again, you use the saved result instead of recalculating.
And there are two ways that you can implement memoization:
Implicit caching is when you manually implement caching logic within functions.
Let's say you have a simple add function and you want to memoize it.
function add(a, b) {
return a + b;
}You can rewrite this add function, so that it memoizes its results.
If you want to code along with this article, initialize a new npm project.
npm init --yThen write a function called memoizeAdd().
function memoizeAdd() {
const cache = {};
return function memoizedAdd(a, b) {
const key = `${a},${b}`;
if (key in cache) {
return cache[key];
} else {
const result = a + b;
cache[key] = result;
return result;
}
};
}
const memoizedAdd = memoizeAdd();
console.log(memoizedAdd(3, 4)); // Computes and caches the result.
console.log(memoizedAdd(3, 4)); // Retrieves the result from cache.
console.log(memoizedAdd(5, 6)); // Computes and caches a new result.
console.log(memoizedAdd(3, 4)); // Still retrieves the result from cache.
Let's break down what's happening here.
In memoizeAdd() you create a cache, which is typically a hash table or an object, where you store the results of function calls. Each entry uses the function's input as the key and the output as the value.
const cache = {
'3,1': 4,
'9001,2012': 11_013,
};
Next, you return the memoizedAdd function, which takes in two numbers a and b.
Each unique combination of arguments corresponds to a key.
Before executing the main logic, the function checks the cache using the current input as the key. If the input is in the cache, it returns the cached result.
If the input is missing in the cache, the function computes the result, stores it in the cache, and then returns the result.
When you call the memoizedAdd function, the result is stored together with its parameters. If you call it again with the same parameters, the result comes from the cache. If the parameters are new, the function computes the result again.
When you run this code, you get the following output.
$ node implicit-caching.js
7
7
11
7
In languages that support higher-order functions, you can use decorators to add memoization without changing the function's core logic.
Higher-order functions are functions that take in functions and return functions.
If this concept is new to you, you might want to read "Unleash JavaScript's Potential with Functional Programming". This article explains higher-order functions and much more from first principles.
Now, check out this simple example of a decorator function for memoization.
function memoize(fn) {
const cache = new Map();
return function(...args) {
const key = JSON.stringify(args);
if (cache.has(key)) {
return cache.get(key);
}
const result = fn.apply(this, args);
cache.set(key, result);
return result;
};
}
function add(a, b) {
return a + b;
}
const memoizedAdd = memoize(add);
console.log(memoizedAdd(3, 4)); // Calculates and caches the result.
console.log(memoizedAdd(3, 4)); // Returns the cached result.
console.log(memoizedAdd(5, 6)); // Computes and caches a new result.
console.log(memoizedAdd(3, 4)); // Still retrieves the result from cache.
Let's go through this code step by step, too.
First, you create a memoize function that takes another function, fn, as its argument.
It starts by initializing a cache using a Map. This cache will store the results of the function calls. A Map is used instead of an object because it can handle a wider variety of key types.
const cache = new Map();
// Use numbers as key for cache.
map.set('[3,1]', 4);
// Use functions as key for cache.
map.set('[function increment(), function double()]', 42);
The returned function accepts any number of arguments. It serializes these arguments into a string to use as a key for the cache.
Before executing the original function, the wrapper checks if the key already exists in the cache. If it does, the function returns the cached result.
If the key is missing in the cache, the wrapper calls the original function using fn.apply(this, args). It stores the result in the cache and returns it.
You can now memoize your add function by passing it to the memoize function.
The memoizedAdd function will work just like in the implicit caching example.
And running your code yields the same result.
$ node decorator-function.js
7
7
11
7
The add function is computationally cheap.
To experience the benefits of memoization, you need to memoize an expensive function.
A classic example is the fibonacci function. Outside of memoization, learning about this function is useful because it's a common topic in coding interviews.
The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones. It usually starts with 0 and 1. Here's how it begins:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
In mathematical terms, you can express this as:
Here's what the fibonacci function looks like in JavaScript.
function fibonacci(n) {
if (n <= 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
If n is 0 or 1, the function returns n directly. These are the first two numbers in the Fibonacci sequence.
For values of n greater than 1, the function calls itself twice: once for fibonacci(n - 1) and once for fibonacci(n - 2), and adds the results of these two calls.
Here's a table showing how the function computes fibonacci(4):
You can see that fibonacci(2) is calculated twice when calling fibonacci(4): once directly from fibonacci(4) and again from fibonacci(3).
The negative performance impacts of these redundant calculations compound as the input to the fibonacci function increases. You want to read this article until the end to learn how memoization can make this computation lightning fast.
Before memoizing your fibonacci function, add a name property to your memoized function. This makes stack tracing easier if your function throws an error.
function memoize(fn) {
const cache = new Map();
function memoizedFunction(...args) {
const key = JSON.stringify(args);
if (cache.has(key)) {
return cache.get(key);
}
const result = fn.apply(this, args);
cache.set(key, result);
return result;
}
Object.defineProperty(memoizedFunction, 'name', {
value: `memoized_${fn.name}`,
configurable: true
});
return memoizedFunction;
}
Use Object.defineProperty to set the name property of the memoizedFunction to a more descriptive value, like memoized_${fn.name}, where fn.name is the name of the original function. By setting this property to be configurable, you allow further modifications or deletion of the property if necessary.
Now you’re ready to measure the impact of memoization. Memoize your fibonacci function and time how long it takes to calculate large numbers.
function memoize(fn) {
const cache = new Map();
function memoizedFunction(...args) {
const key = JSON.stringify(args);
if (cache.has(key)) {
return cache.get(key);
}
const result = fn.apply(this, args);
cache.set(key, result);
return result;
}
Object.defineProperty(memoizedFunction, 'name', {
value: `memoized_${fn.name}`,
configurable: true
});
return memoizedFunction;
}
function fibonacci(n) {
if (n <= 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
const memoizedFibonacci = memoize(fibonacci);
function measurePerformance(func, arg) {
const startTime = process.hrtime.bigint();
const result = func(arg);
const endTime = process.hrtime.bigint();
// Convert nanoseconds to milliseconds.
const duration = (endTime - startTime) / BigInt(1000000);
console.log(`${func.name}(${arg}) = ${result}, Time: ${duration}ms`);
}
const n = 42;
console.log("Starting performance measurement:");
measurePerformance(fibonacci, n);
measurePerformance(memoizedFibonacci, n);
// Second call to show caching effect.
measurePerformance(memoizedFibonacci, n);
The measurePerformance function evaluates and reports the execution time of a given function by capturing start and end times with process.hrtime.bigint(), which provides precise timestamps in nanoseconds. After executing the function with a given argument, it calculates the duration in milliseconds by subtracting the start time from the end time and converting the result from nanoseconds. It then logs the function name, argument, output, and execution duration to the console.
Using measurePerformance, you can compare the performance of the standard Fibonacci function with the memoized version.
Here are the results for the performance measurements.
$ node fibonacci.js
Starting performance measurement:
fibonacci(42) = 267914296, Time: 2405ms
memoized_fibonacci(42) = 267914296, Time: 2394ms
memoized_fibonacci(42) = 267914296, Time: 0ms
As you can see, running the memoized version the second time is instant because the result is retrieved from the cache.
When you use memoization, you want to implement .clear() method to manage your application's resources and performance. Here's why:
Now, add the ability to clear the cache.
function memoize(fn) {
const cache = new Map();
function memoizedFunction(...args) {
const key = JSON.stringify(args);
if (cache.has(key)) {
return cache.get(key);
}
const result = fn.apply(this, args);
cache.set(key, result);
return result;
}
memoizedFunction.clear = function clear() {
cache.clear();
};
Object.defineProperty(memoizedFunction, 'name', {
value: `memoized_${fn.name}`,
configurable: true
});
return memoizedFunction;
}
function fibonacci(n) {
if (n <= 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
const memoizedFibonacci = memoize(fibonacci);
function measurePerformance(func, arg) {
const startTime = process.hrtime.bigint();
const result = func(arg);
const endTime = process.hrtime.bigint();
// Convert nanoseconds to milliseconds.
const duration = (endTime - startTime) / BigInt(1000000);
console.log(`${func.name}(${arg}) = ${result}, Time: ${duration}ms`);
}
const n = 42;
// Measure memoized Fibonacci.
measurePerformance(memoizedFibonacci, n);
// Measure memoized Fibonacci second call.
measurePerformance(memoizedFibonacci, n);
// Clear cache and measure again.
console.log('Clearing cache and measuring again:');
memoizedFibonacci.clear();
measurePerformance(memoizedFibonacci, n);
Then modify your usage example to include a call of the .clear() method after the result has already been memoized successfully.
$ node fibonacci.js
memoized_fibonacci(42) = 267914296, Time: 2456ms
memoized_fibonacci(42) = 267914296, Time: 0ms
Clearing cache and measuring again:
memoized_fibonacci(42) = 267914296, Time: 2484ms
As you can see, clearing the cache causes the function to compute its result again.
So far, all code has been written in JavaScript. Now you will translate the code examples into TypeScript.
Install TypeScript and the node types.
$ npm i --save-dev typescript @types/node
added 3 packages, and audited 4 packages in 1s
found 0 vulnerabilities
Then initialize a new TypeScript project.
$ npx tsc --init
Created a new tsconfig.json with:
TS
target: es2016
module: commonjs
strict: true
esModuleInterop: true
skipLibCheck: true
forceConsistentCasingInFileNames: true
You can learn more at <https://aka.ms/tsconfig>
Now you can write your memoize function in TypeScript.
type AnyFunction = (...args: any[]) => any;
interface MemoizedFunction<T extends AnyFunction> extends CallableFunction {
(...args: Parameters<T>): ReturnType<T>;
clear: () => void;
}
function memoize<T extends AnyFunction>(fn: T): MemoizedFunction<T> {
const cache = new Map<string, ReturnType<T>>();
const memoizedFunction = function(...args: Parameters<T>): ReturnType<T> {
const key = JSON.stringify(args);
if (cache.has(key)) {
return cache.get(key)!;
}
const result = fn(...args);
cache.set(key, result);
return result;
} as MemoizedFunction<T>;
memoizedFunction.clear = function clear() {
cache.clear();
};
Object.defineProperty(memoizedFunction, 'name', {
value: `memoized_${fn.name}`,
configurable: true
});
return memoizedFunction;
}
function fibonacci(n: number): number {
if (n <= 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
const memoizedFibonacci = memoize(fibonacci);
function measurePerformance(func: MemoizedFunction<typeof fibonacci>, arg: number) {
const startTime = process.hrtime.bigint();
const result = func(arg);
const endTime = process.hrtime.bigint();
// Convert nanoseconds to milliseconds.
const duration = (endTime - startTime) / BigInt(1000000);
console.log(`${func.name}(${arg}) = ${result}, Time: ${duration}ms`);
}
const n = 42;
// Measure memoized Fibonacci.
measurePerformance(memoizedFibonacci, n);
// Measure memoized Fibonacci second call.
measurePerformance(memoizedFibonacci, n);
// Clear cache and measure again.
memoizedFibonacci.clear();
measurePerformance(memoizedFibonacci, n);
Here, you create an AnyFunction type, which represents a generic function type in TypeScript. This type is flexible and allows for any function that takes an arbitrary number of arguments of any type and returns any type.
Next, you define a generic MemoizedFunction interface that extends the built-in CallableFunction interface and introduces a clear method. Here, T is a generic type parameter constrained to any function that matches the AnyFunction type. The interface ensures that your memoized function behaves like the original function in terms of accepting the same parameters and returning the same type and additionally exposes the clear method.
You can now implement your memoize function so that it returns the MemoizedFunction interface. Using the as keyword, you can let TypeScript know that the returned function is a MemoizedFunction.
Now when you hover over memoizedFibonacci, TypeScript knows the correct type of the function.
const memoizedFibonacci: MemoizedFunction<(n: number) => number>
And TypeScript also knows about the .clear() method on the memoized function.
(property) MemoizedFunction<(n: number) => number>.clear: () => void
Your function still has a shortcoming. Currently, the memoization only caches the results of the full function call for each argument, but does NOT cache the results of the intermediate recursive calls.
What is a potential drawback of using recursion without memoization for solving certain problems?
It is the significant increase in computational time and resource usage due to redundant calculations.
Call the function with a big number n and then with n + 1.
// ... previous code stays the same.
const n = 42;
measurePerformance(memoizedFibonacci, n);
measurePerformance(memoizedFibonacci, n + 1);
Then run your code to see the difference in performance between 42 and 43.
$ npx tsx example-5.ts
memoized_fibonacci(42) = 267914296, Time: 2442ms
memoized_fibonacci(43) = 433494437, Time: 3975ms
As you can see, fibonacci(43) takes much longer because it recalculates fibonacci(42) from scratch, even though the result is already cached. The same problem occurs with every other intermediate recursive call.
You can fix this by using memoization in the implementation of the fibonacci function.
// ... `memoize` is the same as above.
function fibonacci(n: number): number {
if (n <= 1) {
return n;
}
return memoizedFibonacci(n - 1) + memoizedFibonacci(n - 2);
}
const memoizedFibonacci = memoize(fibonacci);
function measurePerformance(func: MemoizedFunction<typeof fibonacci>, arg: number) {
const startTime = process.hrtime.bigint();
const result = func(arg);
const endTime = process.hrtime.bigint();
// Convert nanoseconds to milliseconds.
const duration = (endTime - startTime) / BigInt(1000000);
console.log(`${func.name}(${arg}) = ${result}, Time: ${duration}ms`);
}
const numbers = [10, 20, 30, 40, 42, 43, 500];
numbers.forEach(n => {
measurePerformance(memoizedFibonacci, n);
});
When you define the fibonacci function, use its memoized version to calculate the next number.
Now, run the function on various large numbers.
$ npx tsx fibonacci.ts
memoized_fibonacci(10) = 55, Time: 0ms
memoized_fibonacci(20) = 6765, Time: 0ms
memoized_fibonacci(30) = 832040, Time: 0ms
memoized_fibonacci(40) = 102334155, Time: 0ms
memoized_fibonacci(42) = 267914296, Time: 0ms
memoized_fibonacci(43) = 433494437, Time: 0ms
memoized_fibonacci(500) = 1.394232245616977e+104, Time: 0ms
The calculation is now virtually instant for every function call no matter how large.
So when you memoize, ask yourself: "What do you want to memoize?" Do you want to memoize only the outer function, or do you want to also memoize intermediary results in the implementation?
When do you want to use memoization?
Memoization is useful in:
As you've learned, memoization improves performance by reducing time complexity of operations and lowering the load on compute resources by avoiding repeated calculations.
But memoization also comes with drawbacks.
Subscribe to my YouTube channel for more great JavaScript and TypeScript tutorials!
