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

問題は、マージを再帰的に行っていることです。指摘したように、 を呼び出すのは問題ありませんmerge(msort(left),msort(right))が、merge関数は実際にそれ自体を呼び出してマージを行うため、再帰の制限に達しています。

merge長さ 1000 のリストで関数を呼び出すことを検討してください。

これらのリストをマージするには、マージするために 2000 回の呼び出しが必要です (aux呼び出しごとに ~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

最大再帰深度に達しました。

これは、msortPython がデフォルトでこれを許可するよりも頻繁に関数が自分自身を呼び出すことを意味します。

このデフォルト値は、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 に答える