Cache (memoize) heavy-computing functions

If you are building a function that may be heavy on the processor (either clientside or serverside) you may want to consider a memoizer which is a cache of previous function executions and their returned values. This allows you to check if the parameters of a function were passed before. Remember, pure functions are those that given an input, return a corresponding unique output and don’t cause side-effects outside their scope so, you should not add memoizers to functions that are unpredictable or depend on external resources (like AJAX calls or randomly returned values).

Let’s say I have a recursive factorial function:

function fact(num) {
  return (num === 0)? 1 : num * fact(num - 1);
}

If I pass small values from 1 to 100 for example, there would be no problem, but once we start going deeper, we might blow up the call stack or make the process a bit painful for the Javascript engine we’re doing this in, especially if the engine doesn’t count with tail-call optimization (although Douglas Crockford says that native ES6 has tail-call optimization included).

We could hard code our own dictionary from 1 to god-knows-what number with their corresponding factorials but, I’m not sure if I advise that! Let’s create a memoizer, shall we?

var fact = (function() {
  var cache = {}; // Initialise a memory cache object
  
  // Use and return this function to check if val is cached
  function checkCache(val) {
    if (val in cache) {
      console.log('It was in the cache :D');
      return cache[val]; // return cached
    } else {
      cache[val] = factorial(val); // we cache it
      return cache[val]; // and then return it
    }
    
    /* Other alternatives for checking are:
    || cache.hasOwnProperty(val) or !!cache[val]
    || but wouldn't work if the results of those
    || executions were falsy values.
    */
  }

  // We create and name the actual function to be used
  function factorial(num) {
    return (num === 0)? 1 : num * factorial(num - 1);
  } // End of factorial function

  /* We return the function that checks, not the one
  || that computes because  it happens to be recursive,
  || if it weren't you could avoid creating an extra
  || function in this self-invoking closure function.
  */
  return checkCache; 
}());

Now we can start using it:

Now that I start to reflect on what I did, if I were to increment from 1 instead of decrement from num, I could have cached all of the factorials from 1 to num in the cache recursively, but I will leave that for you.

This is great but what if we have multiple parameters? This is a problem? Not quite, we can do some nice tricks like using JSON.stringify() on the arguments array or even a list of values that the function will depend on (for object-oriented approaches). This is done to generate a unique key with all the arguments and dependencies included.

We can also create a function that “memoizes” other functions, using the same scope concept as before (returning a new function that uses the original and has access to the cache object):

WARNING: ES6 syntax, if you don’t like it, replace … with nothing and use the var args = Array.prototype.slice.call(null, arguments); trick; replace const and let with var, and the other things you already know.

function memoize(func) {
  let cache = {};

  // You can opt for not naming the function
  function memoized(...args) {
    const argsKey = JSON.stringify(args);
    
    // The same alternatives apply for this example
    if (argsKey in cache) {
      console.log(argsKey + ' was/were in cache :D');
      return cache[argsKey];
    } else {
      cache[argsKey] = func.apply(null, args); // Cache it
      return cache[argsKey]; // And then return it
    }
  }

  return memoized; // Return the memoized function
}

Now notice that this will work for multiple arguments but won’t be of much use in object-oriented methods I think, you may need an extra object for dependencies. Also, func.apply(null, args) can be replaced with func(...args) since array destructuring will send them separately instead of as an array form. Also, just for reference, passing an array as an argument to func won’t work unless you use Function.prototype.apply as I did.

To use the above method you just:

const newFunction = memoize(oldFunction);

// Assuming new oldFunction just sums/concatenates:
newFunction('meaning of life', 42);
// -> "meaning of life42"

newFunction('meaning of life', 42); // again
// => ["meaning of life",42] was/were in cache :D
// -> "meaning of life42"