Kích thước mảng 114467 tốt, 114468 không hoạt động

Question

Tôi có vấn đề lạ với alghoritm của tôi, hoạt động nếu kích thước mảng nhỏ hơn 114468 và không hoạt động nếu có nhiều hơn 114468. Duyệt bằng google chrome. không thể hiểu tại sao = \ Đây là mã:

Tạo mảng:

Tìm elem đầu tiên trong mảng để sắp xếp:

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

Phân loại:

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

Trên bước phân loại, nó dừng hoạt động.

Tất cả các mã:

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

Do tôi nhận được giới hạn bộ nhớ của tôi không?

Answer 1

Được rồi, tôi đã tách sự cố. Dường như splice(0,1) chậm thiên văn khi kích thước mảng tăng từ 114.467 đến 114468.

Sử dụng này benchmark tùy chỉnh:

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

tôi nhận được 3 ms cho 114467 và 2740ms cho 114468 trên Chrome (1000 lặp lại), nhưng 170 mỗi trên Firefox. Có lẽ bạn nên sử dụng một cách khác để loại bỏ các yếu tố? Sử dụng biến thể của bubble sort có thể hoạt động tốt hơn.

Tôi đã gửi bug report về điều này. Nhìn vào câu trả lời, nó có vẻ như là một lỗi hợp lệ. Hy vọng rằng nó sẽ được cố định.