Implementing Memoization in JavaScript

Memoization is a programming technique that tries to extend a function’s performance by caching its antecedently computed results. as a result of JavaScript objects behave like associative arrays, they're ideal candidates to act as caches. whenever a memoized function is called, its parameters are wont to index the cache. If the data is present, then it may be returned, without executing the whole function. However, if the data isn't cached, then the function is executed, and also the result's added to the cache.

In the following example, the initial Fibonacci function is rewritten to incorporate memoization. in the example, a self-executing anonymous function returns an inner function, f(), that is employed as the Fibonacci function. once f() is returned, its closure permits it to continue to access the “memo” object, that stores all of its previous results. each time f() is executed, it 1st checks to visualize if a result exists for the present value of “n”. If it does, then the cached value is returned. Otherwise, the initial Fibonacci code is executed. Note that “memo” is outlined outside of f() in order that it will retain its value over multiple function calls. Recall that the initial algorithmic function was referred to as over forty billion times to compute the fiftieth number. By implementing memoization, this number drops to ninety-nine.

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;
})();

Handling Multiple Arguments - 

In the previous example, the function accepted one argument. This created implementing the cache fairly trivial. sadly, most functions need multiple arguments, that complicates the indexing of the cache. To memoize a function with multiple arguments, either the cache should become multi-dimensional, or all of the arguments should be combined to make one index.

In a multi-dimensional approach, the cache becomes a hierarchy of objects rather than one object. every dimension is then indexed by one parameter. the following example implements a multi-dimensional cache for the Fibonacci function. during this example, the function accepts a further argument, “x”, that will nothing. on every occasion the function is invoked, the code checks that the “x” dimension exists, and initializes it if it doesn't exist. From that time forward, the “x” dimension is used to cache the “n” values. The result's that the function calls fibonacci(“foo”, 3) and fibonacci(“bar”, 3) aren't treated as the same result.

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;
})();

The alternative to a multi-dimensional cache may be a single cache object that is indexed by a mixture of all of the function’s arguments. below this approach, the arguments are transformed into an associated array and so want to index the cache. every function contains an in-built object named “arguments” that contains the arguments that were passed in. “arguments” may be a form of object called associate Array-like object. it's almost like an associate array, but can not be used to index the cache. Therefore, it should 1st be remodeled into an actual array. this could be done using the array slice() methodology. The array illustration will then be used to index the cache as shown before. the subsequent example shows however this is often accomplished. Note that an additional variable, “slice”, is outlined as a reference to the array slice() methodology. By storing this reference, the overhead of repeatedly computing Array.prototype.slice() is avoided. The call() methodology is then used to apply slice() to “arguments"

var fibonacci = (function() {
  var memo = {};
  var slice = Array.prototype.slice;

  function f(x, n) {
    var args = slice.call(arguments);
    var value;

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

      memo[arguments] = value;
    }

    return value;
  }

  return f;
})();