7 ms·

Fast JavaScript Max/Min

62 points by DanielRibeiro 16y ago

jacobolus 16y ago
Underscore.js is pretty good about delegating to built-in functions when available in its little utility functions. http://documentcloud.github.com/underscore/docs/underscore.html#section-25 http://documentcloud.github.com/underscore/docs/underscore.h...
- tzury 16y ago
  They surely missed this one though. as Underscore.js do this: _.max = function(obj, iterator, context) { if (!iterator && _.isArray(obj)) return Math.max.apply(Math, obj); var result = {computed : -Infinity}; each(obj, function(value, index, list) { var computed = iterator ? iterator.call(context, value, index, list) : value; computed >= result.computed && (result = {value : value, computed : computed}); }); return result.value; }; _.min = function(obj, iterator, context) { if (!iterator && _.isArray(obj)) return Math.min.apply(Math, obj); var result = {computed : Infinity}; each(obj, function(value, index, list) { var computed = iterator ? iterator.call(context, value, index, list) : value; computed < result.computed && (result = {value : value, computed : computed}); }); return result.value; }; While John do that: Array.max = function( array ){ return Math.max.apply( Math, array ); }; Array.min = function( array ){ return Math.min.apply( Math, array ); };
  - alunny 16y ago
    The Underscore functions do exactly the same as Resig's in the simple case (when passed just an array of numbers). They're longer because they accept custom iterators for non-numerical arrays.
- jashkenas 16y ago
  The real reason why Underscore doesn't use "Math.max.apply" and "Math.min.apply", is that they only work on small arrays of numbers. After you get beyond 40-50,000-ish (last time I checked), some browsers will throw an exception because you can't pass that many arguments to a function. I remember running into this in real-world code, trying to calculate the brightest pixel in a <canvas> imageData array.
clvv 16y ago
> Posted: January 13th, 2007 That's four years ago.
- gobongo 16y ago
  > 4 points by clvv 2 hours ago | link | parent | flag That's 2 hours ago.
dionidium 16y ago
I started to feel pretty smug [0], at first. How could John Resig not know this? Then I saw that it was from 2007. Sheesh, I probably first learned about this trick from that post. [0] http://stackoverflow.com/questions/5020954/adding-functions-to-javascripts-array-class-breaks-for-loops/5021375#5021375 http://stackoverflow.com/questions/5020954/adding-functions-...
nkassis 16y ago
I used his technique for a while but then I had to find the max and min of an array of 1 million values which is more than the maximum number of arguments to a function in most javascript implementation so I rewrote it a such: Array.prototype.min = function() { var increment = 50000; if(this.length > increment){ var reduced_array = []; for(var i=0;i<this.length;i+=increment) { reduced_array.push(Math.min.apply(Math, this.slice(i,i+increment-1))); } }else { return Math.min.apply(Math, this); } return reduced_array.min(); }; Array.prototype.max = function(array) { var increment = 50000; if(this.length > increment){ var reduced_array = []; for(var i=0;i<this.length;i+=increment) { reduced_array.push(Math.max.apply(Math, this.slice(i,i+increment-1))); } }else { return Math.max.apply(Math, this); } I'm sure someone can suggest a better way.
- qixxiq 16y ago
  They way you've done it seems fine, although if you're trying to find minimums of such large arrays in javascript I'd assume you're doing something wrong. Javascript really isn't a great choice of language for big processing tasks; stuff like that should be moved away where possible (granted it isn't always an option).
  - nkassis 16y ago
    Yeah I would not be doing it unless it was necessary. When I wrote that I was parsing a large file using javascript (from the client filesystem) and the round trip to the server would have been longer than this little function takes.
Tichy 16y ago
I don't like it if it is not documented that Math.max can take more than two arguments. Can we count on all future implementations to accept more than two arguments?
- smanek 16y ago
  It is documented everywhere I looked. Check out pg162 of http://www.ecma-international.org/publications/files/ECMA-ST/ECMA-262.pdf http://www.ecma-international.org/publications/files/ECMA-ST..., for example.
  - Tichy 16y ago
    OK - in the article (or the comments) it said that the documentation everywhere says two arguments only.
utkarshkukreti 16y ago
It might be faster to write the code, but it's definitely not the fastest way to find the minimum/maximum value. Some simple test cases I wrote show a simple for loop iterator over an array to be 2x faster than Math.min.apply in Firefox 4, and 3x faster in Chrome 10. http://jsperf.com/fastest-array-min-max http://jsperf.com/fastest-array-min-max
- dspillett 16y ago
  If you take out the (currently unused: it is updated but never referred to afterwards) the first-index-of-the-smallest-value-was-found-at variable the difference in FF is even larger. These are the results on FF 3.6.16 on my desktop: ~33.5 ops/sec (million test, using Array.min.apply) ~57.0 o/s (with index var) ~86.5 o/s (without index var) I'm a little surprised it makes that much difference (I assumed the two set operations, one of which I removed, would be less significant than that in the execution timings compared to the array object lookup in the comparison, given JS arrays aren't actually arrays strictly speaking). The difference may be less significant (zero, in fact) with a JS engine that does dead-code analysis that successfully works out that min_i is set in the loop but otherwise never used.
  - utkarshkukreti 16y ago
    Ah yes, there was no need of using min_i in my benchmark. That's a pretty big difference, and I wouldn't have expected that much of a difference for assigning one extra variable in the loop.
stevoski 16y ago
In the post, he asks this question: "What's the fastest way to find the largest, or smallest, number in an array?" I guess he means fastest code to write, not the fastest code to run. If you have, say, a million numbers, I'd try doing this using concurrency. If there are two CPUs (or cores), find the maximum in the bottom half of the array and the maximum in the top half in parallel. Then return the maximum of the two maximums. I don't know much JavaScript - does it have built-in support for concurrency?

