15

我必须找到非常大的数组的最大值和最小值。为此，我正在使用

Math.max.apply(Math, my_array);
Math.min.apply(Math, my_array);

它在 Firefox 和 IE 上运行良好，但在 Chrome 上我总是Maximum call stack size exceeded出错......我当前的数组有 221954 个元素，这不是我最大的。

有人知道如何在 Chrome 上解决此错误吗？如何优化最大值和最小值的搜索？

对于那些不敢相信的人，在 Chrome 的控制台中试试这个：

var xxx = []
for(var i=0; i<300000; i++){
    xxx.push(Math.random());
}
Math.max.apply(Math, xxx);

---> RangeError: 超出最大调用堆栈大小

4

4 回答 4

22

这个问题与 Math.max 和 Math.min 无关。

Function.prototype.apply 只能接收长度有限的数组作为其第二个参数。

在本地，我使用以下方法在 Chrome 中对其进行了测试：

function limit(l) {
  var x = []; x.length = l;
  (function (){}).apply(null, x);
}

在本地，limit(l) 在 l = 124980 时完全崩溃。在金丝雀中，这是另一个数字，但也是 ~125k。

这是一个解释为什么会发生这种情况的示例：https ://code.google.com/p/v8/issues/detail?id= 2896（它在其他 JS 引擎中也可以重现，例如 MDN 提到了这个问题：https ://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Function/apply#Using_apply_and_built-in_functions （以“但当心...”开头），指向WebKit中的这个问题bugzilla：https ://bugs.webkit.org/show_bug.cgi?id=80797 ）。据我了解为什么 RangeError 在 V8 中被抛出：

V8 在汇编中实现了 Function.prototype.apply。在调用函数之前，它应该在调用javascript函数之前将所有函数调用参数，例如thisArg，以及第二个arg数组的所有成员一一放入堆栈。但是堆栈的容量是有限的，如果达到限制，就会得到 RangeError。

这是我在 V8 源代码（IA-32 程序集，builtins-ia32.cc）中找到的：

void Builtins::Generate_FunctionApply(MacroAssembler* masm) {
  static const int kArgumentsOffset = 2 * kPointerSize;
  static const int kReceiverOffset = 3 * kPointerSize;
  static const int kFunctionOffset = 4 * kPointerSize;
  {
    FrameScope frame_scope(masm, StackFrame::INTERNAL);

    __ push(Operand(ebp, kFunctionOffset));  // push this
    __ push(Operand(ebp, kArgumentsOffset));  // push arguments
    __ InvokeBuiltin(Builtins::APPLY_PREPARE, CALL_FUNCTION);

    // Check the stack for overflow. We are not trying to catch
    // interruptions (e.g. debug break and preemption) here, so the "real stack
    // limit" is checked.
    Label okay;
    ExternalReference real_stack_limit =
        ExternalReference::address_of_real_stack_limit(masm->isolate());
    __ mov(edi, Operand::StaticVariable(real_stack_limit));
    // Make ecx the space we have left. The stack might already be overflowed
    // here which will cause ecx to become negative.
    // !! ADDED COMMENT: IA-32 stack grows downwards, if address to its current top is 0 then it cannot be placed any more elements into. esp is the pointer to stack top.
    __ mov(ecx, esp);
    // !! ADDED COMMENT: edi holds the "real_stack_limit", which holds the  minimum address that stack should not grow beyond. If we subtract edi from ecx (=esp, or, in other words, "how much space is left on the stack"), we may get a negative value, and the comment above says that
    __ sub(ecx, edi);
    // Make edx the space we need for the array when it is unrolled onto the
    // stack.
    // !! ADDED COMMENT: eax holds the number of arguments for this apply call, where every member of the 2nd argument array counts as separate argument
    __ mov(edx, eax);
    // !! ADDED COMMENT: kPointerSizeLog2 - kSmiTagSize is the base-2-logarithm of how much space would 1 argument take. By shl we in fact get 2^(kPointerSizeLog2 - kSmiTagSize) * arguments_count, i.e. how much space do actual arguments occupy
    __ shl(edx, kPointerSizeLog2 - kSmiTagSize);
    // Check if the arguments will overflow the stack.
    // !! ADDED COMMENT: we compare ecx which is how much data we can put onto stack with edx which now means how much data we need to put onto stack
    __ cmp(ecx, edx);
    __ j(greater, &okay);  // Signed comparison.

    // Out of stack space.
    __ push(Operand(ebp, 4 * kPointerSize));  // push this
    __ push(eax);
    __ InvokeBuiltin(Builtins::APPLY_OVERFLOW, CALL_FUNCTION);

请检查 ！！添加评论以解释我如何理解它。

这是 APPLY_OVERFLOW 函数，用 JS 编写（同样，V8 源代码，runtime.js）：

function APPLY_OVERFLOW(length) {
  throw %MakeRangeError('stack_overflow', []);
}

编辑：在你的情况下，我想：

var max = -Infinity; 
for(var i = 0; i < arr.length; i++ ) if (arr[i] > max) max = arr[i];
于 2014-01-05T23:06:54.650 回答
1

您已达到函数参数大小限制。没关系。_ 函数应该只接受几个参数，否则就是代码异味。

如果你有一堆物品？- 使用数组。您正在使用.apply()which 传递参数，例如：fun(1,2,3,4,5,6....)并达到限制。这是不好的做法。

问题是 -Math.max()只能像这样工作，所以你最好的选择是迭代搜索功能。但这是另一个话题，因为性能和算法可能会有所不同，例如，如果您首先对数组进行排序。

于 2013-10-03T14:18:04.857 回答
0 
var a=[]; 
for(var i=0;i<1125011;i++){ 
    a[i] = i;
}
function maxIterate(arr){
    var max = arr[0];
    for(var i = 1;i< arr.length; i++){
        (max < arr[i]) && (max = arr[i])
    }
    return max;
}
console.log(maxIterate(a));

Math.max可以使用递归方法获取最大值，只需重写一个迭代函数来获取最大值。这样可以避免 RangeError。

于 2013-08-19T09:11:42.247 回答
0

对我来说，错误不应该来自对 Math.min / max 的调用，它看起来像是使用递归的结果，我无法相信 Chrome 会使用它来实现这些功能。

它们是否嵌入在递归代码中？

您可以轻松滚动自己的最小/最大代码以避免 Chrome 中的问题。

于 2013-08-19T08:10:59.583 回答