Memoization के साथ Recursive Fibonacci
पहले निकाले गए Fibonacci values दोबारा calculate न करें।
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 के हिसाब से सेव करता है, ताकि दोबारा कॉल होने पर फिर से गणना करने की जगह सेव किया हुआ नतीजा लौटे।
मुख्य बातें
if number < 2: return numberपहले दो term देता है, 0 और 1।fibonacci(number - 1) + fibonacci(number - 2)परिभाषा को सीधे फ़ॉलो करता है।functoolsका@cacheहर नतीजा याद रखता है, इसलिए हरfibonacci(k)सिर्फ़ एक बार चलता है।@cacheके बिनाfibonacci(10)177 कॉल करेगा; इसके साथ 11।
इसका उपयोग कब करें?
- Recursive फ़ंक्शन जो वही subproblems दोहराते हैं: grid में रास्ते, coin change, शब्दों को बाँटना।
- Dynamic programming के पीछे का विचार सीखना।
- किसी भी pure फ़ंक्शन को तेज़ करना जो अक्सर एक जैसे arguments से कॉल होता है।
कब ज़रूरत नहीं
- Side effects वाले या समय के साथ बदलने वाले नतीजों वाले फ़ंक्शन: cache पुराने जवाब लौटाएगा।
- बहुत गहरा recursion: cache के साथ भी
fib(5000)recursion limit पार कर सकता है; लूप से यह नहीं होता।
देखें यह कैसे काम करता है
हर कॉल को देखने के लिए अगला चरण दबाएँ। ध्यान दें कि fib वही छोटे मान बार-बार निकालता है, इसीलिए सरल संस्करण धीमा है।
उदाहरण कोड
from functools import cache
@cache
def fibonacci(number):
if number < 2:
return number
return fibonacci(number - 1) + fibonacci(number - 2)
print(fibonacci(10))
अपेक्षित आउटपुट
55
यह कैसे काम करता है
Cache exponential runtime को O(n) करता है और O(n) memory लेता है।
मान बदलें और Python इंस्टॉल किए बिना CodeUtility ऑनलाइन Python कंपाइलर में प्रोग्राम चलाएँ।
अभ्यास के कार्य
बड़े dataset पर जाने से पहले input बदलें और edge cases की जाँच करें।
- खाली input, एक element और duplicate values जाँचें।
- हर चरण के बाद state दिखाएँ।
- Performance को दूसरे solution से तुलना करें।
आम गलतियाँ
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)
यह पाठ पूरा कर लिया?
अपनी प्रगति ट्रैक करने के लिए इसे सीखा हुआ मार्क करें।
चैलेंज से अभ्यास करें
इस पाठ में सीखी बात से एक असली समस्या हल करें। हर चैलेंज ब्राउज़र में चलता है, तुरंत टेस्ट और AI रिव्यू के साथ।
- फिबोनाच्ची संख्या n-वीं फिबोनाच्ची संख्या लौटाएँ। आसान
- पासा अनुक्रमणिकाएँ गिनें दिए गए योग के लिए क्रमबद्ध पासा-फेंक अनुक्रमणिकाएँ गिनें। मध्यम