数组大小114467好,114468不行

Question

我的alghoritm有一个奇怪的问题,如果数组大小小于114468则无效,如果大于114468则不起作用.使用谷歌浏览器浏览.无法理解为什么= \这里是代码:

生成数组:

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

在数组中查找第一个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)当阵列大小从114467增加到114468时,似乎放大了天文数字.

使用此自定义基准:

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

我得到3 ms了114467和2740ms为114468在Chrome(1000次迭代),但170每个在Firefox.也许你应该使用不同的方式来删除元素？使用冒泡排序的变体可能会更好.

我已经就此提交了一份错误报告.看看回复,它似乎是一个有效的错误.希望它能被修复.