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

問題を切り分けました。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();

Chrome (1000 回の反復) では3 msfor 114467and 2740msforを取得しますが、Firefox ではそれぞれ取得します。たぶん、要素を削除する別の方法を使用する必要がありますか? バブル ソートの変形を使用すると、うまくいく場合があります。114468170

これに関するバグレポートを提出しました。返信を見ると、有効なバグのようです。うまくいけば、それは修正されるでしょう。

于 2012-05-15T17:02:32.893 に答える