有没有更好的办法（性能）计算斐波纳契比这个？ [英] Is there a better way (performance) calculate fibonacci than this one?

问题描述

我做了这个code ..我需要得到它的最好的..我真的需要计算斐波那契数的最佳性能..请帮助是..

我读过这类计算的一些code，我觉得我得到的最好的人。

Avaliate这对我来说..嘿..

PS：我真的需要的BigInteger。我会计算庞大数量的斐波那契数

PS2：我算过了一些大的数字，这个算法，我有一个伟大的响应时间..但我需要知道它是否会更好。

PS3：运行此code，你需要使用这个VM参数 -Xss16384k （堆栈大小）

 公共类斐波那契{

    私有静态的BigInteger [] fibTmp = {BigInteger.valueOf（0），BigInteger.valueOf（1）};

    公共静态的BigInteger斐波纳契（长V）{

        BigInteger的FIB = BigInteger.valueOf（0）;

        如果（ⅴ== 1）{

            FIB = BigInteger.valueOf（1）;

        }否则，如果（V == 0）{

            FIB = BigInteger.valueOf（0）;

        } 其他 {

            BigInteger的V1 =斐波纳契（V  -  1）;
            的BigInteger V2 = fibTmp [（int）的（五 -  2）];

            FIB = v1.add（V2）;
        }

        同步（fibTmp）{

            如果（fibTmp.length  -  1＆其中;ⅴ）
                fibTmp = Arrays.copyOf（fibTmp，（int）的（V + 10））;

            fibTmp [（INT）V] = FIB;
        }

        返回FIB;
    }
}
 

解决方案

您实现不为任何像样的数字工作，因为它使堆栈溢出。

我看不出有任何理由要在这里使用递归。递归是pretty的，但一般较重（它的语言而定）。这里有一个工作实现用一个简单的为循环：

 私有静态的BigInteger [] fibTmp = {BigInteger.ZERO，BigInteger.ONE};
私有静态诠释maxCached = 1;
公共静态BigInteger的斐波纳契（INT V）{
    如果（fibTmp.length＆LT; = V）{
        fibTmp = Arrays.copyOf（fibTmp，V * 5/4）;
    }
    对于（; maxCached＆LT;伏;）{
        maxCached ++;
        BigInteger的V1 = fibTmp [maxCached  -  1];
        的BigInteger V2 = fibTmp [maxCached  -  2];
        fibTmp [maxCached] = v1.add（V2）;
    }
    返回fibTmp [V];
}
 

这是一个直接实现，而不寻找文学高效的斐波那契算法。你最好去找他们。

另请注意，这个基于缓存实现的内存昂贵，如果你调用该函数多次才有意义。

I made this code.. And I need to get the best of it.. I really need the best performance of calculating fibonacci numbers.. please help be..

I've read some code of this type of calculation and I think I got the best of them..

Avaliate this for me.. plz..

ps: And I really need the BigInteger.. I'll calculate Fibonacci of enormous numbers

ps2: I have calculated some big numbers with this algorithm and I got a great response time.. but I need to know whether it could be better

ps3: to run this code you'll need to use this VM argument -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;
    }
}

解决方案

Your implementation doesn't work for any decent number because it makes the stack overflow.

I don't see any reason to use recursivity here. Recursivity is pretty but generally heavier (it's language dependent). Here's a working implementation with a simple for loop :

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];
}

That's a direct implementation without looking for an efficient Fibonacci algorithm in the literature. You'd better look for them.

Note also that this cache based implementation is memory costly and makes only sense if you call the function multiple times.

这篇关于有没有更好的办法（性能）计算斐波纳契比这个？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！