JavaScript Rules - Fast min/max in arrays

Fast min/max in arrays

23 Sep, 2009 by Marcel Duran

This morning while commuting to the office, reading JavaScript for Web Developers, I bumped into a question: how could I improve a well known algorithm that gets the smallest or the largest number in an array by using built-in Math methods such as Math.min and Math.max. For those not familiar with these methods, they return the smallest or the largest number respectively from a list of zero or more numbers passed as parameters, e.g.: Math.min(4,3,9,6) returns 3, Math.max(4,3,9,6) returns 9. I was wondering if calling such methods using apply and an Array as argument would work. I could hardly wait to get to the office to test it out on my Firebug console. I first tried:

Math.max.apply(Math, [4,8,3,5,1,2]);

And bingo! It works!

Previous work

Since it seemed so easy I thought that somebody else would had already figured this out before and I did a for Math.max.apply and *bam!*: the first occurrence was a John Resig’s post back in 07’s where he describes such technique for augmenting Array type. Really handy.

Performance

My main concern to decide whether to use this technique was its performance, so I ran a quick test comparing it to a very popular for loop algorithm and an optimized loop for a given array of random numbers:

var i, max,
    a = [],
    len = 1e4;

/* create an array of ten thousand random numbers */
console.time('array creation');
for (i = 0; i &lt; len; i += 1) {
    a[i] = Math.floor(Math.random() * 1e4);
}
console.timeEnd('array creation');

/* for loop */
max = -Infinity;
console.time('for loop');
for (i = 0; i &lt; len; i += 1) {
    if (a[i] > max) {
        max = a[i];
    }
}
console.timeEnd('for loop');
console.log(max);

/* optimized loop */
max = -Infinity;
i = len;
console.time('optimized loop');
while (i--) {
    if (a[i] > max) {
        max = a[i];
    }
}
console.timeEnd('optimized loop');
console.log(max);

/* Math.max */
console.time('Math.max');
max = Math.max.apply(Math, a);
console.timeEnd('Math.max');
console.log(max);

Running this code on my firebug console (Firefox 3.0.14), I got the same largest number on each technique within the array as expected and the following times:

array creation: 89ms
for loop: 29ms
optimized loop: 20ms
Math.max: 1ms

Wow! This is pretty fast! Huh? You can copy the code above and paste on your firebug console in order to get your own results or you can check it out here.

Conclusion

This technique deserves lots of credit for its simplicity and speed, it’s those one-line codes that beats any fancy and complex algorithm that once you get to know, you start using every time you need, however it’s not true for all browsers :-(