Cache results for functions?

Question

In Javascript, is there a way to cache results for functions that are:

• a). Computationally expensive.
• b). Called multiple times.

Take for example a recursive factorial function that gets called frequently. Usually I'd create a separate array such as facotrialResults = []; and add my results to them when I calculate them, factorialResults[x] = result; However, is there a better way to accomplish this caching without the use of adding a new variable to the global namespace?

Answer 1

You could attach a hash to the function that you want to cache.

var expensive_fn = function(val) {
  var result = arguments.callee.cache[val];
  if(result == null || result == undefined) {
    //do the work and set result=...
    arguments.callee.cache[val]=result;
  }
  return result;
}
expensive_fn.cache = {};

This would require that the function is a 1-1 function with no side effects.

Answer 2

You could consider rolling the underscore library into your environment. It's useful for many things, including its memoize function

Memoizes a given function by caching the computed result. Useful for speeding up slow-running computations. If passed an optional hashFunction, it will be used to compute the hash key for storing the result, based on the arguments to the original function. The default hashFunction just uses the first argument to the memoized function as the key.

var fibonacci = _.memoize(function(n) {
  return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2);
});

Answer 3

using cache

it's general solution

// wrap cache function
var wrapCache = function(f, fKey){
    fKey = fKey || function(id){ return id; };
    var cache = {};

    return function(key){
        var _key = fKey(key); 
        if (!cache[_key]){
            cache[_key] = f(key);
        };

        return cache[_key];
   };
};

// functions that expensive
var getComputedRGB = function(n){
    console.log("getComputedRGB called", n) ;
    return n * n * n; 
};

// wrapping expensive
var getComputedRGBCache = wrapCache(getComputedRGB, JSON.stringify);


console.log("normal call");
console.log(getComputedRGB(10));
console.log(getComputedRGB(10));
console.log(getComputedRGB(10));
console.log(getComputedRGB(10));
// compute 4 times


console.log("cached call") ;
console.log(getComputedRGBCache(10));
console.log(getComputedRGBCache(10));
console.log(getComputedRGBCache(10));
console.log(getComputedRGBCache(10));
// compute just 1 times


// output
=> normal call 
getComputedRGB called 10
1000
getComputedRGB called 10
1000
getComputedRGB called 10
1000
getComputedRGB called 10
1000

=> cached call
getComputedRGB called 10
1000
1000
1000
1000

Answer 4

You can define your own function properties so that the cached results are associated with the function, rather than populating the global namespace in a new array:

function factorial(n) {
  if (n > 0) {
    if (!(n in factorial))  // Check if we already have the result cached.
      factorial[n] = n * factorial(n-1);
    return factorial[n];
  }
  return NaN;
}
factorial[1] = 1; // Cache the base case.

The only problem with this is the overhead of checking if the result has been cached. However, if the complexity of the check is much lower than recomputing the problem, then it is well worth it.