Array size 114467 good, 114468 not work

javascript

Solution

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

Using this custom benchmark:

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` on Chrome (1000 iterations), but `170` each on Firefox. Maybe you ought to be using a different way to remove elements? Using a variant of bubble sort may work better.

I've submitted a bug report on this. Looking at the reply, it seems to be a valid bug. Hopefully it'll be fixed.

Problem

I have a strange problem with my alghoritm, which work if array size less than 114468 and doesn't work if more than 114468. Browse with google chrome. Can't understand why =\ Here is the code: Generate array: ``` var arr = []; var res = []; for (var i = 114467; i > 0; i--) { arr.push([i - 1, i]); } ``` Find first elem in 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); ``` On the step sorting it stops to work. 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>'); } (); ``` Do i get my memory limit?

Original source