Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What Is Memoization
3.
Importance of Memoization
4.
When to Employ Memoization in JavaScript
5.
The Process of Memoization
6.
Memoization in JavaScript to Cache Function Values
7.
Performance Testing
7.1.
By Using The Default Flow Of The Function
7.2.
By using a Memoized Function
8.
Memoization With Recursive Functions
9.
Frequently Asked Questions
10.
Conclusion
Last Updated: Mar 27, 2024

Memoization in Javascript

Author Aditya kumar
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

Functions are an essential component of every programming language. Functions will be used often in your project as a developer. A function's ability to be reused is one of its most important qualities. You may make a call to them at any point in your programme. A function can either return or take a function as a parameter. We'll likely utilise a function more than once when you have an extensive application.

In this approach, a program's calculation may be contingent on the results of another function being executed. This implies that the programme will run and call these functions again each time we run it, returning the results and passing them to the appropriate analysis.

Executing such functions is inefficient, especially in a large system with a lot of calculations to do. In such time-consuming computations, memoization comes to the rescue.

What Is Memoization

Memoization is a depth-first, top-down optimization approach for storing previously run calculations. The software will not have to repeat the computation whenever the outcome of these computations is required. Instead, the result of the initial analysis will be reused. This eliminates the need for the software to repeat costly calculations. A time-consuming function takes a long time to perform.

This is a concept that pertains to the use of functional programming. Within a programme, you'll frequently repeat functions. When a process is called, the result is briefly saved using the idea of memoization. This function will not have to be executed again in any computation that requires its output. Instead, it will utilise the preceding execution's cached result.

In this scenario, we may define memoization as a method of storing the results of expensive function calls to speed up computer programmes by providing the cached result when the same input is provided again. Memoization will remember and retrieve these values without recalculating them every time.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Importance of Memoization

It is a performance-boosting approach that involves storing the results of function calls. It saves past findings and then retrieves them as needed throughout your programme. This improves CPU performance while reducing execution time.

A pure function should be a memoised function. This signifies that the execution of the function does not change. It should always return the same value when called with specific input, regardless of how many times the function is invoked.

Why not memorise the outcome of a function that performs not once, not twice, but multiple times? You'll just have to run this function once this way. This improves the performance of your software.

When to Employ Memoization in JavaScript

When a function is entirely pure and invoked, a pure function always returns the same value. When a function is impure, it gives different results every time it is called. Return values may be surprising if such values are cached.

When a programme performs an expensive computation, caching the results improves the program's speed. When employing memoization, the function doesn't have to recalculate its values, and it always returns the same results.

When API(Application Programming Interface ) calls are made from afar, use memoization in Javascript to avoid making several calls to the server when performing a repeating API call. You already know the outcome from the previous call, so you don't need to make another one to achieve the same results.

Recursive functions are functions that repeat themselves with recurring input values.

The Process of Memoization

Let's look at a real-life scenario. Assume you're reading a book with a warm, stylish, and appealing cover. A stranger approaches and inquires about the book's title and author. You'll probably turn the page, see the title and author's name, and respond to that stranger.

The book is appealing, and more people will be interested in learning more about it. If another person approaches you and inquires, you will not glance at the book's author and title again. You'll have to search for that information again if you don't recall. You may remember the details of the book at this time.

If a third party inquires about the book's details, you will have to rely on your recollection. Even if a hundred individuals ask about the book, the details will remain unchanged.

The concept of memoization is the same way. Memoisation saves the function results before returning them to the function caller when a function is invoked. Memoisation will return the result saved (cached) in memory when another caller points to the results of this function, and the function will not be called again. By caching the outcomes depending on their inputs, memorising avoids duplicate function calls.

Two major sub-concepts support the idea of memoization:

  • Closure: Closure is a function that has been wrapped around (enclosed) with references to the relevant state (the lexical environment). In another way, Closure allows you to access the outer function's domain from the inside function. Closures are formed when a function is created in JavaScript.
  • High-order function: A high-order function takes another function as an argument and returns another function as its output.

Memoization in JavaScript to Cache Function Values

Let's look at some instances to see how the concept of memoization in JavaScript might be used.

This is an example of a function that accepts an integer as an input and returns the square of that number.

const mysquare = num =>{
  let result = 0;
  for (let i = 1; i <= num; i++) {
    for (let j = 1; j <= num; j++) {
      result ++;
    }
  }
  return result;
}
console.log(mysquare(5));
console.log(mysquare(12));
console.log(mysquare(13));
console.log(mysquare(19));
console.log(mysquare(22));

 

You'll see that anytime you call the function, it will re-execute it and then return a squared value.

The implementation is simple and quick. The math is easy to understand. The main issue arises when you need to execute complex (expensive) calculations.

const mysquare = num =>{
  let result = 0;
  for (let i = 1; i <= num; i++) {
    for (let j = 1; j <= num; j++) {
      result ++;
    }
  }
  return result;
}
console.log(mysquare(191));
console.log(mysquare(899));
console.log(mysquare(5000));
console.log(mysquare(6467));
console.log(mysquare(7666));

 

This is ineffective. Instead, we may use the memoization concept to remember the outcome of mysquare() when it was initially called. The software will not have to perform this function again if we call it with the same input.

Let's implementt the memoization in JavaScript program. To do this, the program performs the first instance of mysquare(), which we will save and reuse numerous times throughout the program.

// a function that accepts a function and returns another
const memoize = (func) => {
  // a collection of results
  const results = {};
  // return a function for the results cache
  return (...args) => {
    //a JSON key to preserve the cached results
    const argsKey = JSON.stringify(args);
    // 'func' should only be used if mysquare has no cached value ()
    if (!results[argsKey]) {
      // mysquare's return value should be saved ()
      results[argsKey] = func(...args);
    }
    // retrieve the results from the cache
    return results[argsKey];
  };
};

//mysquare() should be wrapped with memoize ()
const mysquare = memoize(num => {
    let result = 0;
    for (let i = 1; i <= num; i++) {
        for (let j = 1; j <= num; j++) {
            result++;
        }
    }
    return result;
});

console.log(mysquare(191));
console.log(mysquare(899));
console.log(mysquare(5000));
console.log(mysquare(6467));
console.log(mysquare(7666));

 

When compared to the idea of memoization not being used, the example above executes faster. You may save the cache using a different function, as illustrated above. You might also choose to save the findings in a variable.

Take a look at this example.

const memoizedVal = [];
const mysquare = (num) => {
  if ((memoizedVal[num] == !undefined)) {
    return memoizedVal[num];
  }

  let result = 0;
  for (let i = 1; i <= num; i++) {
    for (let j = 1; j <= num; j++) {
      result++;
    }
  }

  memoizedVal[num] = result;
  return result;
};

console.log(mysquare(191));
console.log(mysquare(899));
console.log(mysquare(5000));
console.log(mysquare(6467));
console.log(mysquare(7666));

Performance Testing

Let's compare the time it takes for a function to execute using the usual function flow to a memoized function.

When the function mysquare() is called, the example below calculates the time it takes.

By Using The Default Flow Of The Function

const mysquare = (num) => {
  let result = 0;
  for (let i = 1; i <= num; i++) {
    for (let j = 1; j <= num; j++) {
      result++;
    }
  }
  return result;
};

console.time("FirstCall");
console.log(mysquare(7467));
console.timeEnd("First call");

// two times the same value
console.time("SecondCall");
console.log(mysquare(7467));
console.timeEnd("SecondCall");

console.time("ThirdCall");
console.log(mysquare(7467));
console.timeEnd("ThirdCall");

 

Output

The time it takes to perform each function gets longer. The execution process is restarted after each function call.

You can practice by yourself with the help of Online Javascript Compiler for better understanding.

By using a Memoized Function

const memoize = (func) => {
  const results = {};
  return (...args) => {
    const argsKey = JSON.stringify(args);
    if (!results[argsKey]) {
      results[argsKey] = func(...args);
    }
    return results[argsKey];
  };
};

const mysquare = memoize((num) => {
  let result = 0;
  for (let i = 1; i <= num; i++) {
    for (let j = 1; j <= num; j++) {
      result++;
    }
  }
  return result;
});

console.time("FirstCall");
console.log(mysquare(7467));
console.timeEnd("FirstCall");

// two times the same value
console.time("SecondCall");
console.log(mysquare(7467));
console.timeEnd("SecondCall");

console.time("ThirdCall");
console.log(mysquare(7467));
console.timeEnd("ThirdCall");

 

When the function is invoked a second time, notice how the execution time drops dramatically. This is because mysquare() was previously cached during the return result.

Output

Memoization With Recursive Functions

When a function calls itself several times, it is referred to as recursion. A break condition will be specified in a function that signals when it should stop calling itself. The idea of looping is used in recursion. When a number iterates numerous times until a given condition is fulfilled, it is said to be in a loop.

A Fibonacci sequence is an excellent example of recursion in action. A Fibonacci sequence predicts the future Fibonacci term by adding two previous numbers in the sequence.

A Fibonacci sequence's initial terms are:

1,1,2,3,5,8,13,...,and so on up to infinity.

Each number is the sum of the two numbers before it. This is how the sequence is put together.

A Fibonacci sequence calculates the same numbers over and over again. This turns into a needless calculation. Furthermore, the application may slow down as you produce more Fibonacci words.

The nth Fibonacci term in the Fibonacci sequence is generated in this Fibonacci example. Keep in mind that the function should run quickly, be well-written, and be stable and trustworthy.

