966

非常に簡単に言えば、テールコール最適化とは何ですか?

より具体的には、適用できる小さなコード スニペットと、適用できない小さなコード スニペットと、その理由の説明を教えてください。

4

10 に答える 10

859

末尾呼び出しの最適化では、呼び出し元の関数は呼び出し先の関数から取得した値を返すだけなので、関数に新しいスタック フレームを割り当てることを回避できます。最も一般的な用途は末尾再帰です。末尾呼び出しの最適化を利用するために作成された再帰関数は、一定のスタック スペースを使用できます。

Scheme は、すべての実装がこの最適化を提供する必要があることを仕様で保証している数少ないプログラミング言語の 1 つです。そのため、Scheme の階乗関数の 2 つの例を次に示します。

(define (fact x)
  (if (= x 0) 1
      (* x (fact (- x 1)))))

(define (fact x)
  (define (fact-tail x accum)
    (if (= x 0) accum
        (fact-tail (- x 1) (* x accum))))
  (fact-tail x 1))

最初の関数は末尾再帰的ではありません。これは、再帰呼び出しが行われると、関数は、呼び出しが返された後に結果を処理するために必要な乗算を追跡する必要があるためです。そのため、スタックは次のようになります。

(fact 3)
(* 3 (fact 2))
(* 3 (* 2 (fact 1)))
(* 3 (* 2 (* 1 (fact 0))))
(* 3 (* 2 (* 1 1)))
(* 3 (* 2 1))
(* 3 2)
6

対照的に、末尾再帰階乗のスタック トレースは次のようになります。

(fact 3)
(fact-tail 3 1)
(fact-tail 2 3)
(fact-tail 1 6)
(fact-tail 0 6)
6

ご覧のように、fact-tail の呼び出しごとに同じ量のデータを追跡するだけで済みます。これは、取得した値を一番上に返すだけだからです。これは、(fact 1000000) を呼び出したとしても、(fact 3) と同じ量のスペースしか必要ないことを意味します。これは非末尾再帰の場合には当てはまらず、そのような大きな値はスタック オーバーフローを引き起こす可能性があります。

于 2008-11-22T07:07:50.910 に答える
638

簡単な例を見てみましょう: C で実装された階乗関数です。

明らかな再帰的定義から始めます

unsigned fac(unsigned n)
{
    if (n < 2) return 1;
    return n * fac(n - 1);
}

関数が戻る前の最後の操作が別の関数呼び出しである場合、関数は末尾呼び出しで終了します。この呼び出しが同じ関数を呼び出す場合、末尾再帰です。

fac()一見末尾再帰のように見えますが、実際にはそうではありません。

unsigned fac(unsigned n)
{
    if (n < 2) return 1;
    unsigned acc = fac(n - 1);
    return n * acc;
}

つまり、最後の操作は乗算であり、関数呼び出しではありません。

fac()ただし、累積された値を追加の引数として呼び出しチェーンに渡し、最終結果のみを戻り値として再度渡すことにより、末尾再帰に書き換えることができます。

unsigned fac(unsigned n)
{
    return fac_tailrec(1, n);
}

unsigned fac_tailrec(unsigned acc, unsigned n)
{
    if (n < 2) return acc;
    return fac_tailrec(n * acc, n - 1);
}

では、なぜこれが役立つのでしょうか。末尾の呼び出しの後にすぐに戻るため、末尾の位置で関数を呼び出す前に前のスタックフレームを破棄するか、再帰関数の場合はスタックフレームをそのまま再利用できます。

末尾呼び出しの最適化は、再帰コードを次のように変換します。

unsigned fac_tailrec(unsigned acc, unsigned n)
{
TOP:
    if (n < 2) return acc;
    acc = n * acc;
    n = n - 1;
    goto TOP;
}

これをインライン化するfac()と、

unsigned fac(unsigned n)
{
    unsigned acc = 1;

TOP:
    if (n < 2) return acc;
    acc = n * acc;
    n = n - 1;
    goto TOP;
}

これはと同等です

unsigned fac(unsigned n)
{
    unsigned acc = 1;

    for (; n > 1; --n)
        acc *= n;

    return acc;
}

ここでわかるように、十分に高度なオプティマイザーは、末尾再帰を反復に置き換えることができます。これは、関数呼び出しのオーバーヘッドを回避し、一定量のスタック スペースのみを使用するため、はるかに効率的です。

于 2012-03-22T00:04:08.367 に答える
235

TCO (Tail Call Optimization) は、スマート コンパイラが関数を呼び出し、追加のスタック スペースを必要としないプロセスです。これが発生する唯一の状況は、関数fで実行された最後の命令が関数 g の呼び出しである場合です(注意: gはfである可能性があります)。ここで重要なのは、fがスタック スペースを必要としないことです。単純にgを呼び出して、 gが返すものを返します。この場合、g が実行され、f を呼び出したものに必要な値を返すという最適化を行うことができます。

この最適化により、再帰呼び出しが爆発するのではなく、一定のスタック スペースを使用するようになる可能性があります。

例: この階乗関数は TCOptimizable ではありません。

from dis import dis

def fact(n):
    if n == 0:
        return 1
    return n * fact(n-1)


