Memoization is an optimization technique used in computer programming to improve the performance of functions by caching their results based on their inputs. It is particularly useful for functions that are computationally expensive and have repetitive calls with the same arguments. By storing the computed results, subsequent calls with the same arguments can be returned directly from the cache, avoiding redundant computations.
Here's an example of memoization in JavaScript:
function fibonacci(n) {
if (n < 2) {
return n;
}
// Check if the result is already cached
if (fibonacciObj.cache[n] !== undefined) {
console.log(`Returning cached result for fibonacci(${n})`);
return fibonacciObj.cache[n];
}
// Calculate the fibonacci number and store it in the cache
console.log(`Calculating fibonacci(${n})`);
fibonacciObj.cache[n] = fibonacci(n - 1) + fibonacci(n - 2);
return fibonacciObj.cache[n];
}
// Initialize cache object
fibonacciObj.cache = {};
console.log(fibonacci(5)); // Output: Calculating fibonacci(5) / Calculating fibonacci(4) / Calculating fibonacci(3) / Calculating fibonacci(2) / Calculating fibonacci(1) / Calculating fibonacci(0) / Returning cached result for fibonacci(1) / Returning cached result for fibonacci(2) / Calculating fibonacci(3) / Returning cached result for fibonacci(4) / Returning cached result for fibonacci(5) / 5
console.log(fibonacci(5)); // Output: Returning cached result for fibonacci(5) / 5
console.log(fibonacci(8)); // Output: Calculating fibonacci(8) / Calculating fibonacci(7) / Calculating fibonacci(6) / Calculating fibonacci(5) / Returning cached result for fibonacci(6) / Calculating fibonacci(4) / Returning cached result for fibonacci(5) / Returning cached result for fibonacci(7) / Returning cached result for fibonacci(8) / 21
console.log(fibonacci(8)); // Output: Returning cached result for fibonacci(8) / 21
In this example, we implement a function to calculate Fibonacci numbers using recursion. We store the computed results in a cache object
`fibonacci.cache`. Before calculating the Fibonacci number for any given `n`, we check if the result is already cached. If it is, we return the cached value, avoiding redundant calculations. If not, we calculate the Fibonacci number and store it in the cache for future use.
As you can see, the first time we call
`fibonacci(5)`, it computes all Fibonacci numbers up to 5 and caches them. When we call
`fibonacci(5)` again, it directly returns the cached result, saving unnecessary computation time. The same applies when calling
`fibonacci(8)` multiple times.
Conclusion:
Memoization can significantly improve the performance of certain functions, especially when dealing with recursive or repetitive computations. It is essential to choose the right scenarios to apply memoization effectively.