3

1,000,000 の数字でテストしていますが、ちょっとぶら下がっています。1,000,000を簡単に通過できると思いました。それは私の実装ですか？のせいだと思いますがslice()、誰か考えはありますか？

編集：このメッセージを受け取りました： FATAL ERROR: CALL_AND_RETRY_2 Allocation failed - process out of memory

TopDownSplitMerge(numbersArray);
function TopDownSplitMerge(arrayOfNumbers) {     
    var length = arrayOfNumbers.length
    var middleIndex = parseInt(length/2);

    if(length <= 1) {
        return arrayOfNumbers;
    }                       

    // Split left side
    var left = TopDownSplitMerge(arrayOfNumbers.slice(0, middleIndex));  

    // Split right side
    var right = TopDownSplitMerge(arrayOfNumbers.slice(middleIndex, length));   

    // Merge every back together
    return TopDownMerge(left, right);
}

function TopDownMerge(left, right) {
    var results = []

    while(left.length || right.length) {
        console.log("looping...");

        // Check if both sides are NOT empty, if so, then just finish shifting the non-empty side
        if(left.length && right.length) { 
            if(left[0] <= right[0]) {
               results.push(left.shift()) 
            } else {
               results.push(right.shift()) 
            }
        } else if(left.length) {
           results.push(left.shift()) 
        } else {
           results.push(right.shift()) 
        }

    }

    console.log("Merging....", results.length);
    return results;
}
4

2 に答える 2

2

変更しなければならなかったことが2つあります

var right = TopDownSplitMerge(arrayOfNumbers.slice(middleIndex, length));

....
....
....

function TopDownMerge(left, right) {
    var results = [], leftLen = left.length, rightLen = right.length;

    for (var i = 0, j = 0; i < leftLen || j < rightLen;) {
        if (i < leftLen && j < rightLen) {
            if(left[i] <= right[j]) {
                results.push(left[i]);
                i += 1;
            } else {
                results.push(right[j]);
                j += 1;
            }
        } else if (i < leftLen) {
            results.push(left[i]);
            i += 1;
        } else {
            results.push(right[j]);
            j += 1;
        }
    }
    return results;
}

編集:スライスされた配列の代わりにインデックスを受け入れるように変更し、パフォーマンスをさらに向上させました。

function TopDownSplitMerge(arrayOfNumbers, start, end) {
    var length = end - start;
    var middleIndex = start + parseInt(length / 2);

    if (length <= 1) {
        return [arrayOfNumbers[start]];
    }

    // Split left side
    var left = TopDownSplitMerge(arrayOfNumbers, start, middleIndex);

    // Split right side
    var right = TopDownSplitMerge(arrayOfNumbers, middleIndex, length);

    // Merge every back together
    return TopDownMerge(left, right);
}
TopDownSplitMerge(numbersArray, 0, numbersArray.length);

Jsperf: http://jsperf.com/so-q-19341534

10,000,000 の数字を持つ私のソリューションの jsperf: http://jsperf.com/solution-to-so-q-19341534

于 2013-10-13T03:45:45.603 に答える
2

私はあなたが正しいと思います。slice()配列をコピーするため、配列を何億回も効果的にコピーしています。そしてshift、アレイの前面を外します。これには、毎回アレイをコピーする必要があります-さらに何十億回も。より良いアプローチは、「分割」のインデックス範囲を渡すことです。

于 2013-10-13T03:27:56.183 に答える