Ruby：堆栈级别太深（SystemStackError）实施合并排序倒数计数

Question

这是我的代码。

@@inversions = 0 
numbers = [very big array] 

def merge_sort(array) 
    return array if array.size <= 1 

    left = array.slice(0, (array.size/2).round) 
    right = array - left 
    merge(merge_sort(left), merge_sort(right)) 
end 

def merge(left, right) 
    return right if left.empty? # crashes here with stack level too deep 
    return left if right.empty? 

    if left.first <= right.first 
    [left.first] + merge(left[1..-1], right) 
    else 
    @@inversions += left.size 
    [right.first] + merge(left, right[1..-1]) 
    end 
end 

请问您为什么会失败？ （对数组工作不到〜15000大小）

Answer 1

你的递归合并功能可能是原因。对于数组中的每个元素，您将在堆栈中进一步深入一层。标准合并排序不应超过lg（N）。尝试重写merge以迭代而不是递归。

喜欢的东西

def merge left,right 
    a = [] 
    while !left.empty? and !right.empty? 
    if left.first < right.first 
     a<<left.shift 
    else 
     a<<right.shift 
    end 
    end 
    a + left + right 
end 

Answer 2

这是因为集堆栈尺寸太小，研究如何增加它！

Answer 3

你跑出书库的 - 很明显 - 但我认为你需要知道这是什么意思所以这里的一些理论。我基于古老的“大会”，但这是一个普遍的问题。

在计算机体系结构有专门作为一个“堆”，这usuaully是一个LIFO（后进先出）“暂存器”的芯片的面积。数据有时是自动的，有时在程序员的选择中被“推入”和“弹出”入堆栈。

有有限长度到该堆栈（以* 86溢出该堆叠覆盖芯片（EIP）是用于改变PROGRM流量控制，但无论如何经典黑客技术的其他特殊区域...

在你的程序每次递归或方法调用时，堆栈被加载调用代码的返回地址（所以它可以返回并继续），这是什么原因造成的堆栈溢出。