const fibonacci = (n) => {
    //Return the first term 1 if n equals 1.
    if (n == 1) {
      return 1;
    }
    //Return the second term 1 if n equals 2.
    else if (n == 2) {
      return 1;
    }

    //If n is more than two, return the total of the two words before it.
    else 
      return fibonacci(n - 1) + fibonacci(n - 2);
};
//the eighth phrase in the series should be printed
console.log(Fibonacci(8));

 

Output

The program is simple to follow. The eighth period, which is 8, is recorded here.

However, when we try to produce a higher nth Fibonacci term, the program gets more sluggish.

const fibonacci = (n) => {
    // Return the first term 1 if n equals 1.
    if (n == 1) {
      return 1;
    }
    // Return the second term 1 if n equals 2.
    else if (n == 2) {
      return 1;
    }

    // If n is more than two, return the total of the two words before it.
    else 
      return fibonacci(n - 1) + fibonacci(n - 2);
};
// the sixtieth phrase in the series should be printed
console.log(fibonacci(60));

 

Output

This calculation takes around 155319.323 milliseconds to complete.

Behind the scenes, the recursive function operates like this. Take, for example, the sixth term. Fibonacci(5) = Fibonacci(4) + Fibonacci(3) is how the fifth term is computed (3).

Fibonacci(4), on the other hand, must produce fibonacci(3) + fibonacci(4) (2).

Fibonacci numbers must be computed by the software (3). Fibonacci(2) + Fibonacci(1) is called again to return Fibonacci (3).

The function repeats itself until the fifth computation term is reached. This is a large number of calculations. When the software returns the previous Fibonacci terms, it will call the Fibonacci calls that were previously called.

You may imagine how many calculations will be required to create the 60th phrase. Because the function repeats itself until the condition of the 60th term is fulfilled, it will be recursive in this situation.

We can instead memorise the function's output.

const memoize = (func) => {
  const results = {};
  return (...args) => {
    const argsKey = JSON.stringify(args);
    if (!results[argsKey]) {
      results[argsKey] = func(...args);
    }
    return results[argsKey];
  };
};

const fibonacci = memoize((n) => {
  // Return the first term 1 if n equals 1.
  if (n == 1) {
    return 1;
  }
  //Return the second term 1 if n equals 2.
  else if (n == 2) {
    return 1;
  }
  // If n is more than two, return the total of the two words before it.
  else 
  return fibonacci(n - 1) + fibonacci(n - 2);
});
//the sixtieth phrase in the series should be printed
console.log(Fibonacci(60));

 

Output

Returning the 60th term with a memoized function takes roughly 4.043ms, which is quicker than the example before.

Every call to a function will be a cache. Fibonacci(5), for example, will just compute Fibonacci(4) + Fibonacci(3) in this situation because the other terms have already been called and cached. Any subsequent calls will not be required to repeat any past calculations.

Check out this problem - Count Ways To Reach The Nth Stair 

Must Read Fibonacci Series in JavaScript  jquery ajax

Frequently Asked Questions

  1.  What exactly do you mean when you say "memoization"?
    It is a technique for speeding up computer systems by caching the results of costly function calls and returning the cached result when the same inputs are used again.
     
  2. What is a recursive function?
    A recursive function is a routine that calls itself directly or indirectly in a programming language.
     
  3. Why do we need to use memoization in Javascript?
    It's a performance-boosting approach that involves storing the results of function calls. It saves past findings and then retrieves them as needed throughout your programme. This improves CPU performance while reducing execution time.
     
  4. When we should not use memoization?
    When the function's output isn't reliant on the input, and the result varies over time, memorising shouldn't be employed.
     
  5. When we should use memoization?
    Memoization is a technique for saving values returned by a function so that you don't have to repeat calculations you've already done. This strategy is convenient when we have a frequently called function whose analysis is time-consuming.

Conclusion

In this article, we have discussed the explanation of memoization in Javascript. Memoization is a programming idea that may be used with any language. Its primary purpose is to make your software better. This is most noticeable when software is conducting complex calculations. Memoization will save the results of these computations so that it does not have to work as hard when performing a complex operation that needs a previously completed analysis. This idea has been implemented in several JavaScript libraries, including Async.js, Lodash, Memoizee, Moize, and Fast-memoize.

We hope that this blog has helped you enhance your knowledge regarding memoization in Javascript. If you want to learn more, check out our article on Implement Linear Search and Binary Search in an ArrayDebounce and Throttle, and Sort an Array with and without inbuilt methods.

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enroll in our courses and refer to the mock test and problems available; look at the Top 150 Interview Puzzles interview experiences and interview bundle for placement preparations.

Do upvote our blog to help other ninjas grow. 

Happy Coding!

Previous article
Implement Custom Deep Clone Method
Next article
Sort an Array with and without inbuilt methods
Live masterclass