Tamaño de la matriz 114467 bien, 114468 no funciona

Question

Tengo un problema extraño con mi alghoritm, que funciona si el tamaño de la matriz es menor que 114468 y no funciona si hay más de 114468. Navegue con google chrome. No se puede entender por qué = \ Este es el código:

Generar matriz:

Buscar la primera elem en orden para ordenar:

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

Clasificación:

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

En la clasificación por pasos, deja de funcionar.

Todo el código:

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>'); 
}(); 

hago para que mi límite de memoria?

Answer 1

Muy bien, he aislado el problema. Parece que splice(0,1) ralentiza astronómicamente cuando el tamaño del array aumenta de 114467 a 114468.

El uso de este índice de referencia:

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

consigo 3 ms para 114467 y 2740ms para 114468 en Chrome (1000 iteraciones), pero 170 cada uno en Firefox. ¿Tal vez deberías estar usando una forma diferente de eliminar elementos? Usar una variante de bubble sort puede funcionar mejor.

He enviado un bug report sobre esto. Mirando la respuesta, parece ser un error válido. Espero que sea arreglado.