10

I have js function to find min and max values in 2d array which works ok on small arrays but when I pass it big array it give me range error:

Maximum call stack size exceeded.

I am using the latest version of Chrome.

function MaxMin2dray(arr, idx){
    return {
       min: Math.min.apply(null, arr.map(function (e) { return e[idx]})),
        max: Math.max.apply(null, arr.map(function (e) { return e[idx]}))
  }
}
Tân
  • 1
  • 14
  • 51
  • 92
user889030
  • 3,643
  • 2
  • 41
  • 50
  • 2
    Function.prototype.apply can only receive array of limited length as its second argument. You should find the min and max manually – Weedoze Mar 06 '17 at 10:29
  • At least, you can optimize your function and remove redundant Array.prototype.map() function call on the same array – RomanPerekhrest Mar 06 '17 at 10:30
  • 3
    More accurately: each argument takes up space on the stack, and passing too many arguments to any function will cause a stack overflow. – Ry- Mar 06 '17 at 10:31
  • `big array` - big alright, chrome *only* handles up to 125519 - other browsers can handle up to 4 times that – Jaromanda X Mar 06 '17 at 10:47

3 Answers3

14

Math.min & Math.max

The Math.min and Math.max most likely crash, or return NaN for big arrays (~10⁷)

(see @DavidWaters & @EugeneGluhotorenko comments).

Instead, you can use old javascript loops like so:

(2nd func is much faster)

function getMax(arr) {
    return arr.reduce((max, v) => max >= v ? max : v, -Infinity);
}

Or

function getMax(arr) {
    let len = arr.length;
    let max = -Infinity;

    while (len--) {
        max = arr[len] > max ? arr[len] : max;
    }
    return max;
}
  • Tested with 1,000,000 items:
    1st function running time (on my machine) was 15.84ms Vs. 2nd function with only 4.32ms.
Lior Elrom
  • 17,742
  • 16
  • 75
  • 90
  • Do you have a documentation or code reference that indicates they are recursive operations? – neverendingqs Mar 27 '19 at 15:48
  • 1
    @neverendingqs, that's a fair question :) When using big arrays, we get a `Maximum call stack size exceeded` error. It means that the stack size is bigger than what JS engine can handle. This type of error is commonly happen when using a large number of recursions. If you, or anyone else, can find a reference in the V8 code and bring more substantial evidence that would be even better. – Lior Elrom Mar 31 '19 at 02:44
  • I'm interested in exactly that :) – neverendingqs Mar 31 '19 at 16:54
  • 1
    Looking at the current code https://chromium.googlesource.com/v8/v8/+/4.3.21/src/math.js?autodive=0%2F%2F#85 Chrome and Nodes built in Javascript uses a for loop for Math.Max and Math.Min. I have not looked to see if this has changed since the question was asked, or if it about how the functions were called. – David Waters Dec 23 '20 at 19:52
  • 1
    Not really. These functions are not recursive (see v8 sources in the comment above). The problem is in the amount of function parameters after destructuring. Here is more details on how stack works https://stackoverflow.com/a/53493938/438084. – Eugene Gluhotorenko Mar 24 '21 at 12:06
  • 1
    @EugeneGluhotorenko & DavidWaters Thank you for clearing this out. I updated the answer to reflect your findings +1 – Lior Elrom Mar 24 '21 at 14:29
6
function minMax2DArray(arr, idx) {
    var max = -Number.MAX_VALUE,
        min = Number.MAX_VALUE;
    arr.forEach(function(e) {
        if (max < e[idx]) {
            max = e[idx];
        }
        if (min > e[idx]) {
           min = e[idx];
       }
    });
    return {max: max, min: min};
}

Edit: Removed use of MIN_VALUE (see post below).

Modernized version

const arrayMinMax = (arr) =>
  arr.reduce(([min, max], val) => [Math.min(min, val), Math.max(max, val)], [
    Number.POSITIVE_INFINITY,
    Number.NEGATIVE_INFINITY,
  ]);
bjornl
  • 1,509
  • 3
  • 16
  • 28
5

There is a issue in bjornl's answer. According to https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Number/MIN_VALUE

The MIN_VALUE property is the number closest to 0, not the most negative number, that JavaScript can represent.

The updated code:

function minMax2DArray(arr, idx) {
    var max = -Number.MAX_VALUE,
        min = Number.MAX_VALUE;
    arr.forEach(function(e) {
        if (max < e[idx]) {
            max = e[idx];
        }
        if (min > e[idx]) {
           min = e[idx];
       }
    });
    return {max: max, min: min};
}
Roy Yin
  • 51
  • 1
  • 3