Another cool JavaScript trick: memoization

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.

Advertisements

~ by Luis Abreu on September 30, 2009.

One Response to “Another cool JavaScript trick: memoization”

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

    Can I share this snippet on my JavaScript library?

    Awaiting your response. Thank

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: