I need to calculate min/max of large array. I know about Math.max.apply(), but on large arrays it fails with Stack overflow exception. Any simple solutions?
-
1Obvious question: How large?gdoron– gdoron2013-06-05 18:21:02 +00:00Commented Jun 5, 2013 at 18:21
-
like 100 000 elementsAlexey Timanovsky– Alexey Timanovsky2013-06-05 18:22:01 +00:00Commented Jun 5, 2013 at 18:22
-
1Why are you processing data that large on the client side?George Cummins– George Cummins2013-06-05 18:22:13 +00:00Commented Jun 5, 2013 at 18:22
-
5I didn't say anything about client sideAlexey Timanovsky– Alexey Timanovsky2013-06-05 18:25:32 +00:00Commented Jun 5, 2013 at 18:25
-
True, but there are better ways to do it on the server side than Javascript, so I made an assumption. Why Javascript?George Cummins– George Cummins2013-06-05 18:28:23 +00:00Commented Jun 5, 2013 at 18:28
|
Show 1 more comment
7 Answers
Sort the array by using
sort()method it sorts array by using quicksort algorithmSince array is sorted in ascending order then the last element is the max
var arr = [1,4,6,4, ...]; arr.sort((a, b) => a - b); var max = arr[arr.length - 1];
5 Comments
Alexey Timanovsky
You answer made me feel really stupid :(. In fact I already have sorted array. That's why you want code reviews...
Nick
Just keep it DRY = Don't Repeat Yourself :)
David Sherret
It's only worth sorting the array if you're going to be doing some binary searches [O(log n)] on the array anyways. If you want to get the max and min you might as well loop through every element since O(n) is faster than O(n log n). For lots of large arrays this might matter...
Alexey Timanovsky
Sure. I have sorted array in order to calculate percentiles. Having min/max is a nice side effect :)
micahbf
You can slightly simplify this by sorting in descending order, which allows just getting the first element. I.e.
arr.sort((a, b) => b - a)[0]Array.prototype.min = function() {
var r = this[0];
this.forEach(function(v,i,a){if (v<r) r=v;});
return r;
};
From JavaScript: min & max Array values? where other solutions from this problem are discussed
FYI: I just googled "max min large array" and found this as the first result...
2 Comments
Alexey Timanovsky
I saw that thread, but didn't go through all of it, thanks :)
apsillers
For reference, the exact answer there that addresses large arrays is this one: stackoverflow.com/a/8986992/710446
Why not just loop through the entire array?
var max = Number.MIN_VALUE, min = Number.MAX_VALUE;
for (var i = 0, len=list.length; i < len; i++) {
if (list[i] > max) max = list[i];
if (list[i] < min) min = list[i];
}
Edit:
For max:
if (typeof Array.prototype.GetMax === "undefined") {
Array.prototype.GetMax = function() {
var max = Number.MAX_VALUE;
for (var i = 0, len=this.length; i < len; i++) {
if (this[i] > max) max = this[i];
}
return max;
}
}
For min:
if (typeof Array.prototype.GetMin === "undefined") {
Array.prototype.GetMin = function() {
var min = Number.MIN_VALUE;
for (var i = 0, len=this.length; i < len; i++) {
if (this[i] < min) min = this[i];
}
return min;
}
}
For both:
if (typeof Array.prototype.GetMaxMin === "undefined") {
Array.prototype.GetMaxMin = function() {
var max = Number.MIN_VALUE, min = Number.MAX_VALUE;
for (var i = 0, len=this.length; i < len; i++) {
if (this[i] > max) max = this[i];
if (this[i] < min) min = this[i];
}
return { Max: max, Min: min};
}
}
4 Comments
Sirko
Just init
min/max with Number.MAX_VALUE/Number.MIN_VALUE. Then you can drop the first if condition.
Comfortably Numb
And this can be added to array.prototype to make it easier to use
David Sherret
I never knew Number.MAX_VALUE existed in javascript. Cool!
RiaD
BTW, I'd initialize it using first element to support non-numeric values too
Should I assume you have thought of this:
var maxSoFar = -9999999;
for (var i = 0; i < array.length ; ++i) {
if (array[i] > maxSoFar) {
maxSoFar = array[i];
}
... similar for minSoFar ...
}
1 Comment
Alexey Timanovsky
Yes, I thought... I was looking for something more functional style :)
try this
var arr = [];
for(var i=1000000;i>0;i--)
{
arr.push(i);
}
//we create a copy of the original array through arr.concat() since we do not want to change the original sorting order of the array
//we pass a function in the sort method as by default it sorts alphabetically instead of numerically. So 99 will be smaller than 100.
var arrMaxMin = arr.concat().sort(function(a,b){return a-b});
arrMaxMin[0]; //min
arrMaxMin[arrMaxMin.length - 1]; //max
Comments
Hey why dont you slice your array into smaller arrays then on that arrays you can easily use Math.max.apply(Math,individual arrays).But remember to reinitialize all subarrays back to null so as to get the memory back once desired max value is obtained
Comments
This is exactly what reduce is for:
function max(arr) {
if (arr.length === 0) {
return NaN // or whatever answer you want for an empty array, or throw an error.
}
return arr.reduce((a, b) => Math.max(a, b), -Infinity)
}
console.log(max([...new Array(100000).keys()]))
(note that [...new Array(100000).keys()] is just a fancy way in a modern browsers to make a huge array of the numbers 0 to 999999. The max function itself will run in anything made in the last 20 years.)
You can also reduce it to this one-liner:
arr.reduce((cur, val, i) => i === 0 ? val : Math.max(cur, val), NaN)
here NaN is the value you get back if the array is empty
Or even
arr.reduce((a, b) => Math.max(a, b), -Infinity)
although this will return -Infinity for an empty array.
Finally, it may be tempting to just do:
arr.reduce(Math.max, -Infinity) //don't do this!!
but this won't work. This is because reduce calls it's function (Math.max) with 4 parameters, one of which is the original array, so a Math.max on those will always result in a NaN.
