Implementing Memoization in JavaScript

Core points

• Memorization is a programming technique that improves the performance of a function by caching the results of previous calculations of a function. This is especially useful for recursive and mathematical functions that often use the same parameters.
• Implementing memory involves using caches indexed by the input parameters by the function. If the parameter exists in the cache, the cache value is returned; otherwise, the function is executed and the result is added to the cache.
• When memorizing is used for functions with multiple parameters, multidimensional cache can be used, or all parameters can be combined to form a single index. Object parameters should be stringified before being used as indexes.
• Memorization has certain limitations. It increases memory consumption and may not be suitable for functions that execute quickly or call low frequency. It can only be automated with references to transparent functions, i.e. its output depends only on its input and does not produce any side effects.

Programs often waste time calling functions that recalculate the same result repeatedly. This is especially true for recursive and mathematical functions. The Fibonacci number generator is a perfect example. A Fibonacci sequence is a series of integers starting with zero sums, where each value is the sum of the first two numbers in the sequence. According to this definition, the first ten Fibonacci numbers are: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34. From a programming perspective, the Fibonacci numbers are usually calculated recursively using the following functions. This function works well for smaller "n" values. However, as "n" increases, performance drops rapidly. This is because the two recursive calls repeat the same work. For example, to calculate the 50th Fibonacci number, the recursive function must be called more than 40 billion times (40,730,022,147 to be exact)! To make matters worse, calculating the 51st figure requires repeating the work almost completely twice. If the function remembers what it calculated before, it can alleviate the problem of repeated work.

