Chrome: Wie zu lösen "Maximale Call-Stack-Größe überschritten" Fehler in Math.max.apply (Math, Array)

Question

Ich muss den maximalen und minimalen Wert von sehr großen Arrays zu finden. Dafür verwende ich

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

Es funktioniert gut auf Firefox und IE, aber auf Chrome habe ich immer Maximum call stack size exceeded Fehler ... meine aktuelle Array hat 221.954 Elemente, und das ist nicht meine größte.

Kann jemand diesen Fehler in Chrome lösen? Wie kann ich die Suche nach Max- und Min-Werten optimieren?

Für diejenigen, die nicht glauben können, versuchen Sie dies in der Konsole von Chrome:

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

---> Auslöser Range: Maximale Call-Stack Größe

überschritten

Answer 1

Für mich den Fehler sollte nicht Von dem Aufruf in Math.min/max kommend, sieht es wie das Ergebnis der Rekursion aus, was ich nicht glauben kann, würde Chrome verwenden, um diese Funktionen zu implementieren.

Sind sie im rekursiven Code eingebettet?

Sie können Ihren eigenen Min/Max-Code trivial aufstellen, um das Problem in Chrome zu vermeiden.

Answer 2

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 rekursive Methode verwenden kann max-Wert zu erhalten, nur eine Iteration Funktion umschreiben max instead.This bekommen Auslöser Range vermeiden.

Answer 3

Sie erreichen die Größenbeschränkung für Funktionsparameter. Und es ist OK. Funktion sollte nur ein paar Parameter akzeptieren, da sonst ein Code Geruch ist.

Wenn Sie eine Reihe von Elementen haben? - Verwenden Sie Array. Sie verwenden .apply(), die Argumente wie folgt übergibt: fun(1,2,3,4,5,6....) und erreicht das Limit. Dies ist eine schlechte Praxis.

Das Problem ist - Math.max() ist nur so funktioniert, so Ihre beste Wette wäre iterative Suchfunktion. Aber das ist ein anderes Thema, da Leistung und Algorithmus zum Beispiel variieren können, wenn Sie das Array zum ersten Mal sortieren.

Answer 4

Dieses Problem hat nichts speziell mit Math.max und Math.min zu tun.

Function.prototype.apply kann nur ein Array mit begrenzter Länge als zweites Argument erhalten.

Lokal Getestet habe ich es in Chrome:

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

Lokal Grenze (l) abgestürzt genau mit l = 124980. In Kanarienvogel, dass eine andere Nummer, aber auch ~ 125k.

Dies ist ein Beispiel Erklärung, warum das passiert: https://code.google.com/p/v8/issues/detail?id=2896 (es ist auch reprodusible in anderen JS-Motoren, zum Beispiel MDN eine Erwähnung des Themas hat: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Function/apply#Using_apply_and_built-in_functions (Beginnend mit „Aber Vorsicht ...“), was auf Dieses Problem in WebKit Bugzilla: https://bugs.webkit.org/show_bug.cgi?id=80797).Soweit ich verstehe, warum RangeError in V8 geworfen wird:

V8 implementiert Function.prototype.apply in Assembly. Bevor die Funktion aufgerufen wird, sollte sie alle Funktionsaufrufparameter, z. ThisArg, und alle Mitglieder des 2. Arg-Arrays, eins nach dem anderen, auf Stapel, vor dem Aufruf der Javascript-Funktion. Aber der Stack hat eine begrenzte Kapazität, und wenn Sie das Limit erreichen, erhalten Sie RangeError.

Dies ist, was ich in V8-Quelle (IA-32-Baugruppe, builtins-ia32.cc) gefunden habe:

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); 

Bitte überprüfen !! ZUSÄTZLICHER KOMMENTAR für Erklärungen, wie ich es verstehe.

Und das ist APPLY_OVERFLOW Funktion, in JS geschrieben (auch hier Quelle V8, runtime.js):

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

EDIT: In Ihrem Fall würde ich gehen wie:

var max = -Infinity; 
for(var i = 0; i < arr.length; i++) if (arr[i] > max) max = arr[i];