0

私はCourseraのオンラインコース「アルゴリズム：設計と分析、パート1」を受講しており、2回目の宿題を完了しました。しかし、私がそれをしている間、私はpythonランタイムエラーによって引き起こされる現象を説明することができません。

ソリューションコードを配布することになっていないので、抜粋をいくつか書きます。

def quick_sort_count (arr, index, median=False):
     # SOME OPERATIONS
     ......
     # Termination
     if len(arr)==0 or len(arr)==1:
         return arr, 0
     ........
     arr[:i-1], t1 = quick_sort_count(arr[:i-1], index, median)
     arr[i:], t2 = quick_sort_count(arr[i:], index, median)
     return arr, len(arr)+t1+t2-1

プログラムは、10,000の一意の番号を持つデータファイルを分析し、クイックソートにある「比較」の数を計算する必要があります。質問には3つの部分が含まれます。比較のピボットとして最初の要素を使用する。最後のものを使用します。そして「中央値」のものを使用します。

奇妙な部分は、どちらかの質問を個別に実行することで正しい答えを得ることができるということです。しかし、次のような関数で3つすべてをまとめて実行することはできません。

def main():
    # READING THE FILE
    ......
    _,result1 = quick_sort_count(arr1, 0)
    _,result2 = quick_sort_count(arr2, -1)
    _,result3 = quick_sort_count(arr3, 0, True)

そうした場合、「RuntimeError：最大再帰深度を超えました」が発生します。何か好きなもの

....
arr[:i-1], t1 = quick_sort_count(arr[:i-1], index, median)
  File "/Users/c/algorithm/quick_sort.py", line 43, in quick_sort_count
arr[:i-1], t1 = quick_sort_count(arr[:i-1], index, median)
  File "/Users/c/algorithm/quick_sort.py", line 43, in quick_sort_count
arr[:i-1], t1 = quick_sort_count(arr[:i-1], index, median)
  File "/Users/c/algorithm/quick_sort.py", line 43, in quick_sort_count
arr[:i-1], t1 = quick_sort_count(arr[:i-1], index, median)
  File "/Users/c/algorithm/quick_sort.py", line 43, in quick_sort_count
arr[:i-1], t1 = quick_sort_count(arr[:i-1], index, median)
  File "/Users/c/algorithm/quick_sort.py", line 33, in quick_sort_count
arr = swap(arr, index, 0)
RuntimeError: maximum recursion depth exceeded

「スワップ」は、arr[index]とarr[0]の位置を変更する単純な操作です。これは、2番目の質問の要件です。「最後の要素をピボット要素として使用し、前に最初の要素にスワップします。並べ替え」。

そして、再帰制限をさらに増やすと

import sys
sys.setrecursionlimit(100000)

そうすると、2番目と3番目の質問の答えが間違ってしまいます。

なぜこれが起こるのか誰かに教えてもらえますか？どうもありがとう！

4

1 に答える 1

3

完全なコードを投稿していないので、Pythonの再帰制限を克服する方法に関する一般的なアドバイスを次に示します。

一般的な再帰関数の構造は次のとおりです。

def foo:
    if termination-condition
        return value
    else
        new-value = some-calculations
        return foo(new-value)

最初のステップは、関数を末尾再帰にすることです。つまり、elseブランチの計算を削除して、フォームに変換します。

def foo:
    if termination-condition
        return value
    else
        return foo(some-calculations)

末尾再帰の最適化をサポートする言語では十分ですが、Pythonではさらに一歩進む必要があります。すぐに再帰的に呼び出す代わりにreturn foo(...)、「サンク」を返しましょう。これは基本的に、意図することの説明または約束です。Pythonでは、サンクは無名lambda関数として記述できます。

def foo:
    if termination-condition
        return value
    else
        return lambda: foo(some-calculations)

もちろん、から返された値を消費する別の中間関数が必要になります。fooサンクが指定された場合は、ターミナル（非関数）値が返されるまでそれを実行します。

def foo-interface:
    # get a thunk or a terminal
    t = foo()  
    # while it's a thunk...
    while callable(t):
        t = t() # ...carry it out
    # return the terminal
    return t

例

大きな引数で失敗する階乗の次の素朴な実装をしましょう：

def fac(n):
    return 1 if n < 2 else n * fac(n - 1)

> fac(3000)
> RuntimeError: maximum recursion depth exceeded

末尾再帰に変換します...

def f(n, acc=1):
    return acc if n < 2 else f(n - 1, acc * n)

...サンク変換を適用します...

def f(n, acc):
    return acc if n < 2 else lambda: f(n - 1, acc * n)

...そしてそれをインターフェース関数（コンシューマー）でラップします...

def fac(n):

    def f(n, acc):
        return acc if n < 2 else lambda: f(n - 1, acc * n)

    t = f(n, 1)
    while callable(t):
        t = t()
    return t

できます！ 

> fac(3000)
> 41493596034....

このテクニックは「トランポリン」と呼ばれています。これがあなたの特定のケース（したがってCW）で役立つかどうかはわかりませんが、これは知っておくとよいことだと思います（そして、たまたま教授に感銘を与えるために））。

デコレータ

この種の末尾再帰は、デコレータとして記述できます。代わりにクラスを使用した良い説明lambdaがここにあります。

于 2013-02-12T09:47:10.753 に答える