JavaScript function memoization

I have previously written about JavaScript functions having properties. I provided a fairly simple example of how this works. Another way this can be utilized is when doing function memoization.

Memoization optimizes speed of function execution by avoiding repeating calculations for previously passed inputs.

This means that a memoized function remembers the computed result for a set of inputs and thus omits the computation completely and instead simply looks up the cached result.

You can employ various techniques for storing the computed data using closures or global variables, but we can also utilize function properties and store the data on the function itself.

Let’s look at this principle in action.

Factorial

// A normal non memoized function calculating the factorial
function factorial(n) {
	if (n <= 1)
		return n;
	else
		return n * factorial(n - 1);
}

The function above calculates the factorial for a non-negative number n. This type of function, when called repeatedly, is a prime candidate for memoization.

By relying on properties on the function itself, memoization can be introduced like this

// Memoized function calculating the factorial
function memoFactorial(n) {
	if (n <= 1)
		return n;
	
	var cache = memoFactorial.cache || (memoFactorial.cache = {});
	return cache[n] || (cache[n] = n * memoFactorial(n - 1));
}

No global variables are being used and no surrounding closures are being created. Instead, the “cache” is being stored on the function itself.

Since the cache resides on the function itself it will continue to work even if we reference the function from another variable.

var another = memoFactorial;
another(6);

This is made possible by using a function declaration thus making it named. When we access memoFactorial we are referencing the actual function and not just a variable pointing to said function (named or anonymous).

General purpose memoization function

One ugly thing we have done though is mixed the responsibility of memoization with that of computing the factorial. To solve this problem we can create a general purpose memoization function that uses the same caching technique but can be applied to an existing function.

function memoize(func) {
	return function memo() {
		var args = Array.prototype.slice.call(arguments),
			cache = memo.cache || (memo.cache = {});

		return cache[args] || (cache[args] = func.apply(this, args));
	}
}

function factorial(n) {
	if (n <= 1)
		return n;
	else
		return n * factorial(n - 1);
}

var memofac = memoize(factorial);

memofac(6);
memofac(6);
memofac(6);

The function memoize takes a single function as argument and returns a new function. Here we do use a closure to access the original function but are still caching the results on the function itself. This mean that just like memoFactorial the returning function can be passed on to different variables without this causing any errors.

One downside to this approach, however, is that we do not cache any subsequent recursive calls to the same function. This means memofac(6) will only cache the result of this explicit function call and not provide any cached results if we decide to call memofac(5) later.

By caching the computed results on the function “object” itself, we ensure that the cache will follow the function without creating external variables coupled with the function. On the other hand, the cache will be public and other objects can potentially alter it from the outside. Different situations call for different strategies and this approach is just another tool for the belt. Use it if it applies.


Warning: count(): Parameter must be an array or an object that implements Countable in /var/www/whoknew.dk/public_html/wp-includes/class-wp-comment-query.php on line 399

Speak Your Mind

*