Memoizing functions in JavaScript

keith (Keith Gaughan) — Fri, 22 Jul 2005 05:35:49 GMT

Here's something I knocked together a fortnight ago because I wanted to see if I could produce Perl's Memoize.pm in JavaScript.

Memoization is a method of increasing the speed of slow referentially transparent functions by caching their arguments and results. This trades a marginal amount of memory space for a potentially huge gain in speed.

Take the canonical definition of the fibonacci sequence, for instance:



function fib(n) {

    if (n < 2) {

        return n;

    }

    return fib(n - 1) + fib(n - 2);

}

As you can guess, this quickly becomes quite slow once you start using numbers greater than around 20. Once you're dealing with numbers in the mid-thirties range, it cripples the computer.

The solution is to memoize the function. You can either do it by hand:



var iterMemoFib = (function() {

    var cache = [1, 1];

    var fib = function(n) {

        if (n >= cache.length) {

            for (var i = cache.length; i <= n; i++) {

                cache[i] = cache[i - 2] + cache[i - 1];

            }

        }

        return cache[n];

    }



    return fib;

})();

Which is a wee bit of a pain and not exactly readable; or get the computer to do it for you:



fib = fib.memoize();

Due to technical (browser security) constraints, the arguments for memoized functions can only be arrays or scalar values. No objects.

The code extends the Function object to add the memoization functionality. If the function is a method, then you can pass the object into memoize().



Function.prototype.memoize = function() {

    var pad  = {};

    var self = this;

    var obj  = arguments.length > 0 ? arguments[i] : null;



    var memoizedFn = function() {

        // Copy the arguments object into an array: allows it to

        // be used as a cache key.

        var args = [];

        for (var i = 0; i < arguments.length; i++) {

            args[i] = arguments[i];

        }



        // Evaluate the memoized function if it hasn't been

        // evaluated with these arguments before.

        if (!(args in pad)) {

            pad[args] = self.apply(obj, arguments);

        }



        return pad[args];

    }



    memoizedFn.unmemoize = function() {

        return self;

    }



    return memoizedFn;

}



Function.prototype.unmemoize = function() {

    alert("Attempt to unmemoize an unmemoized function.");

    return null;

}

DZone Snippets: memoization code

Memoizing functions in JavaScript