dis(fact)
  2           0 LOAD_FAST                0 (n)
              2 LOAD_CONST               1 (0)
              4 COMPARE_OP               2 (==)
              6 POP_JUMP_IF_FALSE       12

  3           8 LOAD_CONST               2 (1)
             10 RETURN_VALUE

  4     >>   12 LOAD_FAST                0 (n)
             14 LOAD_GLOBAL              0 (fact)
             16 LOAD_FAST                0 (n)
             18 LOAD_CONST               2 (1)
             20 BINARY_SUBTRACT
             22 CALL_FUNCTION            1
             24 BINARY_MULTIPLY
             26 RETURN_VALUE

この関数は、return ステートメントで別の関数を呼び出す以外のことを行います。

以下の関数は TCOptimizable です。

def fact_h(n, acc):
    if n == 0:
        return acc
    return fact_h(n-1, acc*n)

def fact(n):
    return fact_h(n, 1)


dis(fact)
  2           0 LOAD_GLOBAL              0 (fact_h)
              2 LOAD_FAST                0 (n)
              4 LOAD_CONST               1 (1)
              6 CALL_FUNCTION            2
              8 RETURN_VALUE

これは、これらの関数のいずれかで最後に発生することは、別の関数を呼び出すことだからです。

于 2008-11-22T07:12:47.467 に答える
72

おそらく、テール コール、再帰テール コール、テール コールの最適化について私が見つけた最高の高レベルの説明は、ブログの投稿です。

「なんだよ、テールコール」

ダン・スガルスキー著。テールコールの最適化について、彼は次のように書いています。

少しの間、次の単純な関数を考えてみましょう:

sub foo (int a) {
  a += 15;
  return bar(a);
}

では、あなた、またはあなたの言語コンパイラーは何ができるでしょうか? できることは、フォームのコードをreturn somefunc();低レベルの sequence に変換することpop stack frame; goto somefunc();です。この例では、これは、 を呼び出す前にbar、fooそれ自体をクリーンアップしてから、サブルーチンとして呼び出すのではなく、 の開始点に対してbar低レベルのgoto操作を行うことを意味しbarます。Fooはすでにスタックから消去されているため、開始時には呼び出した人が本当に を呼び出しbarたように見え、その値を返すと、呼び出し元に返すのではなく、呼び出した人に直接返します。foobarbarfoofoo

そして末尾再帰では:

末尾再帰は、関数が最後の操作として自分自身を呼び出した結果を返す場合に発生します。末尾再帰は、どこかのランダムな関数の先頭にジャンプするのではなく、自分自身の先頭に goto を実行するだけなので、対処が簡単です。これは非常に単純なことです。

したがって、これは次のとおりです。

sub foo (int a, int b) {
  if (b == 1) {
    return a;
  } else {
    return foo(a*a + a, b - 1);
  }

静かに次のようになります:

sub foo (int a, int b) {
  label:
    if (b == 1) {
      return a;
    } else {
      a = a*a + a;
      b = b - 1;
      goto label;
   }

この説明で私が気に入っているのは、命令型言語 (C、C++、Java) のバックグラウンドを持つ人にとって、いかに簡潔で簡単に把握できるかということです。

于 2012-08-26T01:27:05.630 に答える
16

まず、すべての言語がサポートしているわけではないことに注意してください。

TCO は再帰の特殊なケースに適用されます。その要点は、関数で最後に行うことが自分自身の呼び出しである場合 (たとえば、「末尾」の位置から自分自身を呼び出す場合)、これはコンパイラによって最適化され、標準の再帰ではなく反復のように動作するようになります。

ご覧のとおり、通常、再帰中に、ランタイムはすべての再帰呼び出しを追跡する必要があります。これにより、1 つが戻ったときに前の呼び出しから再開できるようになります。(これがどのように機能するかを視覚的に把握するために、再帰呼び出しの結果を手動で書き出してみてください。) すべての呼び出しを追跡するとスペースが必要になります。しかし、TCO では、「最初に戻って、今回だけパラメータ値をこれらの新しい値に変更してください」と言うことができます。再帰呼び出しの後にそれらの値を参照するものがないため、これが可能です。

于 2008-11-22T07:09:41.467 に答える
9

ここを見て：

http://tratt.net/laurie/tech_articles/articles/tail_call_optimization

おそらくご存じのとおり、再帰関数呼び出しはスタックに大混乱をもたらす可能性があります。スタックスペースがすぐに不足するのは簡単です。テール コールの最適化は、一定のスタック スペースを使用する再帰的なスタイルのアルゴリズムを作成するための方法です。

于 2008-11-22T07:05:02.850 に答える
3

  1. 関数自体に goto ステートメントがないことを確認する必要があります..関数呼び出しが呼び出し先関数の最後のものになるように注意してください。

  2. 大規模な再帰ではこれを最適化に使用できますが、小規模では、関数呼び出しを末尾呼び出しにするための命令オーバーヘッドが実際の目的を減らします。

  3. TCO により、関数が永久に実行される可能性があります。

    void eternity()
{
    eternity();
}
于 2012-08-20T10:12:21.903 に答える