为什么这种1,000,000合并类型的实现需要这么长时间？

Question

我用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; 
} 

Answer 1

有两件事情我不得不改变

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

Answer 2

我认为你是对的。 slice()复制数组，因此您正在有效地复制数组bajillions次。然后你的阵列从阵列中移出，这需要每次复制阵列 - 多一次bajillion。一个更好的方法可能是通过索引范围进行“拆分”。