क्या कोई बेहतर तरीका है (प्रदर्शन) इस से फाइबोनैकी की गणना करता है?

Question

मैंने यह कोड बनाया .. और मुझे इसे सबसे अच्छा प्राप्त करने की आवश्यकता है .. मुझे वास्तव में फाइबोनैकी संख्याओं की गणना करने का सबसे अच्छा प्रदर्शन चाहिए .. कृपया मदद करें ..

मैंने इस प्रकार के कुछ कोड पढ़े हैं गणना और मैं मैं उनमें से सबसे अच्छा मिल गया लगता है ..

Avaliate यह मेरे लिए .. plz ..

ps: और मैं वास्तव में BigInteger .. की जरूरत है मैं भारी संख्या के फाइबोनैचि गणना करेंगे

ps2: मैंने इस एल्गोरिदम के साथ कुछ बड़ी संख्याओं की गणना की है और मुझे एक अच्छा प्रतिक्रिया समय मिला है .. लेकिन मुझे यह जानने की ज़रूरत है कि क्या यह बेहतर

PS3 हो सकता है: इस कोड को चलाने के लिए आप क्योंकि यह ढेर अतिप्रवाह बनाता है यह वीएम तर्क -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

आपका क्रियान्वयन किसी भी सभ्य संख्या के लिए काम नहीं करता है का उपयोग करना होगा ।

मुझे यहां रिकर्सिविटी का उपयोग करने का कोई कारण नहीं दिख रहा है। रिकर्सिविटी सुंदर है लेकिन आम तौर पर भारी है (यह भाषा निर्भर है)। यहाँ एक सरल 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]; 
} 

साहित्य में एक कुशल फाइबोनैचि एल्गोरिथ्म के लिए देख के बिना एक सीधा कार्यान्वयन है यही कारण है कि। आप बेहतर उनके लिए देखो।

ध्यान दें कि यह कैश आधारित कार्यान्वयन मेमोरी महंगा है और यदि आप फ़ंक्शन को कई बार कॉल करते हैं तो केवल तभी समझ में आता है।

Answer 2

सबसे पहले, आप रिकर्सन का उपयोग कर रहे हैं, जो समय और अंतरिक्ष जटिलता दोनों के मामले में कुशल नहीं है। आपको पुनरावृत्ति दृष्टिकोण का उपयोग करना चाहिए।

फिर यदि अतिरिक्त मेमोरी या स्पेस डीलर ब्रेकर नहीं है और यदि प्रदर्शन वास्तव में महत्वपूर्ण है, तो हो सकता है कि आप उन सभी नंबरों को प्रीकंप्यूट करना चाहें जिन्हें आप बाद में गणना करना चाहते हैं और उन्हें किसी सरणी में या डिस्क पर स्टोर करना चाहते हैं आपकी याददाश्त के लिए बहुत कुछ। बाद में आप निरंतर समय में मूल्य प्राप्त कर सकते हैं।

Answer 3

हां, एक बेहतर तरीका है। यह एक log(n) इनपुट के रूप में एक सकारात्मक पूर्णांक दिया गया है, मनमाना परिशुद्धता के साथ फाइबोनैकी के एक मूल्य की गणना के लिए परीक्षण और बहुत ही कुशल तरीका है। एल्गोरिथ्म SICP के exercise 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 व्यायाम करने के लिए नीचे स्क्रॉल करें) की व्याख्या दी गई है, और यह कहा गया है कि:

यह एक चतुर एल्गोरिदम है जो फिबोनैची संख्याओं को चरणों की एक संख्या में कंप्यूटिंग करने के लिए है ... इस अभ्यास को क्लोवेज, ऐनी में एक उदाहरण के आधार पर जो स्टॉय द्वारा सुझाया गया था। 1 99 0। प्रोग्रामिंग: एल्गोरिदम का व्युत्पन्न।

बेशक

, अगर एक ही मान पिछले मान संग्रहीत करने के लिए एक मानचित्र का उपयोग उदाहरण के लिए, से अधिक की गणना करने और फिर से, आगे निष्पादन लाभ द्वारा memoizing परिणाम है कि पहले से ही गणना की है प्राप्त किया जा सकता की जरूरत है।