Python एल्गोरिदम

Memoization के साथ Recursive Fibonacci

पहले निकाले गए Fibonacci values दोबारा calculate न करें।

  • मध्यम
  • 2 मिनट में पढ़ें
  • 1 चलाने योग्य उदाहरण

Memoization के साथ Recursive Fibonacci क्या है?

समस्या क्या है

Fibonacci की recursive परिभाषा सुंदर है लेकिन बहुत धीमी: 40वाँ term निकालने में वही छोटी गणनाएँ करोड़ों बार दोहराई जाती हैं। Memoization इसे एक लाइन में ठीक कर देता है और dynamic programming का एक मुख्य विचार सिखाता है।

ऐसे समझें

Memoization ऐसे छात्र जैसा है जो हर जवाब एक नोटबुक में लिख लेता है। जब fib(5) फिर से पूछा जाता है, तो वह दोबारा मेहनत नहीं करता; नोटबुक से जवाब पढ़ लेता है। हर सवाल सिर्फ़ एक बार हल होता है।

नोटबुक से कोड तक
@cache📓 जवाबों की नोटबुक रखिए
fibonacci(number - 1) + fibonacci(number - 2)🧮 दो छोटे सवालों से हल कीजिए
if number < 2: return number🛑 पहले दो जवाब पता हैं
fibonacci(10)⚡ हर छोटा जवाब एक बार निकलता है: तेज़
हर नतीजा पहली बार में सेव कीजिए; उसके बाद दोबारा इस्तेमाल कीजिए।
एक वाक्य में

Memoization हर फ़ंक्शन कॉल का नतीजा उसके arguments के हिसाब से सेव करता है, ताकि दोबारा कॉल होने पर फिर से गणना करने की जगह सेव किया हुआ नतीजा लौटे।

मुख्य बातें

  1. if number < 2: return number पहले दो term देता है, 0 और 1।
  2. fibonacci(number - 1) + fibonacci(number - 2) परिभाषा को सीधे फ़ॉलो करता है।
  3. functools का @cache हर नतीजा याद रखता है, इसलिए हर fibonacci(k) सिर्फ़ एक बार चलता है।
  4. @cache के बिना fibonacci(10) 177 कॉल करेगा; इसके साथ 11।

इसका उपयोग कब करें?

  • Recursive फ़ंक्शन जो वही subproblems दोहराते हैं: grid में रास्ते, coin change, शब्दों को बाँटना।
  • Dynamic programming के पीछे का विचार सीखना।
  • किसी भी pure फ़ंक्शन को तेज़ करना जो अक्सर एक जैसे arguments से कॉल होता है।

कब ज़रूरत नहीं

  • Side effects वाले या समय के साथ बदलने वाले नतीजों वाले फ़ंक्शन: cache पुराने जवाब लौटाएगा।
  • बहुत गहरा recursion: cache के साथ भी fib(5000) recursion limit पार कर सकता है; लूप से यह नहीं होता।

देखें यह कैसे काम करता है

हर कॉल को देखने के लिए अगला चरण दबाएँ। ध्यान दें कि fib वही छोटे मान बार-बार निकालता है, इसीलिए सरल संस्करण धीमा है।

उदाहरण कोड

कोड चलाएँ →
main.py
from functools import cache

@cache
def fibonacci(number):
    if number < 2:
        return number
    return fibonacci(number - 1) + fibonacci(number - 2)

print(fibonacci(10))
इस उदाहरण के लिए Run बटन बनाएँ

अपेक्षित आउटपुट

55

यह कैसे काम करता है

Cache exponential runtime को O(n) करता है और O(n) memory लेता है।

मान बदलें और Python इंस्टॉल किए बिना CodeUtility ऑनलाइन Python कंपाइलर में प्रोग्राम चलाएँ।

अभ्यास के कार्य

बड़े dataset पर जाने से पहले input बदलें और edge cases की जाँच करें।

  1. खाली input, एक element और duplicate values जाँचें।
  2. हर चरण के बाद state दिखाएँ।
  3. Performance को दूसरे solution से तुलना करें।
Python IDE में चलाएँ →

आम गलतियाँ

Cache के बिना recursion

वही वैल्यू बार-बार निकाली जाती हैं, और fib(40) में कई सेकंड लगते हैं।

समस्या
def fibonacci(number):
    if number < 2:
        return number
    return fibonacci(number - 1) + fibonacci(number - 2)
सुधार
@cache
def fibonacci(number):
    if number < 2:
        return number
    return fibonacci(number - 1) + fibonacci(number - 2)

यह पाठ पूरा कर लिया?

अपनी प्रगति ट्रैक करने के लिए इसे सीखा हुआ मार्क करें।

अगला: Python में Stack Data Structure →

चैलेंज से अभ्यास करें

इस पाठ में सीखी बात से एक असली समस्या हल करें। हर चैलेंज ब्राउज़र में चलता है, तुरंत टेस्ट और AI रिव्यू के साथ।

सभी चैलेंज