Bundan daha iyi bir yol (performans) fibonacci hesaplıyor mu?

Question

Ben .. Bu kodu yapılmış Ve ben gerçekten

Ben bu tip bazı kod okudum .. olmak lütfen yardım .. hesaplanması Fibonacci sayılarının en iyi performansı gerek .. Bunu en iyi almak gerekir hesaplama ve ben onlardan en iyisi olduğunu düşünüyorsun .. benim için

Avaliate bu .. plz ..

ps: ve gerçekten ben muazzam sayıların Fibonacci'yi hesaplarız .. BigInteger ihtiyaç

ps2: Bu algoritma ile bazı büyük sayıları hesapladım ve harika bir yanıt zamanı aldım .. ama bilmem gerek Daha iyi

ps3 olabilir: Bu kod çalıştırmasına o yığın taşması yapar çünkü bu VM argüman -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; 
    } 
} 

Answer 1

Uygulamanız herhangi nezih sayı için çalışmıyor kullanmanız gerekir .

Burada özyinelemeyi kullanmak için bir neden göremiyorum. Özyinelelik oldukça güzel ancak genel olarak daha ağırdır (dile bağlıdır). Burada basit for döngü ile bir çalışma uygulama görebilirsiniz:

literatürde verimli bir Fibonacci algoritması için bakmadan doğrudan uygulanmasını var

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

. Onları arasan iyi olur.

Ayrıca, bu önbellek tabanlı uygulamanın bellek maliyetli olduğunu ve işlevi birden çok kez çağırdığınızda yalnızca anlam ifade ettiğini unutmayın.

Answer 2

Her şeyden önce, hem zaman hem de alan karmaşıklığı açısından verimli olmayan özyinelemeyi kullanıyorsunuz. Yinelemeli yaklaşımı kullanmalısın.

Daha fazla bellek ya da alan dağıtıcı değilse ve performans gerçekten çok önemliyse, daha sonra hesaplamak istediğiniz tüm sayıları önceden işlemek ve bir dizide veya diskinizde saklamak isteyebilirsiniz. hafızan için çok fazla. Daha sonra değeri sabit zamanda alabilirsiniz.

Answer 3

Evet, daha iyi bir yol var. Bu, bir log(n) testidir ve giriş olarak pozitif bir tamsayı verildiğinde, Fibonacci'nin bir değerini keyfi doğrulukla hesaplamak için test edilmiş ve çok etkili bir yoldur. Algoritma SICP 'ın exercise 1.19 bir çözüm uyarlanmıştır:

orada (1.19 egzersiz aşağı kaydırın) nasıl çalıştığını gösteren bir açıklama, ve o dile getirilmiştir kitabın bağlantılı bölümde

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; 

} 

o:

Bu, Fibonacci sayılarının logaritmik sayıda adımda hesaplanması için akıllı bir algoritmadır ... Bu egzersiz, Kaldewaij, Anne'deki bir örneğe dayanarak Joe Stoy tarafından önerilmiştir. 1990. Programlama: Algoritmaların Türetilmesi. Tabii

, aynı değerler önceki değerleri saklamak için bir harita kullanarak, örneğin üzerinden hesaplanacak tekrar tekrar ileri performans kazançları zaten hesaplanmıştır memoizing sonuçları elde edilebilir gerekiyorsa.