あなたのお気に入りの言語は深い再帰をどのように処理しますか?[閉まっている]
https://stackoverflow.com/questions/233013
-
04-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
最近 Python を学習し始めたのですが、(デフォルトで) 1000 回の再帰の深さの制限を見つけてかなり驚きました。十分に高い値 (約 30000) に設定すると、C と同様にセグメンテーション違反でクラッシュします。ただし、Cはかなり上に行くようです。
(Python 関係者は、再帰関数はいつでも反復関数に変換でき、その方が常に高速であるとすぐに指摘します。それは100%真実です。それは私の質問の本当の意味ではありませんが。）
同じ実験を Perl で試してみましたが、約 1,000 万回の再帰で 4 ギガの RAM がすべて消費されてしまい、^C を使用して試行を中止しました。Perl が C スタックを使用していないことは明らかですが、再帰時にとんでもない量のメモリを使用します。関数を呼び出すためにどれだけの作業が必要かを考えると、それほど衝撃的なことではありません。
Pike で試してみたところ、約 2 秒で 100,000,000 回の再帰が得られ、まったく驚きました。どのようにしてそうなったのかは分かりませんが、再帰を反復プロセスに平坦化したのではないかと思われます。再帰処理中に余分なメモリを消費することはないようです。[注記：Pike は些細なケースを平坦化しますが、より複雑なケースではセグメンテーション違反を起こす、またはそのように言われています。]
私はこれらの役に立たない関数を使用しました。
int f(int i, int l) { if(i<l) return f(i+1,l); return i; }
sub f { return f($_[0]+1, $_[1]) if $_[0]<$_[1]; return $_[0] };
def f(i,l):
if i<l:
return f(i+1,l)
return i
他の言語 (PHP、Ruby、Java、Lua、Ocaml、Haskell) が再帰をどのように処理するのか、そしてなぜそのように処理するのか、非常に興味があります。さらに、関数が「末尾再帰」である場合に違いが生じるかどうかにも注意してください (コメントを参照)。
解決
「Python 関係者は、再帰関数はいつでも反復関数に変換でき、その方が常に高速であるとすぐに指摘します。」
これは事実ですが、本当にこれだけ簡単な場合、コードをできるだけ単純に見せるために、なぜ Python がそれを実行しないのでしょうか?(Python 実装者を非難するためにこれを言っているのではなく、答えが問題を説明しているからです)。
再帰最適化は、14 世紀か何かの頃から関数型言語に存在していました。Haskell、CAML、Lisp の実装はすべて、通常、少なくとも末尾再帰関数を反復に変換します。基本的に、それが可能であることを発見することによってこれを行います。再帰呼び出し後に戻り値以外のローカル変数が使用されないように関数を再配置できること。戻る前に再帰戻り値に対して何らかの作業が行われた場合にそれを可能にする 1 つのトリックは、追加の「アキュムレータ」パラメータを導入することです。簡単に言えば、これは作業が「上り」ではなく「下り」で効果的に実行できることを意味します。詳細については、「関数を末尾再帰的に作成する方法」を検索してください。
末尾再帰関数をループに変える実際の詳細は、基本的に呼び出し規約を変更することです。つまり、パラメータを設定して関数の先頭に戻るだけで「呼び出しを実行」でき、すべてを保存する必要はありません。決して使用しないことがわかっている範囲のもの。アセンブラの観点から言えば、データ フロー分析により、呼び出し後に使用されていないことが判明した場合、呼び出し元保存レジスタを保存する必要はありません。同様のことがスタック上のすべてのレジスタにも当てはまります。次の再帰/反復によってスタックの「自分の」ビットが書き換えられても構わない場合は、呼び出し時にスタック ポインタを移動する必要はありません。
Python 関係者がどのように言い換えたかに反して、一般的な再帰関数を反復に変換するのは簡単ではありません。たとえば、乗算再帰の場合、単純なアプローチではやはりスタックが必要になります。
ただし、メモ化は任意の再帰関数にとっては便利な手法なので、考えられるアプローチに興味がある場合は調べてみるとよいでしょう。これは、関数が評価されるたびに、結果をキャッシュに保存することを意味します。これを使用して再帰を最適化するには、基本的に、再帰関数が「ダウン」カウントし、それをメモ化した場合、関数の各値を順番に計算して「アップ」カウントするループを追加することで反復的に評価できます。目標。メモ キャッシュが必要なすべての値を保持するのに十分な大きさであれば、これにより使用されるスタック領域は非常に少なくなります。たとえば、f(n) が f(n-1)、f(n-2)、および f(n-3) に依存する場合、キャッシュには 3 つの値のためのスペースのみが必要です。上に上がると、はしごを蹴り飛ばすことができます。f(n) が f(n-1) と f(n/2) に依存する場合、キャッシュ内に多くのスペースが必要になりますが、それでも、最適化されていない再帰でスタックに使用するスペースよりも少なくなります。
他のヒント
これは、言語の問題というよりも実装の問題です。一部の（愚かな）Cコンパイラの実装者が呼び出しスタックを1000に制限することを止めるものは何もありません。
（Pythonの人々は、再帰関数をいつでも反復関数にいつでも変換でき、常に高速であるとすぐに指摘します。それは100％真実です。それは本当に私の質問とは異なります。）
おそらく彼らはそれを言っていますが、これはまったく正しくありません。再帰は常に反復に変換できますが、場合によっては stack を手動で使用する必要もあります。そのような状況では、再帰バージョンの方が高速であることがわかります（不要な宣言を再帰ルーチンの外に引き出すなど、単純な最適化を行うのに十分賢いと仮定します）。結局のところ、スタックプッシュプッシュ周囲のプロシージャコールは、コンパイラが非常によく最適化する方法を知っている必要があります十分に境界の問題です。一方、手動スタック操作では、コンパイラに特殊な最適化コードが含まれることはなく、余分なサイクルを必要とするあらゆる種類のユーザーインターフェイスの健全性チェックが行われやすくなります。
Pythonでは、反復/スタックソリューションが常に高速である場合があります 。もしそうなら、それはPythonの失敗であり、再帰の失敗ではありません。
PHPは、死ぬまでにデフォルトで100の制限があります：
Fatal error: Maximum function nesting level of '100' reached, aborting!
編集：ini_set('xdebug.max_nesting_level', 100000);で制限を変更できますが、約1150回の繰り返しを超えるとPHPがクラッシュします：
[Fri Oct 24 11:39:41 2008] [notice] Parent: child process exited with status 3221225477 -- Restarting.
C＃/。NETは、特定の状況で末尾再帰を使用します。 （C＃コンパイラはテールコールオペコードを出力しませんが、 JITは場合によっては末尾再帰を実装します。
Shri Borde このトピックに関する投稿もあります。もちろん、CLRは絶えず変化しています。.NET3.5および3.5SP1では、テールコールに関して再び変化した可能性があります。
F＃インタラクティブコンソールで次を使用すると、1秒未満で実行されました。
let rec f i l =
match i with
| i when i < l -> f (i+1) l
| _ -> l
f 0 100000000;;
次に、直訳を試みました。つまり、
let rec g i l = if i < l then g (i+1) l else l
g 0 100000000;;
結果は同じですが、コンパイルが異なります。
これは、C＃に翻訳されたときの f の外観です：
int f(int i, int l)
{
while(true)
{
int num = i;
if(num >= l)
return l;
int i = num;
l = l;
i = i + 1;
}
}
g ですが、これは次のように変換されます：
int g(int i, int l)
{
while(i < l)
{
l = l;
i++;
}
return l;
}
基本的に同じ2つの関数が、F＃コンパイラによって異なる方法でレンダリングされるのは興味深いことです。また、F＃コンパイラに末尾再帰最適化があることも示しています。したがって、これはiが32ビット整数の制限に達するまでループします。
このスレッドによると、約5,000,000 java、1Gb RAM。 （そして、「クライアント」バージョンのホットスポットを使用）
300Moのスタック（-Xss）でした。
-serverオプションを使用すると、増やすことができます。
また、コンパイラを最適化して（たとえば、 JETを使用）、各レイヤーでスタックのオーバーヘッド。
一部の非病理学的ケース（あなたのような）では、（最新の）Lua は以下を使用します。 末尾呼び出し再帰, 、つまり。データをスタックにプッシュせずにジャンプするだけです。したがって、再帰ループの数はほぼ無制限になります。
以下でテストしました:
function f(i, l)
if i < l then
return f(i+1, l)
end
return i
end
local val1 = arg[1] or 1
local val2 = arg[2] or 100000000
print(f(val1 + 0, val2 + 0))
また:
function g(i, l)
if i >= l then
return i
end
return g(i+1, l)
end
相互再帰 (f が g を呼び出し、g が f を呼び出す...) も試してみました。
Windows では、Lua 5.1 はこれを実行するために約 1.1MB (一定) を使用し、数秒で終了します。
古い白いMacbookでruby 1.9.2dev（2010-07-11リビジョン28618）[x86_64-darwin10.0.0]を実行する：
def f
@i += 1
f
end
@i = 0
begin
f
rescue SystemStackError
puts @i
end
出力は9353です。つまり、Rubyはスタックで10,000回未満の呼び出しで処理します。
次のような相互再帰あり：
def f
@i += 1
g
end
def g
f
end
半分の時間で4677（〜= 9353/2）になります。
procで再帰呼び出しをラップすることにより、さらに数回の反復を絞り出すことができます。
def f
@i += 1
yield
end
@i = 0
@block = lambda { f(&@block) }
begin
f(&@block)
rescue SystemStackError
puts @i
end
エラーが発生するまで最大4850になります。
Visual Dataflexはオーバーフローをスタックします。
私は関数型プログラミングのかなりのファンです。これらの言語のほとんどは末尾呼び出しの最適化を実装しているため、好きなだけ再帰できます :-P
ただし、実際には Java を多用し、Python も多用する必要があります。Java にどのような制限があるのかはわかりませんが、Python については、装飾された関数を最適化する末尾呼び出しを行うデコレーターを実装することを実際に計画していました (ただし、まだ実行していません)。私はこれを再帰を最適化するためではなく、主に Python バイトコードに動的にパッチを適用し、Python の内部についてさらに学ぶための演習として計画しました。ここにいくつかのインターネットリンクがあります: http://lambda-the-ultimate.org/node/1331 そして http://www.rowehl.com/blog/?p=626
Perlコードを改良して、一定サイズのスタックを使用するようにする方法があります。これを行うには、特別な形式のgotoを使用します。
sub f{
if( $_[0] < $_[1] ){
# return f( $_[0]+1, $_[1] );
@_ = ( $_[0]+1, $_[1] );
goto &f;
} else {
return $_[0]
}
}
最初に呼び出されたとき、スタック上のスペースを割り当てます。次に、引数を変更し、スタックに何も追加せずにサブルーチンを再起動します。したがって、自己を呼び出したことがないふりをし、反復プロセスに変更します。
Sub :: Call :: Recur モジュール。これにより、コードが理解しやすくなり、短くなります。
use Sub::Call::Recur;
sub f{
recur( $_[0]+1, $_[1] ) if $_[0] < $_[1];
return $_[0];
}
clojure は、末尾再帰の特別な形式を提供します<！> quot; recur <！> quot;これは、astの尾部でのみ使用できます。それ以外の場合、javaのように動作し、StackverflowExceptionをスローする可能性があります。
