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:
1
2 function fib(n) {
3 if (n < 2) {
4 return n;
5 }
6 return fib(n - 1) + fib(n - 2);
7 }
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:
1
2 var iterMemoFib = (function() {
3 var cache = [1, 1];
4 var fib = function(n) {
5 if (n >= cache.length) {
6 for (var i = cache.length; i <= n; i++) {
7 cache[i] = cache[i - 2] + cache[i - 1];
8 }
9 }
10 return cache[n];
11 }
12
13 return fib;
14 })();
Which is a wee bit of a pain and not exactly readable; or get the computer to do it for you:
1
2 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().
1
2 Function.prototype.memoize = function() {
3 var pad = {};
4 var self = this;
5 var obj = arguments.length > 0 ? arguments[i] : null;
6
7 var memoizedFn = function() {
8 // Copy the arguments object into an array: allows it to
9 // be used as a cache key.
10 var args = [];
11 for (var i = 0; i < arguments.length; i++) {
12 args[i] = arguments[i];
13 }
14
15 // Evaluate the memoized function if it hasn't been
16 // evaluated with these arguments before.
17 if (!(args in pad)) {
18 pad[args] = self.apply(obj, arguments);
19 }
20
21 return pad[args];
22 }
23
24 memoizedFn.unmemoize = function() {
25 return self;
26 }
27
28 return memoizedFn;
29 }
30
31 Function.prototype.unmemoize = function() {
32 alert("Attempt to unmemoize an unmemoized function.");
33 return null;
34 }
