LA.NET [EN]

Sep 30

Memoization is one nice trick you can use to improve your JavaScript code. The idea is quite simple: in scenarios where you have “pure” functions, you can improve the total time of execution by saving the results of previous executions. I think that an example will help understand how things work. Let’s start by looking at how we might calculate the factorial of a number:

var factorial = function(num) {
    return num < 2 ? 1 : num * factorial(num - 1);
}

The previous function ignores negative numbers and will simply return one for any number that is smaller than 2 (you could improve the code by checking for negative numbers). The problem with this function is that you end up invoking the function several  times and you won’t reuse any of those results in future calls. For instance, if you invoke factorial(5) and then factorial(6), you won’t be able to reuse the results of the first call in the second call. Memoization helps in these cases! Here’s the updated code that uses memoization:

var factorial = function(num) {
    var results = [1, 1]; //0!===1! === 1
    var calculate = function(n) {
        if (results[ n ] === undefined) {
            results[ n ] = n * calculate(n - 1);
        }
        return results[ n ];
    }
    return calculate;
} ();
alert(factorial(5));
alert(factorial(6));

(Once again, I’m not testing for negative numbers in order to keep things simple).

Most of the work is run by the inner calculate function. We wrap it up in an anonymous function so that we can reuse closures to keep the results array “private”. As you can see, calculate will always check for a value in the results array before performing a recursive calculate call.

To make it work, we need to return calculate (ie, we need to return a reference to the calculate function) from the anonymous function and we also need to execute the anonymous function in place (notice the () after the anonymous function definition!).

And that’s it for today! Keep tuned for more on JavaScript.

1 comment so far

  1. JavaScript Countdown Timer
    12:24 am - 10-2-2009

    very cool & good tip, thank you very much for sharing.

    Can I share this snippet on my JavaScript library?

    Awaiting your response. Thank