function fibonacci(n) {
  if (n === 0 || n === 1)
    return n;
  else
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Basics of Memorization

Memorization is a programming technique that attempts to improve the performance of a function by caching the results of a function's previous calculations. Because JavaScript objects behave like associative arrays, they are ideal for acting as caches. Each time the memory function is called, its parameters are used for index cache. If the data exists, it can be returned without executing the entire function. However, if the data is not cached, the function is executed and the result is added to the cache.

In the following example, the original Fibonacci function is rewritten to include memory. In this example, the self-executing anonymous function returns an internal function f() which is used as the Fibonacci function. When f() is returned, its closure allows it to continue accessing the "memo" object, which stores all its previous results. Each time f() is executed, it first checks whether the result of the current "n" value exists. If present, the cache value is returned. Otherwise, execute the original Fibonacci code. Note that "memo" is defined outside of f() so that it can retain its value in multiple function calls. Recall that the original recursive function was called more than 40 billion times before it could calculate the 50th Fibonacci number. By implementing memory, this number drops to 99.

function fibonacci(n) {
  if (n === 0 || n === 1)
    return n;
  else
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Processing multiple parameters

In the previous example, the function accepts a single parameter. This makes implementing caching quite simple. Unfortunately, most functions require multiple parameters, which complicates cached indexes. To memorize a function with multiple parameters, the cache must become multidimensional, or all parameters must be combined to form a single index.

In multidimensional methods, cache becomes the hierarchy of the object, not a single object. Each dimension is then indexed by a single parameter. The following example implements a multidimensional cache for the Fibonacci function. In this example, the function accepts an additional parameter "x" and it does nothing. Each time a function is called, the code checks whether the "x" dimension exists and initializes it if it does not exist. Since then, the "x" dimension is used to cache the "n" value. The result is that function calls fibonacci("foo", 3) and fibonacci("bar", 3) are not considered the same result.

var fibonacci = (function() {
  var memo = {};

  function f(n) {
    var value;

    if (n in memo) {
      value = memo[n];
    } else {
      if (n === 0 || n === 1)
        value = n;
      else
        value = f(n - 1) + f(n - 2);

      memo[n] = value;
    }

    return value;
  }

  return f;
})();

The alternative to multidimensional cache is a single cache object, which is indexed by a combination of all parameters of the function. In this method, the parameters are converted to an array and then used for the index cache. Each function has a built-in object named "arguments" that contains the passed in parameters. "arguments" is an object of type called an array object of class. It is similar to an array, but cannot be used for index cache. Therefore, it must first be converted to the actual array. This can be done using the array slice() method. The cache can then be indexed using array representations, as shown before. The following example shows how to achieve this. Note that the additional variable "slice" is defined as a reference to the array slice() method. By storing this reference, you can avoid repeated calculations of Array.prototype.slice() overhead. Then use the call() method to apply slice() to "arguments".

var fibonacci = (function() {
  var memo = {};

  function f(x, n) {
    var value;

    memo[x] = memo[x] || {};

    if (x in memo && n in memo[x]) {
      value = memo[x][n];
    } else {
      if (n === 0 || n === 1)
        value = n;
      else
        value = f(x, n - 1) + f(x, n - 2);

      memo[x][n] = value;
    }

    return value;
  }

  return f;
})();

Cache object parameters

The memory scheme introduced here does not handle object parameters well. When objects are used as indexes, they are first converted to string representations, such as "[object Object]". This causes multiple objects to be incorrectly mapped to the same cache location. This behavior can be corrected by stringifying object parameters before indexing. Unfortunately, this also slows down the memory process. The following example creates a general memory function that takes an object as an argument. Note that object parameters are stringified using JSON.stringify() to create cached indexes.

function fibonacci(n) {
  if (n === 0 || n === 1)
    return n;
  else
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Automatic memory

In all previous examples, the function is explicitly modified to add memory. Memorized infrastructure can also be implemented without modifying the functions at all. This is useful because it allows the function logic to be implemented separately from the memorized logic. This is done by creating a utility function that takes the function as input and applies it to memorizes it. The following memoize() function takes the function "func" as input. memoize() returns a new function that wraps the cache mechanism around "func". Note that this function does not handle object parameters. To process the object, a loop is needed that will check each parameter individually and stringify as needed.

var fibonacci = (function() {
  var memo = {};

  function f(n) {
    var value;

    if (n in memo) {
      value = memo[n];
    } else {
      if (n === 0 || n === 1)
        value = n;
      else
        value = f(n - 1) + f(n - 2);

      memo[n] = value;
    }

    return value;
  }

  return f;
})();

Limitations

When realizing memory, the following points must be remembered. First, by storing old results, the memorization function consumes extra memory. In the Fibonacci example, the extra memory consumption is unlimited. If memory usage is a problem, a fixed-size cache should be used. The overhead associated with memory may also make it unsuitable for functions that execute very quickly or have low frequency.

The biggest limitation of memory is that it can only be automatically applied to the

reference transparent functions. If the output of a function depends only on its input and does not produce any side effects, the function is considered reference-transparent. Calls that reference transparent functions can be replaced with their return value without changing the semantics of the program. The Fibonacci function is referenced transparent because it depends entirely on the value of "n". In the following example, the function foo() is not referenced transparent because it uses the global variable "bar". Since "bar" can be modified outside of foo(), there is no guarantee that the return value will remain unchanged for each input value. In this example, the two calls to foo() return values ​​2 and 3, even if the parameters passed to the two calls are the same.

var fibonacci = (function() {
  var memo = {};

  function f(x, n) {
    var value;

    memo[x] = memo[x] || {};

    if (x in memo && n in memo[x]) {
      value = memo[x][n];
    } else {
      if (n === 0 || n === 1)
        value = n;
      else
        value = f(x, n - 1) + f(x, n - 2);

      memo[x][n] = value;
    }

    return value;
  }

  return f;
})();

Things to remember

• Memorization can potentially improve performance by caching the results of previous function calls.
• The memory function stores a cache indexed by its input parameters. If the parameter exists in the cache, the cache value is returned. Otherwise, execute the function and add the newly calculated value to the cache.
• Object parameters should be stringified before being used as indexes.
• Memorization can be automatically applied to reference transparent functions.
• Memorization may not be ideal for functions that are not called frequently or executed quickly.

FAQ on Memorizing in JavaScript (FAQ)

What is the main purpose of using memory in JavaScript?

Memorization is a programming technique used to optimize computer programs in JavaScript and other languages. This technique involves storing the results of expensive function calls and reusing them when the same input appears again. This can greatly improve the performance of the program by avoiding unnecessary calculations. It is especially useful in situations where recursive functions or functions that are repeatedly called with the same parameters.

How does memory work in JavaScript?

In JavaScript, memory works by creating a cache to store the results of function calls. When calling a function, the function first checks whether the result of the given input is already in cache. If so, the function returns the cached result instead of performing the calculation again. If the result is not in the cache, the function performs the calculation, stores the result in the cache, and returns the result.

Can you provide an example of a memorized function in JavaScript?

Of course, let's consider an example of a simple function that calculates the factorial of numeric. Without memory, the function looks like this:

function fibonacci(n) {
  if (n === 0 || n === 1)
    return n;
  else
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Using memory, we can optimize this function by storing the results of previous function calls:

var fibonacci = (function() {
  var memo = {};

  function f(n) {
    var value;

    if (n in memo) {
      value = memo[n];
    } else {
      if (n === 0 || n === 1)
        value = n;
      else
        value = f(n - 1) + f(n - 2);

      memo[n] = value;
    }

    return value;
  }

  return f;
})();

Is there any limitations or disadvantages of using memory in JavaScript?

While memorization can significantly improve the performance of JavaScript programs, it is not without its limitations. A major disadvantage of memory is that it can consume a lot of memory, especially when storing a lot of data in cache. If not managed properly, this can lead to performance issues. Furthermore, memory is only valid when the function is called with the same parameter multiple times. Memorization does not provide any performance benefits if the function input is always different.

Can I use memorization for all types of functions in JavaScript?

Memorization is most effective when used with pure functions. A pure function is a function that always returns the same result of the same input and does not produce any side effects. Memorizing the function may lead to unexpected results if it depends on an external state or has side effects. So while you can technically use memorization for any type of function in JavaScript, it is best for pure functions.

How to memorize functions with multiple parameters in JavaScript?

Implementing memory for a function with multiple parameters can be a bit complicated, but this is definitely possible. One way is to convert the arguments into strings that can be used as keys in the cache. Here is an example:

function fibonacci(n) {
  if (n === 0 || n === 1)
    return n;
  else
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Is there any library or tool that can help memorize in JavaScript?

Yes, there are libraries and tools that can help memorize in JavaScript. For example, the popular JavaScript utility library Lodash provides a _.memoize function that can easily memorize functions. Similarly, the Ramda library provides a R.memoizeWith function that allows you to specify custom cache key functions.

How to clear cache in memory function?

The cache in the memory function can be cleared by simply resetting the cache object. Here is an example:

var fibonacci = (function() {
  var memo = {};

  function f(n) {
    var value;

    if (n in memo) {
      value = memo[n];
    } else {
      if (n === 0 || n === 1)
        value = n;
      else
        value = f(n - 1) + f(n - 2);

      memo[n] = value;
    }

    return value;
  }

  return f;
})();

Can memory be used in JavaScript frameworks such as React?

Yes, memory is very useful in JavaScript frameworks such as React. For example, React provides a React.memo function that can be used to memorize components. This can help improve performance by preventing unnecessarily re-rendering of components.

How is memory in JavaScript compared to other optimization techniques?

Memorization is a powerful optimization technique, but it is not always the best solution. In some cases, other optimization techniques such as dejitter and throttling may be more suitable. The key is to understand the specific needs and constraints of the program and choose the right optimization technology.

The above is the detailed content of Implementing Memoization in JavaScript. For more information, please follow other related articles on the PHP Chinese website!