Memoization बनाम Tabulation
subproblem answers को cache करने के दो तरीके
Memoization बनाम Tabulation, CoddyKit पर Competitive Programming Academy का एक निःशुल्क पाठ है। यह 4 में से 1वाँ पाठ है। आप नीचे पूरा पाठ निःशुल्क पढ़ सकते हैं—फिर अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर के साथ ब्राउज़र में इसका व्यावहारिक अभ्यास कर सकते हैं। यह Competitive Programming Academy सीखने के मार्ग का हिस्सा है और आपकी प्रगति वेब तथा CoddyKit ऐप पर सिंक होती रहती है। Competitive Programming Academy पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
कैश का उपयोग क्यों करें
साधारण पुनरावर्तन एक ही काम बार-बार दोहराता है। डायनेमिक प्रोग्रामिंग हर उत्तर को एक बार सहेजती है, इसलिए उसे फिर से गणना नहीं करना पड़ता।
fib(40) # slow: recomputes endlesslyएक-दूसरे से दोहरती उप-समस्याएँ
डीपी तब लागू होती है जब कोई समस्या एक-दूसरे से दोहरती उप-समस्याओं में विभाजित हो। पुनरावर्तन की कई शाखाओं में वही छोटी समस्या बार-बार दिखाई देती है।
fib(5) needs fib(3) twiceऊपर से नीचे: मेमोइज़ेशन
मेमोइज़ेशन कैश के साथ किया गया साधारण पुनरावर्तन है। आप आवश्यकता के अनुसार गणना करते हैं और हर इनपुट को पहली बार देखने पर उसका परिणाम सहेज लेते हैं।
memo = {}पाइथन में आसान मेमोइज़ेशन
lru_cache डेकोरेटर एक पंक्ति में धीमे पुनरावर्तन को तेज़ डीपी में बदल देता है और हर कॉल को अपने-आप कैश कर लेता है।
from functools import lru_cache
@lru_cache(None)
def f(n): ...नीचे से ऊपर: सारणीकरण
सारणीकरण सबसे छोटी अवस्थाओं से शुरू करके उत्तर तक एक सारणी भरता है और पुनरावर्तन के बजाय लूप का उपयोग करता है।
dp = [0] * (n + 1)सारणीबद्ध फ़िबोनाची
आधार मान सेट करें, फिर हर सेल को पहले से गणना किए गए मान पढ़ने दें। कोई कॉल स्टैक नहीं, केवल एक साफ़ लूप।
dp[0], dp[1] = 0, 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]एक ही उत्तर, अलग शैली
मेमोइज़ेशन और सारणीकरण एक ही पुनरावृत्ति-संबंध को हल करते हैं। अंतर केवल दिशा का है: आवश्यकता के अनुसार ऊपर से नीचे, या क्रम से नीचे से ऊपर।
मेमोइज़ेशन को कब प्राथमिकता दें
मेमोइज़ेशन तब अपनाएँ जब पुनरावृत्ति-संबंध स्वाभाविक रूप से लिखना आसान हो और संभव है कि आपको हर अवस्था की आवश्यकता न पड़े।
सारणीकरण को कब प्राथमिकता दें
कसे हुए लूप के लिए, पुनरावर्तन-सीमा की त्रुटियों से बचने के लिए और तब सारणीकरण चुनें जब आपको पूरी सारणी की गणना वैसे भी करनी हो।
import sys; sys.setrecursionlimit(10**6)पुनरावर्तन सीमा पर ध्यान दें
गहरे मेमोइज़ किए गए पुनरावर्तन में पाइथन की पुनरावर्तन सीमा पार हो सकती है और बड़े इनपुट पर रनटाइम त्रुटि के साथ कार्यक्रम रुक सकता है।
दोनों की एक ही लागत है
दोनों तरीकों में गति इसलिए बढ़ती है क्योंकि हर अवस्था को एक बार हल किया जाता है। कुल समय अवस्थाओं की संख्या को प्रति अवस्था किए गए काम से गुणा करने के बराबर होता है।
त्वरित जाँच
कौन-सा तरीका लूप के साथ नीचे से ऊपर एक सारणी भरता है?
पुनरावलोकन: दो रास्ते, एक डीपी
अब आप उप-समस्याओं को दो तरीकों से कैश कर सकते हैं। मेमोइज़ेशन ऊपर से नीचे पुनरावर्तन करता है; सारणीकरण नीचे से ऊपर लूप चलाता है। जो तरीका अधिक स्पष्ट लगे, उसे चुनें। ✨
एआई शिक्षक के साथ Python सीखें — निःशुल्क
अपने ब्राउज़र में वास्तविक कोड लिखें और चलाएँ, चौबीसों घंटे एआई शिक्षक से तुरंत सहायता पाएँ, और वेब या ऐप पर वहीं से शुरू करें जहाँ आपने छोड़ा था।
- पाठ्यक्रम
- 30
- पाठ
- 120
अक्सर पूछे जाने वाले प्रश्न
क्या “Memoization बनाम Tabulation” पाठ निःशुल्क है?
हाँ—“Memoization बनाम Tabulation” का पूरा पाठ यहाँ वेब पर निःशुल्क पढ़ा जा सकता है। इंटरैक्टिव अभ्यास (अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर) करने और Competitive Programming Academy पाठ्यक्रम का बाकी हिस्सा अनलॉक करने के लिए CoddyKit PRO लें। Competitive Programming Academy पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
“Memoization बनाम Tabulation” में मैं क्या सीखूँगा?
subproblem answers को cache करने के दो तरीके आप ब्राउज़र में सीधे चलाए जाने वाले व्यावहारिक कोड के साथ Competitive Programming Academy का अभ्यास करते हैं, और पाठ पूरा करते समय 24/7 एआई ट्यूटर आपके प्रश्नों के उत्तर देता है।
क्या Competitive Programming Academy शुरू करने के लिए मुझे किसी अनुभव की आवश्यकता है?
पहले के अनुभव की आवश्यकता नहीं है। CoddyKit पर Competitive Programming Academy शुरुआती से लेकर उन्नत शिक्षार्थियों तक सभी के लिए व्यवस्थित किया गया है, इसलिए आप यहीं से या शुरुआत से सीखना शुरू कर सकते हैं और अपनी गति से आगे बढ़ सकते हैं। यह 4 में से 1वाँ पाठ है।
“Memoization बनाम Tabulation” पाठ पूरा करने में कितना समय लगता है?
CoddyKit का अधिकांश पाठ लगभग 5–10 मिनट में पूरा हो जाता है। हर पाठ छोटा और संवादात्मक है, इसलिए आप लगातार प्रगति करते हैं और वेब या ऐप पर वहीं से सीखना जारी रख सकते हैं जहाँ आपने छोड़ा था।
क्या मैं इस Competitive Programming Academy पाठ में कोड लिख और चला सकता हूँ?
हाँ। हर Competitive Programming Academy पाठ में एक अंतर्निर्मित कोड संपादक शामिल है, जिससे आप सीधे अपने ब्राउज़र में वास्तविक कोड लिख और चला सकते हैं और तुरंत एआई प्रतिक्रिया पा सकते हैं—स्थानीय सेटअप की आवश्यकता नहीं है।
इस पाठ्यक्रम के सभी पाठ
- Memoization बनाम Tabulation
- State और Transition परिभाषित करना
- Climbing Stairs और Coin Combinations
- Longest Increasing Subsequence