19

アルゴリズムの紹介 ではp169、末尾再帰の使用について説明していQuicksortます。

この章の前半の元のクイックソート アルゴリズムは (疑似コードで)

Quicksort(A, p, r)
{
 if (p < r)
 {
  q: <- Partition(A, p, r)
  Quicksort(A, p, q)
  Quicksort(A, q+1, r)
 }
}

末尾再帰を使用した最適化バージョンは次のとおりです。

Quicksort(A, p, r)
{
 while (p < r)
 {
  q: <- Partition(A, p, r)
  Quicksort(A, p, q)
  p: <- q+1
 }
}

Partitionピボットに従って配列をソートする場所。

違いは、2 番目のアルゴリズムQuicksortが LHS を並べ替えるために 1 回だけ呼び出すことです。

1 番目のアルゴリズムではスタック オーバーフローが発生するのに、2 番目のアルゴリズムでは発生しない理由を誰かが説明してくれますか? それとも私は本を誤解していますか？

4

5 に答える 5

11

まず、スタック オーバーフローとは何かについて、おそらく正確ではないが有効な簡単な定義から始めましょう。

おそらくご存知のように、あまりにも異なるデータ構造で実装されている 2 つの異なる種類のメモリがあります: ヒープとスタックです。

サイズに関しては、ヒープはスタックよりも大きく、簡単にするために、関数呼び出しが行われるたびに新しい環境 (ローカル変数、パラメーターなど) がスタック上に作成されるとしましょう。そのため、スタックのサイズが制限されているという事実を考えると、あまりにも多くの関数呼び出しを行うと、スペースが不足するため、スタック オーバーフローが発生します。

再帰の問題は、反復ごとにスタック上に少なくとも 1 つの環境を作成しているため、限られたスタック内の多くのスペースを非常に急速に占有することになるため、スタック オーバーフローは一般的に再帰呼び出しに関連付けられることです。

したがって、再帰呼び出しが行われるたびに同じ環境を再利用するテール再帰呼び出しの最適化と呼ばれるものがあり、スタックで占有されるスペースは一定であり、スタックオーバーフローの問題を防ぎます。

ここで、テール コールの最適化を実行するためのルールがいくつかあります。まず、各呼び出しは最も完全であり、つまり、実行を中断した場合に関数がいつでも結果を返すことができる必要があることを意味します。SICPでは 、関数が再帰的であっても、これは反復プロセスと呼ばれます。

最初の例を分析すると、各反復が 2 つの再帰呼び出しによって定義されていることがわかります。これは、結果がそれらの呼び出しに依存するため、いつでも実行を停止すると、部分的な結果を与えることができないことを意味します。このシナリオでは、すべての再帰呼び出し間で合計情報が分割されるため、スタック環境を再利用することはできません。

ただし、2 番目の例にはその問題はありません。A は定数であり、p と r の状態はローカルで決定できるため、続行するすべての情報がそこにあるため、TCO を適用できます。

于 2013-09-30T15:01:59.473 に答える