5

約 8 億回呼び出す必要がある再帰関数 (C#) があります。これは明らかに通常、約 900 回目の呼び出しの後にスタック オーバーフローを引き起こします。私はこれを複数のループに追い出しましたが、再帰パターンは非常に簡単で、維持するのがきれいです。

私が読んで見たものから、スタックオーバーフローの問題を解決し、複数のネストされたループを修正する必要があるように、yコンビネーターを使用して再帰関数を実装することを検討しています。

y-combinator を使用した経験のある人はいますか? スタック オーバーフローでスタックすることはありますか?

階乗の簡単な例を見てみましょう。5,000 などより大きいほとんどの数値の階乗は、スタック オーバーフローを引き起こします。そのシナリオで y-combinator を適切に使用した場合、スタック オーバーフローは修正されますか?

実装するのは簡単ではないように見えるので、開発努力/リソースを y-combinator の実装と学習に費やす前に確認したいと思います。

4

4 に答える 4

6

Y コンビネータは便利ですが、末尾再帰関数のスタックの使用を排除する末尾再帰の最適化が本当に必要だと思います。末尾再帰は、すべての再帰呼び出しの結果が呼び出し元からすぐに返され、呼び出し後に追加の計算が行われない場合にのみ可能です。残念ながら、C# は末尾再帰の最適化をサポートしていませんが、末尾再帰メソッドからトランポリン ラップ メソッドへの簡単な変換を可能にするトランポリンでエミュレートできます。

// Tail
int factorial( int n ) { return factorialTail( n, 1, 1 ); }
int factorialTail( int n, int i, int acc ) {
  if ( n < i ) return acc;
  else return factorialTail( n, i + 1, acc * i );
}

// Trampoline
int factorialTramp( int n ) { 
   var bounce = new Tuple<bool,int,int>(true,1,1);
   while( bounce.Item1 ) bounce = factorialOline( n, bounce.Item2, bounce.Item3 );
   return bounce.Item3;
}
Tuple<bool,int,int> factorialOline( int n, int i, int acc ) {
  if ( n < i ) return new Tuple<bool,int,int>(false,i,acc);
  else return new Tuple<bool,int,int>(true,i + 1,acc * i);
}
于 2011-12-02T07:42:10.907 に答える
6

いいえ、Y-コンビネータを使用しても状況は改善されません。何かを 8 億回行う必要がある場合は、(a) 再帰するか、(b) ループする (または (c) 関数に 8 億回の呼び出しを書き込む) ことができます。Y コンビネータはループしないため、再帰する必要があります。

適切な末尾再帰 (Scheme など) を提供するランタイム環境を使用していない限り、ループはあなたが探しているものです。

そうは言っても、選択した言語で Y コンビネーターをゼロから実装することは、優れた演習です。

于 2011-12-02T07:14:14.170 に答える
5

Reactive Extension で使用されているトランポリンを使用できます。ブログhttp://rohiton.net/2011/08/15/trampoline-and-reactive-extensions/で説明しようとしました。

于 2011-12-02T08:36:10.900 に答える
1

1 つの解決策は、ループと明示的なコンテキストデータ構造を使用するように関数を変換することです。コンテキストは、コール スタックとして一般的に考えられているものを表します。末尾再帰への変換に関する別の質問に対する私の回答が役に立つかもしれません。関連する手順は 1 ～ 5 です。6 と 7 はその特定の機能に固有のものですが、あなたのものはより複雑に聞こえます。

ただし、「簡単な」代替手段は、各関数に深度カウンターを追加することです。限界に達すると (実験によって決定されます)、新しいスレッドを生成して、新しいスタックで再帰を続行します。古いスレッドは、新しいスレッドが結果を送信するのを待ってブロックします (または、気をつけたい場合は、結果または例外を再発生させます)。新しいスレッドの深度カウンターは 0 に戻ります。制限に達すると、3 番目のスレッドが作成されます。必要以上に頻繁にスレッド作成コストを支払うことを避けるためにスレッドをキャッシュすると、プログラムを大幅に再構築することなく許容できるパフォーマンスが得られることが期待されます。

于 2011-12-02T11:07:01.340 に答える