2

次のコードを実行すると:

public static void main(String[] argsv) {

    long whichFib = 45;
    long st;
    st = System.currentTimeMillis();
    System.out.println(recursiveFib(whichFib));
    System.out.println("Recursive version took " + (System.currentTimeMillis() - st) + " milliseconds.");

    st = System.currentTimeMillis();
    System.out.println(iterativeFib(whichFib));
    System.out.println("Iterative version took " + (System.currentTimeMillis() - st) + " milliseconds.");

}

public static long recursiveFib(long n) {

    if (n == 0)
        return 0;
    if (n == 1 || n == 2)
        return 1;

    return recFib(n - 1) + recFib(n - 2);
}

public static long iterativeFib(long n) {

    if (n == 0)
        return 0;
    else if (n == 1 || n == 2)
        return 1;

    long sum = 1;
    long p = 1;
    long u = 1;

    for (int i = 2; i < n; i++) {
        sum = p + u;
        p = u;
        u = sum;
    }

    return sum;
}

次の出力が得られます。

1134903170 再帰バージョンは 5803 ミリ秒かかりました。1134903170 反復バージョンは 0 ミリ秒かかりました。

ここで何か間違ったことをしたような気がします。末尾呼び出し (再帰的なフィボナッチ法の最後の行) がコンパイラによって最適化され、反復バージョンに速度が近づくと考えました。なぜこれが非常に遅く実行されているのか、誰にも考えがありますか? それは単に不十分に書かれた機能ですか？

NB私はOracle JDK 1.7を使用しています

4

4 に答える 4

6 
return recFib(n - 1) + recFib(n - 2);

1 回ではなく 2 回の再帰呼び出しを行っているため、コンパイラが従来の末尾呼び出しの最適化を実行できる可能性は低いです。

末尾呼び出し最適化を使用して再帰的なフィボナッチ ソルバーを作成する方法については、このページを参照してください。

于 2013-01-12T15:11:13.160 に答える
5

他の回答が指摘したように、関数は末尾再帰ではありません。フィボナッチの末尾再帰バージョンは次のとおりです。

long fibonacci(int n) {
    if (n == 0)
        return 0;
    else
        return fibonacciTail(n, 1, 0, 1);
}

long fibonacciTail(int n, int m, long fibPrev, long fibCurrent) {
    if (n == m)
        return fibCurrent;
    else
        return fibonacciTail(n, m + 1, fibCurrent, fibPrev + fibCurrent);
}

また、JVM は末尾呼び出しの最適化を行わないため、再帰呼び出しごとにスタック フレームが割り当てられ、非常にコストのかかる操作になります。ただし、これは技術的に実装に依存することに注意することが重要です。TCO を実行する IBM SDK へのリンクについてはコメントを参照してください。詳細については、このSO の質問を参照してください。

最適化されたバージョンは、手動で末尾呼び出しの最適化を行い、上記を変数の再割り当てを伴う while ループに変換することです。

long fibonacciIter(int n) {
    int m = 1;
    long fibPrev = 0;
    long fibCurrent = 1;
    while (n != m) {
        m = m + 1;
        int current = fibCurrent;
        fibCurrent = fibPrev + fibCurrent;
        fibPrev = current;
    }
    return fibCurrent;
}
于 2013-01-12T15:17:46.000 に答える
1

再帰コードでは、呼び出しの数は答えに比例します。つまり、O(exp(n)) です。

反復法では、実行時間はループ回数に比例します。の上）

さらに悪いことに、ループは再帰呼び出しよりもはるかに高速な操作であるため、同じ反復が行われる場合でも、はるかに高速になります。

このように反復 fib を書くことができます。

public static long iterativeFib(int n) { // no chance of taking a long
    long a = 0, b = 1;    
    while(n-- > 0) {
        long c = a + b;
        a = b;
        b = c;
    }
    return c;
}

なぜこれが非常に遅く実行されているのか、誰にも考えがありますか? それは単に不十分に書かれた機能ですか？

Java は関数型言語ではなく、末尾呼び出しの最適化を行いません。これは、通常、反復が Java の再帰よりもはるかに高速であることを意味します。(例外あり)

于 2013-01-12T16:08:38.063 に答える
1

再帰バージョンでは、繰り返しが同じスタックで動作している間に、関数呼び出しが変数をスタック、スタック管理などにプッシュすることを含むため、関数を再帰的に作成しています。これは高価です。

于 2013-01-12T15:11:42.053 に答える