7

我的算法有一个奇怪的问题，如果数组大小小于 114468，则该算法有效，如果大于 114468，则该算法无效。使用 google chrome 浏览。不明白为什么=\ 这是代码：

生成数组：

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

我有内存限制吗？

4

1 回答 1

16

好的，我隔离了问题。当数组大小从 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（1000 次迭代）上获得3 ms了 for 114467and 2740msfor ，但每次都在 Firefox 上。也许您应该使用不同的方式来删除元素？使用冒泡排序的变体可能会更好。114468170

我已经提交了关于此的错误报告。查看回复，这似乎是一个有效的错误。希望它会得到修复。

于 2012-05-15T17:02:32.893 回答