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

有两件事我必须改变

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

jsperf 用于我的 10,000,000 个数字的解决方案：http: //jsperf.com/solution-to-so-q-19341534

于 2013-10-13T03:45:45.603 回答
2

我觉得你是对的。slice()复制数组，因此您有效地复制了数组 bajillions 次。然后你shift把数组的前面去掉，这需要每次都复制数组——无数次。更好的方法可能是传递“拆分”的索引范围。

于 2013-10-13T03:27:56.183 回答