1

在大小不超过 N = ~1950 左右的较小列表上，我得到了正确的输出......但是，大小不大的列表会返回错误而不是预期的结果。我的代码：

def merge(left, right, aux=[]):
    if left == []:
        for x in right:
            aux.append(x)
        return aux
    elif right == []:
        for x in left:
            aux.append(x)
        return aux
    elif left[0] > right[0]:
        aux.append(right[0])
        return merge(left, right[1:], aux)
    else:
        aux.append(left[0])
        return merge(left[1:], right, aux)

def msort(values):
    size = len(values)

    if size == 1:
        return values
    else:
        mid = size/2
        return merge(msort(values[:mid]), msort(values[mid:]), [])

在这些测试列表上运行msort会给我预期的（升序）输出：

val = [x for x in range(1950, 0, -1)
val = [x for x in range(4,0,-1)]

例如 [1,2,3,...,1948,1949,1950] 和 [1,2,3,4]

但是，当我msort在这个测试用例上运行时：

val = [x for x in range(2000,0,-1)]

我现在收到此错误（经过多次回溯merge）：

RuntimeError: maximum recursion depth exceeded in cmp

所以我的问题是：我在这里的实现出了什么问题？我不能将它与 N ~ >=2000 的列表一起使用。为什么？

4

4 回答 4

4

问题是您正在递归地进行合并。正如所指出的， call 很好merge(msort(left),msort(right))，但是由于您的merge函数实际上调用自己进行合并，因此您达到了递归限制。

merge考虑在长度为 1000 的列表上调用您的函数。

aux要合并这些列表，您需要 2000 次合并调用（因为每次调用只需添加 ~1 个元素）。

于 2013-04-26T13:29:29.457 回答
2

您的合并函数使用有限制的递归。

如果你迭代而不是重复你绕过这个：

def merge(left, right, aux=[]):
    while left and right:
        if left[0] > right[0]:
            aux.append(right.pop(0))
        else:
            aux.append(left.pop(0))
    aux.extend(right)
    aux.extend(left)
    return aux

这是一个用法示例：

>>> merge([1,3,5,7], [3,4,5,6])
[1, 3, 3, 4, 5, 5, 6, 7]
于 2013-04-26T13:27:12.287 回答
0

您已达到最大递归深度。

这意味着，您的函数msort调用自身的频率高于默认情况下 python 允许的调用频率。

您可以使用sys.setrecursionlimit增加此默认值。

于 2013-04-26T13:20:03.810 回答
0

Python 有递归限制。您可以使用以下方法设置最大值（小心）：

import sys
sys.setrecursionlimit(MAXRECURSION)

我能够运行您的列表

val = [x for x in range(2000,0,-1)]

MAXRECURSION 为 2500

于 2013-04-26T13:20:50.837 回答