我的算法有一个奇怪的问题，它在数组大小小于 114468 时有效，而在大于 114468 时无效。使用谷歌浏览器浏览。无法理解为什么 =\这是代码:

生成数组:

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

查找数组中的第一个元素进行排序:

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

我有内存限制吗？

最佳答案

好的，我解决了这个问题。当数组大小从 114467 增加到 114468 时，splice(0,1) 似乎在天文数字上变慢了。

使用这个自定义基准:

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

在 Chrome 上，114467 得到 3 ms，114468 得到 2740ms(1000 次迭代)，但是 170 每个在 Firefox 上。也许你应该使用不同的方式来删除元素？使用 bubble sort 的变体可能效果更好。

我已经提交了 bug report对此。查看回复，似乎是一个有效的错误。希望它会得到修复。

关于javascript - 数组大小 114467 好，114468 不行，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10568018/