10

Tail 呼び出しの再帰について勉強していて、言及されているドキュメントに出くわしました。Sun Java は末尾呼び出しの最適化を実装していません。3 つの異なる方法でフィボナッチ数を計算する次のコードを書きました。

public class Fibonacci {
    public static void main(String[] args) throws InterruptedException {
        int n = Integer.parseInt(args[0]);
        System.out.println("\n Value of n : " + n);
        System.out.println("\n Using Iteration : ");
        long l1 = System.nanoTime();
        fibonacciIterative(n);
        long l2 = System.nanoTime();
        System.out.println("iterative time = " + (l2 - l1));
        System.out.println(fibonacciIterative(n));

        System.out.println("\n Using Tail recursion : ");
        long l3 = System.nanoTime();
        fibonacciTail(n);
        long l4 = System.nanoTime();
        System.out.println("Tail recursive time = " + (l4 - l3));
        System.out.println(fibonacciTail(n));

        System.out.println("\n Using Recursion : ");
        long l5 = System.nanoTime();
        fibonacciRecursive(n);
        long l6 = System.nanoTime();
        System.out.println("Head recursive time = " + (l6 - l5));
    }

    private static long fibonacciRecursive(int num) {
        if (num == 0) {
            return 0L;
        }
        if (num == 1) {
            return 1L;
        }
        return fibonacciRecursive(num - 1) + fibonacciRecursive(num - 2);
    }

    private static long fibonacciIterative(int n) throws InterruptedException {
        long[] arr = new long[n + 1];
        arr[0] = 0;
        arr[1] = 1;
        for (int i = 2; i <= n; i++) {
            // Thread.sleep(1);
            arr[i] = arr[i - 1] + arr[i - 2];
        }
        return arr[n];
    }

    private static long fibonacciTail(int n) {
        if (n == 0)
            return 0;
        return fibHelper(n, 1, 0, 1);
    }

    private static long fibHelper(int n, int m, long fibM_minus_one, long fibM) {
        if (n == m)
            return fibM;
        return fibHelper(n, m + 1, fibM, fibM_minus_one + fibM);
    }
}

このプログラムを実行すると、いくつかの結果が得られました。

  1. n>50 の場合、Head Recursive メソッドが終了しません。プログラムがぶら下がっているように見えました。なぜこれが起こるのでしょうか？
  2. テール再帰法は、ヘッド再帰法と比較して大幅に時間がかかりませんでした。反復法よりもさらに時間がかからないこともありました。Java が Tail 呼び出しの最適化を内部的に行っているということですか? もしそうなら、なぜ私は n > 5000 で StackOverflowError を与えたのですか?

システム仕様:

インテル Core 5 プロセッサー、

ウィンドウズXP、

32 ビット Java 1.6

JVM のデフォルトのスタック サイズ。

4

4 に答える 4

12

Does it mean that java does some Tail call optimization internally?

No, it does not. The HotSpot JIT compilers do not implement tail-call optimization.

The results you are observing are typical of the anomalies that you see in a Java benchmark that doesn't take account of JVM warmup. For instance, the "first few" times a method is called, it will be executed by the interpreter. Then the JIT compiler will compile the method ... and it will get faster.

To get meaningful results, put a loop around the whole lot and run it a number of times until the timings stabilize. Then discard the results from the early iterations.

... why I did it give StackOverflowError at n > 5000?

That's just evidence that there isn't any tail-call optimization happening.

于 2011-03-28T00:31:21.487 に答える
3

最初の質問では、2^50 (またはそれに近いもの) とは何ですか? 再帰的な Fib 関数の各数値 N は、それを 2 回呼び出します (前の 2)。これらのそれぞれは、2回前の反復などを呼び出します。したがって、再帰の2^(Nk)に成長します(kはおそらく2または3です)。

2 番目の質問は、2 番目の質問が単純な N 再帰であるためです。双頭(N-1),(N-2)になるのではなく、単に M=1、M=2... M=N から構築されます。途中の各ステップで、N-1 値が追加のために保持されます。これは O(N) 操作であるため、反復法に匹敵します。唯一の違いは、JIT コンパイラーがそれを最適化する方法です。ただし、再帰の問題は、フレームにスタックするレベルごとに膨大なメモリ フットプリントが必要になることです。ある制限でメモリまたはスタック スペースが不足します。 それでも、一般的には反復法よりも遅くなるはずです。

于 2011-03-28T00:14:40.610 に答える
2

メモ化を使用して、先頭の再帰を回避できます。

次のコードをテストしました。N <=40 の場合、Map にはトレードオフがあるため、このアプローチは不適切です。

private static final Map<Integer,Long> map = new HashMap<Integer,Long>();

private static long fibonacciRecursiveMemoization(int num) {
    if (num == 0) {
        return 0L;
    }
    if (num == 1) {
        return 1L;
    }

    int num1 = num - 1;
    int num2 = num - 2;

    long numResult1 = 0;
    long numResult2 = 0;

    if(map.containsKey(num1)){
        numResult1 = map.get(num1);
    }else{
        numResult1 = fibonacciRecursiveMemoization(num1);
        map.put(num1, numResult1);
    }

    if(map.containsKey(num2)){
        numResult2 = map.get(num2);
    }else{
        numResult2 = fibonacciRecursiveMemoization(num2);
        map.put(num2, numResult2);
    }

    return numResult1 + numResult2;
}

n の値が 44 の場合

反復の使用: 反復時間 = 6984

末尾再帰の使用: 末尾再帰時間 = 8940

メモ化再帰の使用 : メモ化再帰時間 = 1799949

再帰の使用: ヘッド再帰時間 = 12697568825

于 2011-12-04T00:47:07.217 に答える
2

ポイント1に関して：メモ化せずにフィボナッチ数を再帰的に計算すると、実行時間が指数関数的になりnます。これは、関数の結果を自動的にメモ化しないプログラミング言語 (Java、C#、C++ などのほとんどの主流の非関数型言語など) に当てはまります。その理由は、同じ関数が何度も何度も呼び出されるためです。たとえば、 andf(8)が呼び出さf(7)れf(6)ます。はandf(7)を呼び出すので、は 2 回呼び出されます。この影響は伝播し、関数呼び出しの数が指数関数的に増加します。以下は、どの関数が呼び出されるかを視覚化したものです。f(6)f(5)f(6)

f(8)
 f(7)
  f(6)
   f(5)
    f(4)
     ...
    f(3)
     ...
   f(4)
    ...
  f(5)
   f(4)
    ...
   f(3)
    ...
 f(6)
  f(5)
   ...
  f(4)
   ...
于 2011-03-28T00:15:28.140 に答える