First, I should say that it's not misspelled! Memoization is a technique used to speed up functions by creating a cache of results. It's like giving your function a notebook to write down answers and not having to recalculate things again, smart, isn't it?
A Quick Note: Pure Functions
A pure function has the following characteristics:
- Deterministic: For the same inputs, it always returns the same output.
- No side effects: It doesn't modify any state outside its local scope.
- Doesn't depend on external state: Its result depends only on the arguments passed.
Example:
// Impure function ❌
function add(){
const a = prompt(`Number 1:`);
const b = prompt(`Number 2:`);
return a + b;
}
let total = 0;
// Impure function ❌
function addToTotal(value) {
total += value;
return total;
}
// Pure function ✅
function add(a, b){
return a + b;
}To perform memoization, it's essential that it be done with pure functions.
Memoizing the Last Calculated Value
Imagine you have a frontend application with a button that performs a complex calculation that takes 200 ms to complete. If the user desperately clicks this button, the browser will simply freeze for moments. How can we solve a problem like this? Memoization
For this, let's create a utility function to add memoization to our expensive function:
function memoizeLastResult(fn) {
// Stores the arguments of the last call
let lastArgs = null;
// Stores the result of the last call
let lastResult = null;
// Returns a new function that wraps the original function
return function(...args) {
// Compares current arguments with those of the last call
// Uses JSON.stringify to compare arrays/objects deeply
if (JSON.stringify(args) === JSON.stringify(lastArgs)) {
// If the arguments are the same, returns the cached result
return lastResult;
}
// If the arguments are different:
// 1. Updates lastArgs with current arguments
lastArgs = args;
// 2. Calls the original function and stores the result
lastResult = fn.apply(this, args);
// 3. Returns the new result
return lastResult;
};
}
// Usage:
// const memoizedFn = memoizeLastResult(originalFunction);
// memoizedFn() will now have memoization behavior
Thus, on the next call of the memoized function, the result will come instantly with the last calculated value.
Example:
// Function that simulates an expensive calculation
function calculateComplexArea(width, height) {
console.log(`Calculating area for ${width} x ${height}...`);
// Simulating a time-consuming calculation
let result = 0;
for (let i = 0; i < 1000000; i++) {
result += width * height;
}
return result / 1000000;
}
// Applying memoization to the calculation function
const memoizedCalculateArea = memoizeLastResult(calculateComplexArea);
// Usage examples
console.time("First call");
console.log(memoizedCalculateArea(5, 3));
console.timeEnd("First call");
console.time("Second call (same arguments)");
console.log(memoizedCalculateArea(5, 3));
console.timeEnd("Second call (same arguments)");
console.time("Third call (different arguments)");
console.log(memoizedCalculateArea(6, 4));
console.timeEnd("Third call (different arguments)");
console.time("Fourth call (arguments same as third)");
console.log(memoizedCalculateArea(6, 4));
console.timeEnd("Fourth call (arguments same as third)");In this example, we have the following result:
Calculating area for 5 x 3...
15
First call: 2.713134765625 ms
15 Second call (same arguments): 0.02294921875 ms
Calculating area for 6 x 4...
24
Third call (different arguments): 0.761962890625 ms
24
Fourth call (arguments same as third): 0.017822265625 ms
Thus, we can observe that between the first call and the second with the same arguments, there was a MASSIVE decrease in response time! However, when changing the arguments, there will no longer be the benefit of memoization, making it a technique that won't serve so well for functions that are constantly invoked with different parameters.
Memoizing All Calculated Values
This method not only memoizes the last value but all calculated results using a map.
function memoizeAll(fn) {
// Creates a Map to store cached results
// Map is used instead of a simple object for better performance with complex keys
const cache = new Map();
// Returns a new function that wraps the original function
return function(...args) {
// Converts the arguments into a string to use as a cache key
// JSON.stringify is used to handle arguments that are objects or arrays
const key = JSON.stringify(args);
// Checks if the result for these arguments is already in the cache
if (cache.has(key)) {
// If it's in the cache, returns the stored result
return cache.get(key);
}
// If it's not in the cache, executes the original function
// 'apply' is used to preserve the 'this' context and pass the arguments
const result = fn.apply(this, args);
// Stores the result in the cache for future use
cache.set(key, result);
// Returns the calculated result
return result;
};
}
// Usage:
// const memoizedFn = memoizeAll(originalFunction);
// memoizedFn() will now have complete memoization behavior
In this case, there will be a performance increase in all calls with repeated arguments, but as we change the arguments of the call to the memoized function, our map will continue to grow.
Therefore, this solution trades faster performance for potentially unlimited memory growth. In the worst cases, this can result in the browser tab failing, especially if each result uses a significant portion of memory (for example, a DOM tree).
Besides these methods, you can also implement something like memoization for only the last N results so that there isn't unlimited growth in the memory used, or even use a WeakMap that can be automatically cleaned whenever the key object no longer exists.
Finally, memoization is a technique to make your program more performant by using cache in specific functions that are called with high frequency, and it's up to you to understand where it can or cannot be used.
And you, did you already know this technique? Have you seen it used somewhere besides the famous memo/useMemo in React?