Concept of memoization is not new. There is like a billion articles on the topic. Out of many, Resig covered it in his Secrets of JS Ninja book and Stefanov in his JavaScript Patterns. Addy Osmani blogged about performance of different memoization techniques and if you've been leaving under a rock and you are not familiar with it google is your firiend. There is a lot of good stuff out there so make sure you check it out. Long story short memoization is a method of caching the results of a function, you know, to make it faster.
Imagine that
superLongCalculation() function takes a parameter and returns value of some sort.
function superLongCalculation(someArg)
{
// some complicated stuff is happening here with someArg provided and only when done return result
return result;
}
Now, wouldn't it be nice if the function, after doing all the work could remember what the result is for this particular argument? Next time when its called with the same argument it should be able to look it up and return it right away, without recalculating same thing again. This is fairly simple to implement, just look at my attempt in JS below:
function superLongCalculation(someArg) {
return someArg * 3;
}
Function.prototype.memoized = function(a) {
if (typeof this.cache === "undefined") this.cache = [];
if (this.cache[a]) {
return this.cache[a];
} else {
this.cache[a] = this(a);
return this.cache[a];
}
}
console.log(superLongCalculation.memoized(2));
For the sake of example I keep it simple. Calculation is not all that complicated and code is pretty much self explanatory. We simply extending Function object with additional method. This
memoized method, once called with argument, will check internal array if there is a precalculated value for the argument we passed. If so then will return this precalculated value. Otherwise will call original function (
this(a)), this function will do very long calculations and the new value will be returned. To call it we simply use:
superLongCalculation.memoized(2)
Easy stuff yet very powerful. Yes, I know, extending native JS prototypes is a bad idea in general blah blah blah.. IMO it is useful in certain situation and as long as you understand what you doing and possible problems that come with it I see no issue.
Ok, then I stumbled upon Secrets of JS Ninja by Resig. He further extended the method allowing memoization to be called directly on a function. Real brainfuck if you ask me. And very interesting one. It allows retrieving cached results directly out of a function:
superLongCalculation(2)
To implement this we need to go a bit further however. The code I managed to put together is below and explanation of bits and pieces will follow:
Function.prototype.memoized = function(a) {
if (typeof this.cache === "undefined") this.cache = [];
if (this.cache[a]) {
return this.cache[a];
} else {
this.cache[a] = this(a);
return this.cache[a];
}
}
Function.prototype.memoize=function() {
var t=this;
return function() {
return t.memoized.apply(t,arguments);
}
}
myTest = (function superLongCalculation(someArg) {
return someArg * 3;
}).memoize();
console.log(myTest(2));
memoized function stays as it is. As previously it takes parameter and checks cache for precalculated values.
So lets start with figuring out what each bit is doing:
myTest = (function superLongCalculation(someArg) {
return someArg * 3;
}).memoize();
We simply creating a function here:
(function superLongCalculation(someArg) {
return someArg * 3;
})
It takes argument, multiplies by 3 and returns. This is in fact Function object and as such has
memoize method we attached to Function prototype:
Function.prototype.memoize=function() {
var t=this;
return function() {
return t.memoized.apply(t,arguments);
}
}
Further we have a call to
memoize method:
.memoize();
This call will give us back another method that will do stuff later. So to sum it up from now on, when we call
myTest, in fact we will call:
function() {
return t.memoized.apply(t,arguments);
};
This method has access to function object we created earlier (
t) and in turn calls
memoized method on this very object. Everyone's following? Right, so now at some point in our program we get to call
myTest and spit out result to console:
console.log(myTest(2));
So now
myTest(2) calls:
function() {
return t.memoized.apply(t,arguments);
}
t (via closure) refers to function object we created earlier. On this object we call
memoized method with "
2" passed as parameter.
memoized method checks if value is in cache, if so returns it, otherwise calls original method and then returns the result. And so we have basic memoization implemented now.
Now, that was the easy part and it gets a bit more involving when you try to make
superLongCalculations recursive. If anyone actually read this post I might put together few more examples with
fibonacci numbers or something later, for today its enough however.
