Formato array 114467 buono, 114468 non funziona

Question

Ho uno strano problema con il mio alghoritm, che funziona se la dimensione dell'array è inferiore a 114468 e non funziona se oltre 114468. Sfoglia con google chrome. Non riesco a capire il motivo per cui = \ Ecco il codice:

Genera matrice:

Trova primo elem in ordine per ordinare:

 for (var i = 0, j = arr.length; i < j && res.length == 0; i++) { 
      var found = false; 
      for (var m = 0; m < j; m++) { 
       if (i == m || arr[i][0] == arr[m][1] || arr[i][1] == arr[m][0]) { 
        found = true; 
        break; 
       } 

       if (!found) { 
        res.push(arr[m]); 
        arr.splice(m, 1); 
       } 
      } 
     } 

Ordinamento:

 do { 
      for (var i = 0, j = arr.length; i < j; i++) { 
       var resLength = res.length - 1; 
       if (arr[i][1] == res[resLength][0] || arr[i][0] == res[resLength][1]) { 
        res.push(arr[i]); 
        arr.splice(i, 1); 
        break; 
       } 
      } 
     } while (arr.length > 0); 

In fase di ordinamento smette di funzionare.

Tutto il codice:

var t = function() { 
    var arr = []; 
    var res = []; 
    for (var i = 114467; i > 0; i--) { 
     arr.push([i - 1, i]); 
    } 

    var startsec = new Date().getSeconds(); 
    var startmilsec = new Date().getMilliseconds(); 
    document.write(startsec + '.' + startmilsec + '<br>'); 

    for (var i = 0, j = arr.length; i < j && res.length == 0; i++) { 
     var found = false; 
     for (var m = 0; m < j; m++) { 
      if (i == m || arr[i][0] == arr[m][1] || arr[i][1] == arr[m][0]) { 
       found = true; 
       break; 
      } 

      if (!found) { 
       res.push(arr[m]); 
       arr.splice(m, 1); 
      } 
     } 
    } 

    do { 
     for (var i = 0, j = arr.length; i < j; i++) { 
      var resLength = res.length - 1; 
      if (arr[i][1] == res[resLength][0] || arr[i][0] == res[resLength][1]) { 
       res.push(arr[i]); 
       arr.splice(i, 1); 
       break; 
      } 
     } 
    } while (arr.length > 0); 

    var stopsec = new Date().getSeconds(); 
    var stopmilsec = new Date().getMilliseconds(); 
    document.write(stopsec + '.' + stopmilsec + '<br>'); 
    var executionTime = (stopsec - startsec).toString() + "s" + (stopmilsec - startmilsec).toString() + "'ms"; 
    document.write(executionTime + '<br>'); 
}(); 

faccio ad avere il mio limite di memoria?

Answer 1

OK, ho isolato il problema. Sembra che splice(0,1) rallenta astronomicamente quando la dimensione della matrice aumenta da 114467 a 114468.

Utilizzando questo benchmark personalizzato:

var t; 
function startBench(){t=new Date().getTime();} 
function stopBench(){console.log(new Date().getTime()-t);} 
var arr=[]; 
    for (var i = 114467; i > 0; i--) { 
     arr.push([i - 1, i]); 
    } 
var arr2=[]; 
    for (var i = 114468; i > 0; i--) { 
     arr2.push([i - 1, i]); 
    } 
startBench(); 
for(i=0;i<1000;i++){ 
arr.splice(0,1); 
} 

stopBench(); 
startBench(); 
for(i=0;i<1000;i++){ 
arr2.splice(0,1); 
} 
stopBench(); 

ricevo 3 ms per 114467 e 2740ms per 114468 su Chrome (1000 iterazioni), ma 170 ciascuno su Firefox. Forse dovresti usare un modo diverso per rimuovere gli elementi? L'utilizzo di una variante di bubble sort potrebbe funzionare meglio.

Ho inviato un bug report su questo. Guardando la risposta, è sembra essere un errore valido. Speriamo che venga risolto.