JAVA SCRIPT - Improving Application Performance with Memoization (Caching Calculations

 Improving Application Performance with Memoization (Caching Calculations)

Problem

You want to optimize your JavaScript applications and libraries by reducing the need to repeat complex and CPU-intensive computations.

Solution

Use function memoization in order to cache the results of a complex calculation. Here, I’m borrowing an example as applied to the code to generate a Fibonacci number:

var fibonacci = function () {
 var memo = [0,1];
 var fib = function (n) {
 var result = memo[n];
 if (typeof result != "number") {
 result = fib(n -1) + fib(n - 2);
 memo[n] = result;
 }
 return result;
 };
 return fib;
}();

Memoization is the process where interim values are cached rather than recreated, cut‐ ting down on the number of iterations and computation time. It works especially well with something like the Fibonacci numbers or factorials, both of which operate against previously calculated values. For instance, we can look at a factorial, 4!, as follows:

return 1;
return 1;
return 1 * 2;
return 1 * 2 * 3;
return 1 * 2 * 3 * 4;
But we can also view it as: 3! * 4 // 4!

In other words, if we cache the value for 2! when creating 3!, we don’t need to recalculate 1 * 2 and if we cache 3! when calculating 4!, we don’t need 1 * 2 * 3, and so on. 

Memoization is built into some languages, such as Java, Perl, Lisp, and others, but not into JavaScript. If we want to memoize a function, we have to build the functionalityourselves. The key to the effective use of memoization is being aware that the technique doesn’t result in performance improvements until the number of operations is signifi‐ cant enough to compensate for the extra effort shows the memoized and nonmemoized versions of the 


Fibonacci function that Crockford provided in his book. Note that the calculations are intense and can take a considerable time. Save any work you have in other tabs. You may have to override a message given by the browser, too, about killing a script that’s running a long time 

A demonstration of memoization

// Memoized Function
var fibonacci = function () {
 var memo = [0,1];
 var fib = function (n) {
 var result = memo[n];
 if (typeof result != "number") {
 result = fib(n -1) + fib(n - 2);
 memo[n] = result;
 }
 return result;
 };
 return fib;
}();
// nonmemoized function
var fib = function (n) {
 return n < 2 ? n : fib(n - 1) + fib(n - 2);
};
// run nonmemo function, with timer
console.time("non-memo");
for (var i = 0; i <= 10; i++) {
 console.log(i + " " + fib(i));
}
console.timeEnd("non-memo");
// now, memo function with timer
console.time("memo");
for (var i = 0; i <= 10; i++) {
 console.log(i + " " + fibonacci(i));
}
console.timeEnd("memo");

First, the code is run in 10 times in a loop, in jsFiddle via Firefox:

non-memo: 14ms
memo: 8ms

The result generates one big “meh.” In the second run, though, the code is edited to run the code in a for loop of 30. The result is as follows:

non-memo: 4724ms
memo: 19ms

A major change. When I tried to run the example in a loop of 50 iterations, my browser crashed.