62 points by DanielRibeiro 16y ago

Underscore.js is pretty good about delegating to built-in functions when available in its little utility functions. http://documentcloud.github.com/underscore/docs/underscore.html#section-25 http://documentcloud.github.com/underscore/docs/underscore.h...

tzury 16y ago
They surely missed this one though. as Underscore.js do this: _.max = function(obj, iterator, context) { if (!iterator && _.isArray(obj)) return Math.max.apply(Math, obj); var result = {computed : -Infinity}; each(obj, function(value, index, list) { var computed = iterator ? iterator.call(context, value, index, list) : value; computed >= result.computed && (result = {value : value, computed : computed}); }); return result.value; }; _.min = function(obj, iterator, context) { if (!iterator && _.isArray(obj)) return Math.min.apply(Math, obj); var result = {computed : Infinity}; each(obj, function(value, index, list) { var computed = iterator ? iterator.call(context, value, index, list) : value; computed < result.computed && (result = {value : value, computed : computed}); }); return result.value; }; While John do that: Array.max = function( array ){ return Math.max.apply( Math, array ); }; Array.min = function( array ){ return Math.min.apply( Math, array ); };
- alunny 16y ago
  The Underscore functions do exactly the same as Resig's in the simple case (when passed just an array of numbers). They're longer because they accept custom iterators for non-numerical arrays.
jashkenas 16y ago
The real reason why Underscore doesn't use "Math.max.apply" and "Math.min.apply", is that they only work on small arrays of numbers. After you get beyond 40-50,000-ish (last time I checked), some browsers will throw an exception because you can't pass that many arguments to a function. I remember running into this in real-world code, trying to calculate the brightest pixel in a <canvas> imageData array.

clvv 16y ago

> Posted: January 13th, 2007 That's four years ago.

gobongo 16y ago
> 4 points by clvv 2 hours ago | link | parent | flag That's 2 hours ago.

dionidium 16y ago

I started to feel pretty smug [0], at first. How could John Resig not know this? Then I saw that it was from 2007. Sheesh, I probably first learned about this trick from that post. [0] http://stackoverflow.com/questions/5020954/adding-functions-to-javascripts-array-class-breaks-for-loops/5021375#5021375 http://stackoverflow.com/questions/5020954/adding-functions-...

nkassis 16y ago

I used his technique for a while but then I had to find the max and min of an array of 1 million values which is more than the maximum number of arguments to a function in most javascript implementation so I rewrote it a such: Array.prototype.min = function() { var increment = 50000; if(this.length > increment){ var reduced_array = []; for(var i=0;i<this.length;i+=increment) { reduced_array.push(Math.min.apply(Math, this.slice(i,i+increment-1))); } }else { return Math.min.apply(Math, this); } return reduced_array.min(); }; Array.prototype.max = function(array) { var increment = 50000; if(this.length > increment){ var reduced_array = []; for(var i=0;i<this.length;i+=increment) { reduced_array.push(Math.max.apply(Math, this.slice(i,i+increment-1))); } }else { return Math.max.apply(Math, this); } I'm sure someone can suggest a better way.

qixxiq 16y ago
They way you've done it seems fine, although if you're trying to find minimums of such large arrays in javascript I'd assume you're doing something wrong. Javascript really isn't a great choice of language for big processing tasks; stuff like that should be moved away where possible (granted it isn't always an option).
- nkassis 16y ago
  Yeah I would not be doing it unless it was necessary. When I wrote that I was parsing a large file using javascript (from the client filesystem) and the round trip to the server would have been longer than this little function takes.

Tichy 16y ago

I don't like it if it is not documented that Math.max can take more than two arguments. Can we count on all future implementations to accept more than two arguments?

smanek 16y ago
It is documented everywhere I looked. Check out pg162 of http://www.ecma-international.org/publications/files/ECMA-ST/ECMA-262.pdf http://www.ecma-international.org/publications/files/ECMA-ST..., for example.
- Tichy 16y ago
  OK - in the article (or the comments) it said that the documentation everywhere says two arguments only.

utkarshkukreti 16y ago

It might be faster to write the code, but it's definitely not the fastest way to find the minimum/maximum value. Some simple test cases I wrote show a simple for loop iterator over an array to be 2x faster than Math.min.apply in Firefox 4, and 3x faster in Chrome 10. http://jsperf.com/fastest-array-min-max http://jsperf.com/fastest-array-min-max

dspillett 16y ago
If you take out the (currently unused: it is updated but never referred to afterwards) the first-index-of-the-smallest-value-was-found-at variable the difference in FF is even larger. These are the results on FF 3.6.16 on my desktop: ~33.5 ops/sec (million test, using Array.min.apply) ~57.0 o/s (with index var) ~86.5 o/s (without index var) I'm a little surprised it makes that much difference (I assumed the two set operations, one of which I removed, would be less significant than that in the execution timings compared to the array object lookup in the comparison, given JS arrays aren't actually arrays strictly speaking). The difference may be less significant (zero, in fact) with a JS engine that does dead-code analysis that successfully works out that min_i is set in the loop but otherwise never used.
- utkarshkukreti 16y ago
  Ah yes, there was no need of using min_i in my benchmark. That's a pretty big difference, and I wouldn't have expected that much of a difference for assigning one extra variable in the loop.

stevoski 16y ago

In the post, he asks this question: "What's the fastest way to find the largest, or smallest, number in an array?" I guess he means fastest code to write, not the fastest code to run. If you have, say, a million numbers, I'd try doing this using concurrency. If there are two CPUs (or cores), find the maximum in the bottom half of the array and the maximum in the top half in parallel. Then return the maximum of the two maximums. I don't know much JavaScript - does it have built-in support for concurrency?