ऐरे आकार 114467 अच्छा, 114468 काम नहीं

Question

मुझे अपने alghoritm के साथ एक अजीब समस्या है, जो 114468 से कम सरणी आकार का काम करता है और 114468 से अधिक काम नहीं करता है। Google क्रोम के साथ ब्राउज़ करें। समझ में नहीं आता क्यों = \ यहाँ कोड है:

उत्पन्न सरणी:

सॉर्ट करने के लिए सरणी में पहले ELEM खोजें:

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

मैं अपने स्मृति सीमा मिलता है?

Answer 1

ठीक है, मैंने समस्या को अलग कर दिया। ऐसा लगता है कि splice(0,1) नीचे astronomically धीमा कर देती है जब सरणी आकार 114468.

करने के लिए 114467 से बढ़ जाती है इस कस्टम बेंचमार्क का उपयोग करना: क्रोम पर

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

मैं 114467 के लिए 3 ms हो और 2740ms114468 के लिए (1000 पुनरावृत्तियों), लेकिन फ़ायरफ़ॉक्स पर 170 प्रत्येक। शायद आपको तत्वों को हटाने के लिए एक अलग तरीके का उपयोग करना चाहिए? bubble sort का एक संस्करण का उपयोग करना बेहतर काम कर सकता है।

मैंने इस पर bug report सबमिट किया है। उत्तर को देखते हुए, यह एक वैध बग होने के लिए लगता है। उम्मीद है कि यह तय किया जाएगा।