Array size 114467 good, 114468 not working

Question

I have a strange problem with my alghoritm, which works if the array size is less than 114468 and does not work if it is larger than 114468. Browse using google chrome. I can’t understand why = \ Here is the code:

Generate an array:

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

Find the first element in the array to sort:

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

Sorting:

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

When sorting steps, it stops working.

All code:

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

Can I get a memory limit?

Answer 1

Ok, I isolated the problem. It seems that splice(0,1) slows down astronomically when the size of the array increases from 114467 to 114468.

Using this custom test:

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

I get 3 ms for 114467 and 2740ms for 114468 in Chrome (1000 iterations), but 170 each in Firefox. Maybe you should use a different way to delete items? Using a bubble type option may work better.

I sent a bug report . Looking at the answer, this seems like a real mistake. Hope this will be fixed.