5

私はこのコードを作成しました..そして私はそれを最大限に活用する必要があります..フィボナッチ数を計算する最高のパフォーマンスが本当に必要です..助けてください..

このタイプの計算のコードをいくつか読んだことがありますが、それらを最大限に活用したと思います..

私のためにこれを評価してください..plz..

ps: そして、私は本当に BigInteger が必要です..膨大な数のフィボナッチを計算します

ps2: このアルゴリズムでいくつかの大きな数値を計算したところ、優れた応答時間が得られました..しかし、それがより良いかどうかを知る必要があります

ps3: このコードを実行するには、この VM 引数-Xss16384k(StackSize)を使用する必要があります

public class Fibonacci {

    private static BigInteger[] fibTmp = { BigInteger.valueOf(0), BigInteger.valueOf(1) };

    public static BigInteger fibonacci(long v) {

        BigInteger fib = BigInteger.valueOf(0);

        if (v == 1) {

            fib = BigInteger.valueOf(1);

        } else if (v == 0) {

            fib = BigInteger.valueOf(0);

        } else {

            BigInteger v1 = fibonacci(v - 1);
            BigInteger v2 = fibTmp[(int) (v - 2)];

            fib = v1.add(v2);
        }

        synchronized (fibTmp) {

            if (fibTmp.length - 1 < v)
                fibTmp = Arrays.copyOf(fibTmp, (int) (v + 10));

            fibTmp[(int) v] = fib;
        }

        return fib;
    }
}
4

3 に答える 3

7

はい、もっと良い方法があります。これは、log(n)入力として正の整数が与えられた場合に、任意の精度でフィボナッチの値を計算するためのテスト済みの非常に効率的な方法です。このアルゴリズムは、 SICPの演習 1.19のソリューションから適用されました。

public static BigInteger fibonacci(int n) {

    int count = n;
    BigInteger tmpA, tmpP;
    BigInteger a = BigInteger.ONE;
    BigInteger b = BigInteger.ZERO;
    BigInteger p = BigInteger.ZERO;
    BigInteger q = BigInteger.ONE;
    BigInteger two = new BigInteger("2");

    while (count != 0) {

        if ((count & 1) == 0) {
            tmpP = p.multiply(p).add(q.multiply(q));
            q = two.multiply(p.multiply(q)).add(q.multiply(q));
            p = tmpP;
            count >>= 1;
        }

        else {
            tmpA = b.multiply(q).add(a.multiply(q).add(a.multiply(p)));
            b = b.multiply(p).add(a.multiply(q));
            a = tmpA;
            count--;
        }

    }

    return b;  

}

本のリンクされた章には、それがどのように機能するかの説明があり (演習 1.19 までスクロールします)、次のように述べられています。

これは、フィボナッチ数を対数のステップ数で計算するための巧妙なアルゴリズムです... この演習は、Kaldewaij, Anne の例に基づいて、Joe Stoy によって提案されました。1990.プログラミング: アルゴリズムの導出。

もちろん、同じ値を何度も計算する必要がある場合は、たとえば以前の値を保存するためのマップを使用するなど、既に計算された結果を記憶することで、さらにパフォーマンスを向上させることができます。

于 2013-02-26T16:15:38.680 に答える
4

スタックがオーバーフローするため、適切な数に対して実装が機能しません。

ここで再帰性を使用する理由はわかりません。再帰性はきれいですが、一般的に重いです (言語に依存します)。単純なforループを使用した実用的な実装を次に示します。

private static BigInteger[] fibTmp = {BigInteger.ZERO, BigInteger.ONE};
private static int maxCached = 1;
public static BigInteger fibonacci(int v) {
    if (fibTmp.length<=v) {
        fibTmp = Arrays.copyOf(fibTmp, v*5/4);
    }
    for (; maxCached<v;) {
        maxCached++;
        BigInteger v1 = fibTmp[maxCached - 1];
        BigInteger v2 = fibTmp[maxCached - 2];
        fibTmp[maxCached] = v1.add(v2);
    }
    return fibTmp[v];
}

これは、文献で効率的なフィボナッチ アルゴリズムを探すことなく直接実装したものです。あなたはそれらを探したほうがいいです。

また、このキャッシュベースの実装はメモリを消費するため、関数を複数回呼び出す場合にのみ意味があることに注意してください。

于 2013-02-26T16:08:47.103 に答える
0

まず第一に、再帰を使用していますが、これは時間と空間の両方の複雑さの点で効率的ではありません。反復アプローチを使用する必要があります。

次に、余分なメモリやスペースが問題にならず、パフォーマンスが非常に重要な場合は、後で計算したいすべての数値を事前に計算し、それらが多すぎる場合は配列またはディスクに格納することをお勧めします。メモリー。後で一定時間で値を取得できます。

于 2013-02-26T16:12:13.000 に答える