Reusable Memoization Function

Let us see how we could use a reusable function that can ‘memoize’ any given function.

Memoization is a technique that can be used in long, recursive code to cache results from previous executions and speed up the overall process. Previously we have seen an overview memoization in JS with an example of generating Fibonacci series using such techniques.

But, what if you want to apply that for multiple operations? Say, you are building a super-calculator that outputs Fibonacci series, factorial of a number, sum-product of repeat combinations, etc.

In the previous rather simplistic example, we would have to write functions for individual calculations. Today, we will see how we could potentially abstract the function that does the actual memo and keep it separate from the actual calculation.

We will take the previous example of generating Fibonacci series. We have the following code that is memozed and ready-to-rock -

function fibo(n, cache) {
  cache = cache ? cache : {};

  if (cache[n]) {
    console.log("returning cached result for: ", n);
    return cache[n];
  }

  if (n < 2) {
    console.log("iterating..", 1);
    cache["0"] = 1;
    cache["1"] = 1;
    return 1;
  } else {
    console.log("iterating..", n);
    cache[n] = fibo(n - 1, cache) + fibo(n - 2, cache);
    console.log("cache: ", cache);
    return cache[n];
  }
}

fibo(5);

First, let us extract the function responsible to do the calculation.

let fibo = function(n) {
  if (n <= 1) return 1;
  else {
    return fibo(n - 1) + fibo(n - 2);
  }
};

fibo(5); // works!

Now, let’s create a separate function that can produce the same results as using the cache within the function.

let memoize = function(func) {
  const cache = {};
  return (...args) => {
    const key = JSON.stringify(args);
    console.log(cache);
    return key in cache ? cache[key] : (cache[key] = func(...args));
  };
};

Wrap fibo within memoize - producing the following code.

let memoThis = function(func) {
  const cache = {};
  return (...args) => {
    const key = JSON.stringify(args);
    console.log(cache);
    return key in cache ? cache[key] : (cache[key] = func(...args));
  };
};

let fibo = memoThis(function(n) {
  if (n <= 1) return 1;
  else {
    return fibo(n - 1) + fibo(n - 2);
  }
});

console.log(fibo(5));

/* output
{}
{}
{}
{}
{}
{ '[1]': 1 }
{ '[1]': 1, '[0]': 1, '[2]': 2 }
{ '[1]': 1, '[0]': 1, '[2]': 2, '[3]': 3 }
{ '[1]': 1, '[0]': 1, '[2]': 2, '[3]': 3, '[4]': 5 }
*/

Beautiful, ain’t it?

comments powered by Disqus