Memoization in JavaScript

Memoization is a technique used in computer science to optimize the performance of functions by caching the results of expensive computations. This can significantly improve the speed and efficiency of your code, especially when working with large datasets or complex algorithms.

In this article, we'll explore how memoization works and provide a code example to illustrate its benefits.

How Memoization Works

Memoization works by storing the results of expensive computations in a cache so that they can be quickly retrieved later without repeating the same calculation. This can be especially useful for functions that take a long time to execute, such as those that involve complex mathematical operations or data processing.

When a memoized function is called with a given set of input arguments, the function first checks if the result for those arguments has already been computed and stored in the cache. If the result is found in the cache, it is immediately returned without performing the expensive computation. If the result is not found in the cache, the function performs the computation as usual and stores the result in the cache for future use.

Code Example

Fibonacci is a mathematical sequence in which each number is the sum of the two preceding numbers. The sequence starts with 0 and 1, and the next number in the sequence is the sum of the previous two numbers. So the sequence goes like this: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, and so on.

Let's look at an example to see how memoization works in practice. Suppose we have a function fibonacci that calculates the nth number in the Fibonacci sequence:

const fibonacci = (n) => {
  if (n < 2) {
    return n;
  } else {
    return fibonacci(n - 1) + fibonacci(n - 2);
  }
};

This function uses recursion to calculate the Fibonacci sequence, which can be very computationally expensive for large values of n. For example, if we call fibonacci(50), it would take several seconds to compute.

Now let's apply memoization to this function to speed it up. We can create a higher-order function called memoize that takes a function as an argument and returns a memoized version of that function:

const memoize = (fn) => {
  const cache = {};
  return (...args) => {
    const key = JSON.stringify(args);
    if (cache[key]) {
      return cache[key];
    } else {
      const result = fn(...args);
      cache[key] = result;
      return result;
    }
  };
};

This function returns a new function that caches the results of the original function based on its input arguments. The cache is implemented as an object, where the keys are the serialized input arguments and the values are the computed results.

We can now use the memoize function to create a memoized version of fibonacci:

const memoizedFibonacci = memoize(fibonacci);

This creates a memoized version of fibonacci called memoizedFibonacci. Now if we call memoizedFibonacci(50), the result is computed much faster than before because the result is cached after the first call.

console.time("Memoized Fibonacci");
console.log(memoizedFibonacci(50));
console.timeEnd("Memoized Fibonacci");

console.time("Unmemoized Fibonacci");
console.log(fibonacci(50));
console.timeEnd("Unmemoized Fibonacci");

Output:

Memoized Fibonacci: 12586269025
Memoized Fibonacci: 0.080ms
Unmemoized Fibonacci: 12586269025
Unmemoized Fibonacci: 3032.342ms

As you can see from the output, the memoized version fibonacci is much faster than the original version, even though it computes the same result. This is because the memoized version caches the results of previous calls, eliminating the need to recompute the result for the same input arguments.

Conclusion

Memoization is a powerful optimization technique that can significantly improve the performance of your code, especially for functions that involve expensive computations. By caching the results of previous function calls, you can avoid unnecessary recalculations and improve the speed and efficiency of your code.

In this article, we've explored how memoization works and we provided a code example to illustrate its benefits. We've seen how to create a memoized version of a function using a higher-order function called memoize, which caches the results of the original function based on its input arguments.

Overall, memoization is a valuable technique that can help you optimize your code and improve its performance. By applying memoization to your functions, you can reduce the time and resources required to execute them and improve the overall efficiency of your code.