23

私は最近 Python の学習を始めましたが、(デフォルトで) 1000 の深い再帰制限を見つけてかなり驚きました。30000 くらいに設定すると、C と同じようにセグメンテーション違反でクラッシュします。ただし、C はかなり高くなるようです。

(Python 関係者は、いつでも再帰関数を反復関数に変換でき、常に高速であるとすぐに指摘します。それは 100% 真実です。しかし、それは実際には私の質問の内容ではありません。)

Perl で同じ実験を試みたところ、約 1000 万回の再帰で 4 ギガの RAM がすべて消費され、^C を使用して試行を停止しました。明らかに、Perl は C スタックを使用しませんが、再帰の際に途方もない量のメモリを使用します。関数を呼び出すためにどれだけの作業をしなければならないかを考えると、それほど衝撃的ではありません。

Pike で試してみたところ、約 2 秒で 100,000,000 回の再帰が得られたことに完全に驚きました。それがどのように行われたかはわかりませんが、反復プロセスへの再帰を平坦化したのではないかと思います-実行中に余分なメモリを消費していないようです. [注: Pike は些細なケースを平坦化しますが、より複雑なケースでは segfault を実行します。そう言われています。]

私はこれらの無用な機能を使用しました：

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 など) が再帰をどのように処理するのか、またなぜそのように処理するのか、非常に興味があります。さらに、関数が「末尾再帰」である場合に違いが生じるかどうかに注意してください (コメントを参照)。

4

11 に答える 11

23

「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）に依存する場合、

于 2008-10-24T11:30:53.213 に答える
7

これは、言語の問題というよりも実装の問題です。一部の (ばかげた) C コンパイラの実装者がコール スタックを 1000 に制限することを止めるものは何もありません。多くのスタック スペースを持たない小さなプロセッサがたくさんあります。

(Python 関係者は、いつでも再帰関数を反復関数に変換でき、常に高速であるとすぐに指摘します。それは 100% 真実です。しかし、それは実際には私の質問の対象ではありません。)

おそらく彼らはそう言っているのでしょうが、これは完全に正しくありません。再帰は常に反復に変換できますが、スタックを手動で使用する必要がある場合もあります。そのような状況では、再帰バージョンの方が高速であることがわかりました (再帰ルーチンの外で不要な宣言をプルするなど、単純な最適化を行うのに十分賢いと仮定します)。結局のところ、プロシージャ呼び出しを取り巻くスタック プッシュは、コンパイラが適切に最適化する方法を知っている必要がある、限定された問題です。一方、手動のスタック操作では、コンパイラに特殊な最適化コードが含まれず、あらゆる種類のユーザー インターフェイスのサニティ チェックが余分なサイクルを必要とする傾向があります。

Python では、反復/スタック ソリューションが常に高速である場合があります。もしそうなら、それは再帰ではなく Python の失敗です。

于 2008-10-24T13:41:46.090 に答える
4

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.

于 2008-10-24T10:36:28.643 に答える
3

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ビット整数の制限に達するまでループする必要があります。

于 2008-10-24T12:45:19.073 に答える
3

C#/.NET は、特定の状況で末尾再帰を使用します。(C# コンパイラは末尾呼び出しオペコードを発行しませんが、JIT は末尾再帰を実装する場合があります。

Shri Bordeもこのトピックに関する投稿をしています。もちろん、CLR は継続的に変更されており、.NET 3.5 および 3.5SP1 では、テール コールに関して再び変更されている可能性があります。

于 2008-10-24T10:38:08.000 に答える
2

一部の病理学的でないケース (あなたのような) では、(最新の) 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

相互再帰も試しました（gを呼び出すfとfを呼び出すg ...）。

Windows では、Lua 5.1 はこれを実行するために約 1.1MB (定数) を使用し、数秒で終了します。

于 2008-10-24T11:45:11.957 に答える
2

このスレッドによると、Java、1Gb RAMで約 5,000,000です。（そして、ホットスポットの「クライアント」バージョンで）

それは 300Mo のスタック (-Xss)でした。

-server オプションを使用すると、これを増やすことができます。

また、各層のスタック オーバーヘッドを削減するために、コンパイラを (たとえばJETを使用して) 最適化することもできます。

于 2008-10-24T10:36:31.110 に答える
1

Visual Dataflex はスタック オーバーフローを起こします。

于 2008-10-24T10:46:52.367 に答える
1

clojureは末尾再帰のための特別な形式 "recur" を提供します。これは ast の末尾の場所でのみ使用できます。それ以外の場合は、Java のように動作し、StackverflowException をスローする可能性があります。

于 2010-11-19T21:34:16.217 に答える
1

コードを改善して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];
}
于 2008-10-24T16:05:58.623 に答える
1

私は関数型プログラミングのファンです。これらの言語のほとんどは末尾呼び出しの最適化を実装しているため、好きなだけ再帰を行うことができます :-P

しかし、実際には、Java を多用し、Python も多用する必要があります。Javaの制限はわかりませんが、Pythonの場合、装飾された関数をテールコール最適化するデコレーターを実装することを実際に計画していました（ただし、まだ実行していません）。これは、再帰を最適化するためではなく、主に Python バイトコードに動的にパッチを適用し、Python の内部構造についてさらに学習するための演習として計画していました。いくつかの興味深いリンクがあります: http://lambda-the-ultimate.org/node/1331およびhttp://www.rowehl.com/blog/?p=626

于 2008-10-24T16:16:24.233 に答える