Memoization In JavaScript

Memoization is a popular programming technique that involves storing the result of a function for later use. This can be thought of as memorization for functions, to distinguish it from the regular meaning of the word memorization, which is simply remembering something. By storing the result of a function, we can optimize our program and avoid repeating the same computation.

Rather than invoking a function each time we need its result, we can simply retrieve the stored result instead. This is much faster since the result is already computed and just needs to be retrieved from storage. Essentially, memoization works like a cache for function results, allowing us to invoke a function with the same arguments and retrieve its result from the cache instead of computing it again.

It’s important to note that memoization only works if the function is deterministic and the same arguments always produce the same result. If the arguments differ, the result will also be different and the function will need to be invoked again to generate a new result.

Example

const sum = (a, b) => a + b;
console.log(sum(2,7))
console.log(sum(2,7))
//output: 9
//output: 9
const cache = {
    "2,7":9
}

1. We have a function called “sum” which takes two arguments, “a” and “b”, and returns their sum.
2. If we call the function with arguments (2, 7) and print the result with console.log(sum(2, 7)), we get the output 9. However, if we repeatedly call the function with the same arguments, it will do the computation every time, which can be time-consuming.
3. To avoid this, we can create a cache object that stores the results of previous function calls. When we call the function with the same arguments again, instead of computing the result again, we can simply return the result stored in the cache. This is known as memoization. However, it’s important to note that memoization uses additional memory to store the results, so we need to weigh the trade-off between improved performance and increased memory usage. In general, memoization is a useful technique for optimizing functions that take a long time to execute and are called repeatedly with the same arguments. Overall, while this code is a simple example of memoization, it’s important to use established solutions for memoization rather than implementing it manually and to carefully consider the complexity and memory usage of memoization when optimizing functions.

Complexity

Before we move forward, let’s discuss the concept of computational complexity. When a function takes a long time to execute, we say it’s computationally expensive. In such cases, we may want to optimize the function to execute faster, and one way to do this is through memoization. Memoization involves storing the results of expensive function calls and returning the cached result when the same inputs occur again. By doing so, we avoid repeated expensive computations.

However, memoization requires additional memory to store the cached results. We need to make a decision about whether we want to optimize the function for faster execution or trade-off with memory usage to store cached results. While memory is not a significant constraint nowadays, we should still be mindful of how much memory we’re using and whether it’s necessary to store cached results.

Memoization is an effective technique for optimizing functions that take a substantial amount of time to execute. It’s related to other algorithmic techniques, such as dynamic programming and tabulation, which involve remembering certain values to construct the final result. These techniques help to avoid repeating computations and can significantly improve performance.

According to the concept of memoization on Stack Overflow, it is commonly used to optimize the performance of repeatedly computing a result that will always be the same. This optimization, however, comes at the cost of allocating memory for the cached results. Here’s a simple code example:

var cachedResult;
function doHeavyCalculation()
{
    if (typeof(cachedResult) !== 'undefined')
        return cachedResult;

    // no cached result available. calculate it, and store it.
    cachedResult = /* do your computation */;
    return cachedResult;
}

There are several JavaScript frameworks available that facilitate memoization for any function. These frameworks provide a reusable boilerplate code by decorating a function.

The Fibonacci Series

Conventionally, the Fibonacci series is often used as an example to demonstrate how memoization can help with recursive solutions to problems.

The Fibonacci series is a sequence of numbers where each number is the sum of the two preceding ones, starting from 0 and 1. It looks like this: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, and so on.

A classic problem involving the Fibonacci series is to find the nth number in the series. For example, finding the 20th number in the series would be 6765.

Below is an example implementation of a function that calculates the nth Fibonacci number using recursion:

function fibonacci(n) {   
   if (n <= 1) {   
     return n;   
 }  
    return fibonacci(n - 1) + fibonacci(n - 2); 
}

However, this implementation can become slow for larger values of n, since it calculates the same values multiple times. This is where memoization can come in handy. By caching previously calculated values, we can avoid redundant calculations and significantly improve performance.