2

n=1000 より前にスタック オーバーフローが発生します。JVM がすべてのスタック フレームを保持する必要があると感じているのは long[] パラメータへの参照のためですか (ワイルド 推測)、それとも何か間違ったことをしているのですか?

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        fibonacciMemoized(1000);
        long end = System.currentTimeMillis();
        System.out.println("\nTotal run time: " + (end-start));
    }

    public static void fibonacciMemoized(int n) {
        long[] fibMemos = new long[n+1];
        for (int i = 0;  i < fibMemos.length; i++) {
            fibMemos[i] = Long.MAX_VALUE;
        }
        long fibResult = fib(n, 1, 0, fibMemos);
        System.out.println(fibResult);
    }

    public static long fib(int n, long fibAcc, long fibPrev, long[] fibMemos) {
        if (fibMemos[n] != Long.MAX_VALUE){
            return fibMemos[n];
        } else if (n == 0) {
            return fibPrev;
        } else if (n == 1){
            return fibAcc;
        } else {
            long result = fib(n-1, fibAcc+fibPrev, fibAcc, fibMemos);
            fibMemos[n] = result;
            return result;
        }
    }
4

3 に答える 3

4

これはコメントというよりも答えだと思います：

末尾再帰フィボナッチ アルゴリズムを使用してスタックを使い果たすのはなぜですか?

Java はテール コールの削除をサポートしていないためです。

于 2013-03-21T03:21:31.410 に答える
1

メモ化の主な問題は、メモ化された関数の後続の呼び出しが、同じパラメーターに対して事前に計算された値を使用することです。

コードでは、以前に関数を呼び出していないため、再利用する前の結果がなく、値 1000 で呼び出しを開始すると、fib()with の最後で再帰呼び出しが行わfib(n-1, fibAcc+fibPrev, fibAcc, fibMemos)れるため、 1000 回の再帰呼び出しでスタックします。

于 2013-03-21T03:31:27.327 に答える
0

java -Xss4m などのスタックを増やすオプションを使用して実行してみてください。

注: -X​​ss を使用すると、すべてのスレッドのスタック サイズが設定され、非常に悪い考えです。

于 2013-03-21T03:27:13.720 に答える