15

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
  • 15
  • 56
  • 102
user889030
  • 4,353
  • 3
  • 48
  • 51
  • 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

4 Answers4

18

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
  • 19,660
  • 16
  • 80
  • 92
  • 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
9
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,757
  • 3
  • 17
  • 29
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
0

Use min and max functions from lodash library, https://lodash.com/docs/4.17.15#max

You can pass arrays directly into them, as opposed to Math.max and Math.min functions and they work fine with huge arrays of numbers. I had a similar problem and got it resolved with functions from lodash.

Назар Мельник
  • 123
  • 1
  • 4