मेमोइजेशन: Difference between revisions
No edit summary |
No edit summary |
||
| Line 59: | Line 59: | ||
=== कार्यात्मक प्रोग्रामिंग === | === कार्यात्मक प्रोग्रामिंग === | ||
{{main|थंक #कार्यात्मक प्रोग्रामिंग}} | {{main|थंक #कार्यात्मक प्रोग्रामिंग}} | ||
[[कार्यात्मक प्रोग्रामिंग]] भाषाओं के लिए संकलक में मेमोइज़ेशन का अत्यधिक उपयोग किया जाता है, जो अक्सर नाम मूल्यांकन रणनीति द्वारा कॉल का उपयोग करते हैं। तर्क मूल्यों की गणना के साथ ओवरहेड से बचने के लिए, इन भाषाओं के संकलक तर्क मूल्यों की गणना करने के लिए [[थंक]] नामक सहायक कार्यों का भारी उपयोग करते हैं, और बार-बार होने वाली गणनाओं से बचने के लिए इन कार्यों को याद करते हैं। | [[कार्यात्मक प्रोग्रामिंग]] भाषाओं के लिए संकलक में मेमोइज़ेशन का अत्यधिक उपयोग किया जाता है, जो अक्सर नाम मूल्यांकन रणनीति द्वारा कॉल का उपयोग करते हैं। तर्क मूल्यों की गणना के साथ ओवरहेड से बचने के लिए, इन भाषाओं के संकलक तर्क मूल्यों की गणना करने के लिए [[थंक]] नामक सहायक कार्यों का भारी उपयोग करते हैं, और बार-बार होने वाली गणनाओं से बचने के लिए इन कार्यों को याद करते हैं। | ||
| Line 66: | Line 65: | ||
जबकि मेमोइज़ेशन को [[कंप्यूटर प्रोग्राम]]र द्वारा आंतरिक रूप से और स्पष्ट रूप से फ़ंक्शंस में जोड़ा जा सकता है, उसी तरह उपरोक्त मेमोइज़्ड संस्करण <code>factorial</code> लागू किया गया है, संदर्भित रूप से पारदर्शी कार्यों को स्वचालित रूप से बाह्य रूप से याद किया जा सकता है।<ref name="Norvig1991" />[[पीटर नॉरविग]] द्वारा नियोजित तकनीकों का न केवल [[ सामान्य लिस्प ]] (जिस भाषा में उनके पेपर ने स्वचालित मेमोइज़ेशन प्रदर्शित किया था) में, बल्कि विभिन्न अन्य [[प्रोग्रामिंग भाषा]]ओं में भी आवेदन किया है। शब्द पुनर्लेखन के अध्ययन में स्वचालित संस्मरण के अनुप्रयोगों का भी औपचारिक रूप से पता लगाया गया है<ref name="Hoffman1992">{{cite book |last=Hoffman |first=Berthold |chapter=Term Rewriting with Sharing and Memoïzation |title=Algebraic and Logic Programming: Third International Conference, Proceedings, Volterra, Italy, 2–4 September 1992 |series=Lecture Notes in Computer Science |editor-first=H. |editor-last=Kirchner |editor2-first=G. |editor2-last=Levi |pages=128–142 |year=1992 |volume=632 |location=Berlin |publisher=Springer |isbn=978-3-540-55873-6 |doi=10.1007/BFb0013824 }}</ref> और कृत्रिम बुद्धि।<ref name="MayfieldEtAl1995">{{cite book |last1=Mayfield |first1=James |first2=T. |last2=Finin |first3=M. |last3=Hall |display-authors=1 |chapter-url=http://ebiquity.umbc.edu/get/a/publication/799.pdf |chapter=Using Automatic Memoization as a Software Engineering Tool in Real-World AI Systems |title=Proceedings of the Eleventh IEEE Conference on Artificial Intelligence for Applications (CAIA '95) |pages=87–93 |year=1995 |doi=10.1109/CAIA.1995.378786 |hdl=11603/12722 |isbn=0-8186-7070-3 |s2cid=8963326 }}</ref> | जबकि मेमोइज़ेशन को [[कंप्यूटर प्रोग्राम]]र द्वारा आंतरिक रूप से और स्पष्ट रूप से फ़ंक्शंस में जोड़ा जा सकता है, उसी तरह उपरोक्त मेमोइज़्ड संस्करण <code>factorial</code> लागू किया गया है, संदर्भित रूप से पारदर्शी कार्यों को स्वचालित रूप से बाह्य रूप से याद किया जा सकता है।<ref name="Norvig1991" />[[पीटर नॉरविग]] द्वारा नियोजित तकनीकों का न केवल [[ सामान्य लिस्प ]] (जिस भाषा में उनके पेपर ने स्वचालित मेमोइज़ेशन प्रदर्शित किया था) में, बल्कि विभिन्न अन्य [[प्रोग्रामिंग भाषा]]ओं में भी आवेदन किया है। शब्द पुनर्लेखन के अध्ययन में स्वचालित संस्मरण के अनुप्रयोगों का भी औपचारिक रूप से पता लगाया गया है<ref name="Hoffman1992">{{cite book |last=Hoffman |first=Berthold |chapter=Term Rewriting with Sharing and Memoïzation |title=Algebraic and Logic Programming: Third International Conference, Proceedings, Volterra, Italy, 2–4 September 1992 |series=Lecture Notes in Computer Science |editor-first=H. |editor-last=Kirchner |editor2-first=G. |editor2-last=Levi |pages=128–142 |year=1992 |volume=632 |location=Berlin |publisher=Springer |isbn=978-3-540-55873-6 |doi=10.1007/BFb0013824 }}</ref> और कृत्रिम बुद्धि।<ref name="MayfieldEtAl1995">{{cite book |last1=Mayfield |first1=James |first2=T. |last2=Finin |first3=M. |last3=Hall |display-authors=1 |chapter-url=http://ebiquity.umbc.edu/get/a/publication/799.pdf |chapter=Using Automatic Memoization as a Software Engineering Tool in Real-World AI Systems |title=Proceedings of the Eleventh IEEE Conference on Artificial Intelligence for Applications (CAIA '95) |pages=87–93 |year=1995 |doi=10.1109/CAIA.1995.378786 |hdl=11603/12722 |isbn=0-8186-7070-3 |s2cid=8963326 }}</ref> | ||
प्रोग्रामिंग भाषाओं में जहां कार्य [[प्रथम श्रेणी की वस्तु]]एं हैं (जैसे [[लुआ (प्रोग्रामिंग भाषा)]], [[पायथन (प्रोग्रामिंग भाषा)]], या [[पर्ल]]<ref name="perl-firstclass">{{cite web|title=Bricolage: Memoization|url=http://perl.plover.com/MiniMemoize/memoize.html}}</ref>), पैरामीटर के दिए गए सेट के लिए मान की गणना करने के बाद स्वचालित मेमोइज़ेशन को (रन-टाइम पर) फ़ंक्शन को इसकी गणना मूल्य के साथ कार्यान्वित किया जा सकता है। फ़ंक्शन जो इस वैल्यू-फॉर-फ़ंक्शन-ऑब्जेक्ट प्रतिस्थापन को करता है, सामान्य रूप से किसी भी संदर्भित पारदर्शी फ़ंक्शन को लपेट सकता है। निम्नलिखित स्यूडोकोड पर विचार करें (जहां यह माना जाता है कि कार्य प्रथम श्रेणी के मान हैं): | प्रोग्रामिंग भाषाओं में जहां कार्य [[प्रथम श्रेणी की वस्तु]]एं हैं (जैसे [[लुआ (प्रोग्रामिंग भाषा)]], [[पायथन (प्रोग्रामिंग भाषा)]], या [[पर्ल]]<ref name="perl-firstclass">{{cite web|title=Bricolage: Memoization|url=http://perl.plover.com/MiniMemoize/memoize.html}}</ref>), पैरामीटर के दिए गए सेट के लिए मान की गणना करने के बाद स्वचालित मेमोइज़ेशन को (रन-टाइम पर) फ़ंक्शन को इसकी गणना मूल्य के साथ कार्यान्वित किया जा सकता है। फ़ंक्शन जो इस वैल्यू-फॉर-फ़ंक्शन-ऑब्जेक्ट प्रतिस्थापन को करता है, सामान्य रूप से किसी भी संदर्भित पारदर्शी फ़ंक्शन को लपेट सकता है। निम्नलिखित स्यूडोकोड पर विचार करें (जहां यह माना जाता है कि कार्य प्रथम श्रेणी के मान हैं): | ||
फ़ंक्शन मेमोइज्ड-कॉल (एफ फ़ंक्शन ऑब्जेक्ट पैरामीटर है) | फ़ंक्शन मेमोइज्ड-कॉल (एफ फ़ंक्शन ऑब्जेक्ट पैरामीटर है) | ||
यदि F के पास कोई संलग्न सरणी मान नहीं है | यदि F के पास कोई संलग्न सरणी मान नहीं है | ||
| Line 79: | Line 78: | ||
वापसी F.values [तर्क]; | वापसी F.values [तर्क]; | ||
अंत फ़ंक्शन | अंत फ़ंक्शन | ||
स्वचालित रूप से याद किए गए संस्करण को कॉल करने के लिए <code>factorial</code> कॉल करने के अतिरिक्त उपरोक्त रणनीति का उपयोग करना <code>factorial</code> सीधे, कोड आमंत्रित करता है <code>memoized-call(factorial(''n''))</code>. इस तरह की प्रत्येक कॉल पहले यह देखने के लिए जांच करती है कि क्या परिणामों को संग्रहीत करने के लिए एक धारक सरणी आवंटित की गई है, और यदि नहीं, तो वह सरणी संलग्न करती है। यदि स्थिति पर कोई प्रविष्टि उपस्थित नहीं है <code>values[arguments]</code> (कहाँ <code>arguments</code> साहचर्य सरणी की कुंजी के रूप में उपयोग किया जाता है), एक वास्तविक कॉल किया जाता है <code>factorial</code> प्रदान किए गए तर्कों के साथ। अंत में, कुंजी स्थिति में सरणी में प्रविष्टि कॉलर को वापस कर दी जाती है। | स्वचालित रूप से याद किए गए संस्करण को कॉल करने के लिए <code>factorial</code> कॉल करने के अतिरिक्त उपरोक्त रणनीति का उपयोग करना <code>factorial</code> सीधे, कोड आमंत्रित करता है <code>memoized-call(factorial(''n''))</code>. इस तरह की प्रत्येक कॉल पहले यह देखने के लिए जांच करती है कि क्या परिणामों को संग्रहीत करने के लिए एक धारक सरणी आवंटित की गई है, और यदि नहीं, तो वह सरणी संलग्न करती है। यदि स्थिति पर कोई प्रविष्टि उपस्थित नहीं है <code>values[arguments]</code> (कहाँ <code>arguments</code> साहचर्य सरणी की कुंजी के रूप में उपयोग किया जाता है), एक वास्तविक कॉल किया जाता है <code>factorial</code> प्रदान किए गए तर्कों के साथ। अंत में, कुंजी स्थिति में सरणी में प्रविष्टि कॉलर को वापस कर दी जाती है। | ||
उपरोक्त रणनीति के लिए प्रत्येक कॉल पर एक फ़ंक्शन के लिए स्पष्ट रैपिंग की आवश्यकता होती है जिसे याद किया जाना है। उन भाषाओं में जो क्लोजर (कंप्यूटर विज्ञान) की अनुमति देते हैं, मेमोइज़ेशन को [[समारोह वस्तु|फ़ंक्शन वस्तु]] फ़ैक्टरी के माध्यम से स्पष्ट रूप से प्रभावित किया जा सकता है जो एक [[डेकोरेटर पैटर्न]] में लिपटे मेमोइज़्ड फ़ंक्शन ऑब्जेक्ट को लौटाता है। स्यूडोकोड में, इसे इस प्रकार व्यक्त किया जा सकता है: | उपरोक्त रणनीति के लिए प्रत्येक कॉल पर एक फ़ंक्शन के लिए स्पष्ट रैपिंग की आवश्यकता होती है जिसे याद किया जाना है। उन भाषाओं में जो क्लोजर (कंप्यूटर विज्ञान) की अनुमति देते हैं, मेमोइज़ेशन को [[समारोह वस्तु|फ़ंक्शन वस्तु]] फ़ैक्टरी के माध्यम से स्पष्ट रूप से प्रभावित किया जा सकता है जो एक [[डेकोरेटर पैटर्न]] में लिपटे मेमोइज़्ड फ़ंक्शन ऑब्जेक्ट को लौटाता है। स्यूडोकोड में, इसे इस प्रकार व्यक्त किया जा सकता है: | ||
फ़ंक्शन कंस्ट्रक्शन-मेमोइज़्ड-फ़ंक्टर (F एक फ़ंक्शन ऑब्जेक्ट पैरामीटर है) | फ़ंक्शन कंस्ट्रक्शन-मेमोइज़्ड-फ़ंक्टर (F एक फ़ंक्शन ऑब्जेक्ट पैरामीटर है) | ||
memoized-version नामक फ़ंक्शन ऑब्जेक्ट आवंटित करें; | memoized-version नामक फ़ंक्शन ऑब्जेक्ट आवंटित करें; | ||
| Line 102: | Line 101: | ||
संस्मरण-संस्करण लौटाएं; | संस्मरण-संस्करण लौटाएं; | ||
अंत फ़ंक्शन | अंत फ़ंक्शन | ||
कॉल करने के अतिरिक्त <code>factorial</code>, एक नया फ़ंक्शन ऑब्जेक्ट <code>memfact</code> निम्नानुसार बनाया गया है: | कॉल करने के अतिरिक्त <code>factorial</code>, एक नया फ़ंक्शन ऑब्जेक्ट <code>memfact</code> निम्नानुसार बनाया गया है: | ||
| Line 112: | Line 111: | ||
अनिवार्य रूप से, इस तरह की तकनीकों में मूल फ़ंक्शन ऑब्जेक्ट को बनाए गए फ़ंक्टर को संलग्न करना और कॉल को अग्रेषित करना मूल फ़ंक्शन को उपनाम के माध्यम से याद किया जाता है जब वास्तविक फ़ंक्शन के लिए कॉल की आवश्यकता होती है (अंतहीन पुनरावर्तन से बचने के लिए), जैसा कि नीचे दिखाया गया है: | अनिवार्य रूप से, इस तरह की तकनीकों में मूल फ़ंक्शन ऑब्जेक्ट को बनाए गए फ़ंक्टर को संलग्न करना और कॉल को अग्रेषित करना मूल फ़ंक्शन को उपनाम के माध्यम से याद किया जाता है जब वास्तविक फ़ंक्शन के लिए कॉल की आवश्यकता होती है (अंतहीन पुनरावर्तन से बचने के लिए), जैसा कि नीचे दिखाया गया है: | ||
फ़ंक्शन कंस्ट्रक्शन-मेमोइज़्ड-फ़ंक्टर (F एक फ़ंक्शन ऑब्जेक्ट पैरामीटर है) | फ़ंक्शन कंस्ट्रक्शन-मेमोइज़्ड-फ़ंक्टर (F एक फ़ंक्शन ऑब्जेक्ट पैरामीटर है) | ||
memoized-version नामक फ़ंक्शन ऑब्जेक्ट आवंटित करें; | memoized-version नामक फ़ंक्शन ऑब्जेक्ट आवंटित करें; | ||
| Line 134: | Line 133: | ||
संस्मरण-संस्करण लौटाएं; | संस्मरण-संस्करण लौटाएं; | ||
अंत फ़ंक्शन | अंत फ़ंक्शन | ||
(नोट: ऊपर दिखाए गए कुछ चरणों को कार्यान्वयन भाषा द्वारा अप्रत्यक्ष रूप से प्रबंधित किया जा सकता है और उदाहरण के लिए प्रदान किया गया है।) | (नोट: ऊपर दिखाए गए कुछ चरणों को कार्यान्वयन भाषा द्वारा अप्रत्यक्ष रूप से प्रबंधित किया जा सकता है और उदाहरण के लिए प्रदान किया गया है।) | ||
=== पार्सर्स === | === पार्सर्स === | ||
जब एक टॉप-डाउन [[ पदच्छेद ]] | टॉप-डाउन पार्सर एक अस्पष्ट संदर्भ-मुक्त व्याकरण (CFG) के संबंध में एक सिंटैक्टिक अस्पष्टता इनपुट को पार्स करने का प्रयास करता है, तो उसे चरणों की एक घातीय संख्या (इनपुट की लंबाई के संबंध में) की आवश्यकता हो सकती है सभी संभावित पार्स पेड़ बनाने के लिए सीएफजी के सभी विकल्पों का प्रयास करें। इसके लिए अंततः घातीय मेमोरी स्पेस की आवश्यकता होगी। 1991 में पीटर नॉरविग द्वारा मेमोइज़ेशन को एक पार्सिंग रणनीति के रूप में खोजा गया था, जिन्होंने दिखाया कि अर्ली पार्सर में [[ गतिशील प्रोग्रामिंग ]] और स्टेट-सेट के उपयोग के समान [[सीवाईके एल्गोरिदम]] कसमी, घातीय समय जटिलता की समस्या को हल करने के लिए एक साधारण [[ बैक ट्रैकिंग ]] [[पुनरावर्ती वंश पार्सर]] को स्वचालित ज्ञापन शुरू करके उत्पन्न किया जा सकता है।<ref name="Norvig1991"/>नॉरविग के दृष्टिकोण में मूल विचार यह है कि जब एक पार्सर इनपुट पर लागू होता है, तो परिणाम बाद के पुन: उपयोग के लिए यादगार में संग्रहीत किया जाता है यदि उसी पार्सर को कभी भी उसी इनपुट पर दोबारा लागू किया जाता है। रिचर्ड फ्रॉस्ट ने [[पार्सर कॉम्बिनेटर]] की घातीय समय जटिलता को कम करने के लिए ज्ञापन का भी उपयोग किया, जिसे "विशुद्ध रूप से कार्यात्मक टॉप-डाउन बैकट्रैकिंग" पार्सिंग तकनीक के रूप में देखा जा सकता है।<ref name="Frost1996">{{cite journal |last1=Frost |first1=Richard |last2=Szydlowski |first2=Barbara |title=विशुद्ध रूप से कार्यात्मक टॉप-डाउन बैकट्रैकिंग भाषा प्रोसेसर को याद रखना|journal=Sci. Comput. Program. |year=1996 |volume=27 |issue=3 |pages=263–288 |doi=10.1016/0167-6423(96)00014-7 |doi-access=free }}</ref> उन्होंने दिखाया कि सीएफजी के निष्पादन योग्य विनिर्देशों के रूप में जटिल पार्सर बनाने के लिए बुनियादी मेमोइज्ड पार्सर कॉम्बिनेटर का उपयोग बिल्डिंग ब्लॉक के रूप में किया जा सकता है।<ref name="Frost1994">{{cite journal |last=Frost |first=Richard |title=गैर-नियतात्मक टॉप-डाउन पार्सर्स के विशुद्ध रूप से कार्यात्मक निष्पादन योग्य विनिर्देशों की बहुपद जटिलता प्राप्त करने के लिए मेमोइज़ेशन का उपयोग करना|journal=SIGPLAN Notices |year=1994 |volume=29 |issue=4 |pages=23–30 |doi=10.1145/181761.181764 |s2cid=10616505 }}</ref><ref name="Frost2003">{{cite book |last=Frost |first=Richard |year=2003 |chapter=Monadic Memoization towards Correctness-Preserving Reduction of Search |title=Canadian Conference on AI 2003 |series=Lecture Notes in Computer Science |volume=2671 |pages=66–80 |isbn=978-3-540-40300-5 |doi=10.1007/3-540-44886-1_8 }}</ref> 1995 में जॉनसन द्वारा पार्सिंग के संदर्भ में इसे फिर से खोजा गया | जब एक टॉप-डाउन [[ पदच्छेद ]] | टॉप-डाउन पार्सर एक अस्पष्ट संदर्भ-मुक्त व्याकरण (CFG) के संबंध में एक सिंटैक्टिक अस्पष्टता इनपुट को पार्स करने का प्रयास करता है, तो उसे चरणों की एक घातीय संख्या (इनपुट की लंबाई के संबंध में) की आवश्यकता हो सकती है सभी संभावित पार्स पेड़ बनाने के लिए सीएफजी के सभी विकल्पों का प्रयास करें। इसके लिए अंततः घातीय मेमोरी स्पेस की आवश्यकता होगी। 1991 में पीटर नॉरविग द्वारा मेमोइज़ेशन को एक पार्सिंग रणनीति के रूप में खोजा गया था, जिन्होंने दिखाया कि अर्ली पार्सर में [[ गतिशील प्रोग्रामिंग ]] और स्टेट-सेट के उपयोग के समान [[सीवाईके एल्गोरिदम]] कसमी, घातीय समय जटिलता की समस्या को हल करने के लिए एक साधारण [[ बैक ट्रैकिंग ]] [[पुनरावर्ती वंश पार्सर]] को स्वचालित ज्ञापन शुरू करके उत्पन्न किया जा सकता है।<ref name="Norvig1991"/>नॉरविग के दृष्टिकोण में मूल विचार यह है कि जब एक पार्सर इनपुट पर लागू होता है, तो परिणाम बाद के पुन: उपयोग के लिए यादगार में संग्रहीत किया जाता है यदि उसी पार्सर को कभी भी उसी इनपुट पर दोबारा लागू किया जाता है। रिचर्ड फ्रॉस्ट ने [[पार्सर कॉम्बिनेटर]] की घातीय समय जटिलता को कम करने के लिए ज्ञापन का भी उपयोग किया, जिसे "विशुद्ध रूप से कार्यात्मक टॉप-डाउन बैकट्रैकिंग" पार्सिंग तकनीक के रूप में देखा जा सकता है।<ref name="Frost1996">{{cite journal |last1=Frost |first1=Richard |last2=Szydlowski |first2=Barbara |title=विशुद्ध रूप से कार्यात्मक टॉप-डाउन बैकट्रैकिंग भाषा प्रोसेसर को याद रखना|journal=Sci. Comput. Program. |year=1996 |volume=27 |issue=3 |pages=263–288 |doi=10.1016/0167-6423(96)00014-7 |doi-access=free }}</ref> उन्होंने दिखाया कि सीएफजी के निष्पादन योग्य विनिर्देशों के रूप में जटिल पार्सर बनाने के लिए बुनियादी मेमोइज्ड पार्सर कॉम्बिनेटर का उपयोग बिल्डिंग ब्लॉक के रूप में किया जा सकता है।<ref name="Frost1994">{{cite journal |last=Frost |first=Richard |title=गैर-नियतात्मक टॉप-डाउन पार्सर्स के विशुद्ध रूप से कार्यात्मक निष्पादन योग्य विनिर्देशों की बहुपद जटिलता प्राप्त करने के लिए मेमोइज़ेशन का उपयोग करना|journal=SIGPLAN Notices |year=1994 |volume=29 |issue=4 |pages=23–30 |doi=10.1145/181761.181764 |s2cid=10616505 }}</ref><ref name="Frost2003">{{cite book |last=Frost |first=Richard |year=2003 |chapter=Monadic Memoization towards Correctness-Preserving Reduction of Search |title=Canadian Conference on AI 2003 |series=Lecture Notes in Computer Science |volume=2671 |pages=66–80 |isbn=978-3-540-40300-5 |doi=10.1007/3-540-44886-1_8 }}</ref> 1995 में जॉनसन द्वारा पार्सिंग के संदर्भ में इसे फिर से खोजा गया और डोरे।<ref name="Johnson1995">{{cite journal |last=Johnson |first=Mark |arxiv=cmp-lg/9504016 |title=टॉप-डाउन पार्सिंग का संस्मरण|journal=Computational Linguistics |volume=21 |issue=3 |pages=405–417 |year=1995 |bibcode=1995cmp.lg....4016J }}</ref><ref name="Johnson&Dorre">{{cite book |last1=Johnson |first1=Mark |last2=Dörre |first2=Jochen |name-list-style=amp |arxiv=cmp-lg/9504028 |chapter=Memoization of Coroutined Constraints |title=Proceedings of the 33rd Annual Meeting of the Association for Computational Linguistics |location=Cambridge, Massachusetts |year=1995 }}</ref> 2002 में, फोर्ड द्वारा [[पैकराट पार्सर]] नामक रूप में इसकी काफी गहराई से जांच की गई थी।<ref name="Ford2002">{{cite thesis |last=Ford |first=Bryan |title=Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking |type=Master’s thesis |publisher=Massachusetts Institute of Technology |year=2002 |hdl=1721.1/87310 }}</ref> | ||
2007 में, फ्रॉस्ट, हाफिज और कैलाघन{{citation needed|date=December 2017}} ने एक टॉप-डाउन पार्सिंग एल्गोरिदम का वर्णन किया है जो [[बहुपद]] समय (बिग ओ नोटेशन|Θ(n)<sup>4</sup>) बाएँ पुनरावर्तन के लिए | बाएँ-पुनरावर्ती व्याकरण और Θ(n<sup>3</sup>) गैर वाम-पुनरावर्ती व्याकरण के लिए)। उनके टॉप-डाउन पार्सिंग एल्गोरिदम को 'कॉम्पैक्ट प्रतिनिधित्व' और 'स्थानीय अस्पष्टता समूह' द्वारा संभावित घातीय अस्पष्ट पार्स पेड़ के लिए बहुपद स्थान की भी आवश्यकता होती है। उनका कॉम्पैक्ट प्रतिनिधित्व टॉमिटा के [[नीचे-ऊपर पार्सिंग]] के कॉम्पैक्ट प्रतिनिधित्व के साथ तुलनीय है।<ref name="Tomita1985">{{cite book |author-link=Masaru Tomita |last=Tomita |first=Masaru |title=प्राकृतिक भाषा के लिए कुशल पार्सिंग|publisher=Kluwer |location=Boston |year=1985 |isbn=0-89838-202-5 }}</ref> मेमोइज़ेशन का उनका उपयोग केवल पहले से गणना किए गए परिणामों को पुनर्प्राप्त करने तक ही सीमित नहीं है जब एक पार्सर को एक ही इनपुट स्थिति पर बार-बार लागू किया जाता है (जो बहुपद समय की आवश्यकता के लिए आवश्यक है); यह निम्नलिखित अतिरिक्त कार्यों को करने के लिए विशिष्ट है: | 2007 में, फ्रॉस्ट, हाफिज और कैलाघन{{citation needed|date=December 2017}} ने एक टॉप-डाउन पार्सिंग एल्गोरिदम का वर्णन किया है जो [[बहुपद]] समय (बिग ओ नोटेशन|Θ(n)<sup>4</sup>) बाएँ पुनरावर्तन के लिए | बाएँ-पुनरावर्ती व्याकरण और Θ(n<sup>3</sup>) गैर वाम-पुनरावर्ती व्याकरण के लिए)। उनके टॉप-डाउन पार्सिंग एल्गोरिदम को 'कॉम्पैक्ट प्रतिनिधित्व' और 'स्थानीय अस्पष्टता समूह' द्वारा संभावित घातीय अस्पष्ट पार्स पेड़ के लिए बहुपद स्थान की भी आवश्यकता होती है। उनका कॉम्पैक्ट प्रतिनिधित्व टॉमिटा के [[नीचे-ऊपर पार्सिंग]] के कॉम्पैक्ट प्रतिनिधित्व के साथ तुलनीय है।<ref name="Tomita1985">{{cite book |author-link=Masaru Tomita |last=Tomita |first=Masaru |title=प्राकृतिक भाषा के लिए कुशल पार्सिंग|publisher=Kluwer |location=Boston |year=1985 |isbn=0-89838-202-5 }}</ref> मेमोइज़ेशन का उनका उपयोग केवल पहले से गणना किए गए परिणामों को पुनर्प्राप्त करने तक ही सीमित नहीं है जब एक पार्सर को एक ही इनपुट स्थिति पर बार-बार लागू किया जाता है (जो बहुपद समय की आवश्यकता के लिए आवश्यक है); यह निम्नलिखित अतिरिक्त कार्यों को करने के लिए विशिष्ट है: | ||
* मेमोइज़ेशन प्रक्रिया (जिसे किसी भी पार्सर निष्पादन के आसपास 'रैपर' के रूप में देखा जा सकता है) इनपुट लंबाई और वर्तमान इनपुट स्थिति के संबंध में गहराई प्रतिबंध लगाकर एक निरंतर बढ़ते प्रत्यक्ष बाएं-पुनरावर्ती पार्स को समायोजित करती है। | * मेमोइज़ेशन प्रक्रिया (जिसे किसी भी पार्सर निष्पादन के आसपास 'रैपर' के रूप में देखा जा सकता है) इनपुट लंबाई और वर्तमान इनपुट स्थिति के संबंध में गहराई प्रतिबंध लगाकर एक निरंतर बढ़ते प्रत्यक्ष बाएं-पुनरावर्ती पार्स को समायोजित करती है। | ||
| Line 158: | Line 157: | ||
(नोटेशन नोट: उपरोक्त उदाहरण में, औपचारिक व्याकरण # व्याकरण का वाक्य विन्यास S → (A c) | (B d) पढ़ता है: एक ''S'' या तो एक 'A' है जिसके बाद a c या 'a' है 'बी'' के बाद एक डी। उत्पादन एक्स → एक्स [एक्स] एक 'एक्स' पढ़ता है एक एक्स एक वैकल्पिक 'एक्स' के बाद होता है।) | (नोटेशन नोट: उपरोक्त उदाहरण में, औपचारिक व्याकरण # व्याकरण का वाक्य विन्यास S → (A c) | (B d) पढ़ता है: एक ''S'' या तो एक 'A' है जिसके बाद a c या 'a' है 'बी'' के बाद एक डी। उत्पादन एक्स → एक्स [एक्स] एक 'एक्स' पढ़ता है एक एक्स एक वैकल्पिक 'एक्स' के बाद होता है।) | ||
यह व्याकरण [[स्ट्रिंग (कंप्यूटर विज्ञान)]] के निम्नलिखित तीन रूपों में से एक उत्पन्न करता है: ''xac'', ''xbc'', या ''xbd'' (जहाँ ''x'' का अर्थ यहाँ समझा जाता है ''एक या अधिक ''x''<nowiki>'</nowiki>s''।) इसके बाद, विचार करें कि पार्स विनिर्देश के रूप में उपयोग किया जाने वाला यह व्याकरण कैसे प्रभाव डाल सकता है | यह व्याकरण [[स्ट्रिंग (कंप्यूटर विज्ञान)]] के निम्नलिखित तीन रूपों में से एक उत्पन्न करता है: ''xac'', ''xbc'', या ''xbd'' (जहाँ ''x'' का अर्थ यहाँ समझा जाता है ''एक या अधिक ''x''<nowiki>'</nowiki>s''।) इसके बाद, विचार करें कि पार्स विनिर्देश के रूप में उपयोग किया जाने वाला यह व्याकरण कैसे प्रभाव डाल सकता है स्ट्रिंग xxxxxbd का एक टॉप-डाउन, बाएँ-दाएँ पार्स: | ||
: नियम ए xxxxxb को पहचान लेगा (पहले एक एक्स को पहचानने के लिए एक्स में उतरकर, और फिर से एक्स में तब तक उतरता है जब तक कि सभी x<nowiki>'</nowiki>s का उपभोग नहीं हो जाता है, और फिर बी को पहचानते हैं), और फिर वापस लौटें एस, और सी को पहचानने में विफल। S का अगला खंड तब B में उतरेगा, जो बदले में 'फिर से X में उतरता है' और x<nowiki>'</nowiki>s को कई रिकर्सिव कॉल के माध्यम से X को पहचानता है, और फिर ab, और S पर वापस लौटता है और अंत में एक डी को पहचानता है। | : नियम ए xxxxxb को पहचान लेगा (पहले एक एक्स को पहचानने के लिए एक्स में उतरकर, और फिर से एक्स में तब तक उतरता है जब तक कि सभी x<nowiki>'</nowiki>s का उपभोग नहीं हो जाता है, और फिर बी को पहचानते हैं), और फिर वापस लौटें एस, और सी को पहचानने में विफल। S का अगला खंड तब B में उतरेगा, जो बदले में 'फिर से X में उतरता है' और x<nowiki>'</nowiki>s को कई रिकर्सिव कॉल के माध्यम से X को पहचानता है, और फिर ab, और S पर वापस लौटता है और अंत में एक डी को पहचानता है। | ||
Revision as of 19:33, 16 June 2023
कम्प्यूटिंग में, मेमोइज़ेशन या मेमोइज़ेशन एक ऑप्टिमाइज़ेशन (कंप्यूटर विज्ञान) तकनीक है जो मुख्य रूप से महंगे सबरूटीन के परिणामों को संग्रहीत करके कंप्यूटर प्रोग्राम को गति देने के लिए उपयोग किया जाता है और जब वही इनपुट फिर से होता है तो कैश्ड परिणाम लौटाता है। मेमोइज़ेशन का उपयोग अन्य संदर्भों में भी किया गया है (और गति लाभ के अतिरिक्त अन्य उद्देश्यों के लिए), जैसे कि सरल पारस्परिक पुनरावर्तन अवतरण पार्सिंग में।[1] चूंकि कैश (कंप्यूटिंग) से संबंधित, मेमोइज़ेशन इस अनुकूलन के एक विशिष्ट स्थितियों को संदर्भित करता है, इसे बफर (कंप्यूटर विज्ञान) या पृष्ठ प्रतिस्थापन एल्गोरिदम जैसे कैशिंग के रूपों से अलग करता है। कुछ तर्क प्रोग्रामिंग लैंग्वेज के संदर्भ में मेमोइज़ेशन को प्रोलॉग टेबलिंग के रूप में भी जाना जाता है।[2]
व्युत्पत्ति
मेमोइज़ेशन शब्द 1968 में डोनाल्ड मिक्सी द्वारा गढ़ा गया था[3] और लैटिन शब्द ज्ञापन (याद रखने के लिए) से लिया गया है, जिसे सामान्यतः अमेरिकी अंग्रेजी में मेमो के रूप में छोटा किया जाता है, और इस प्रकार किसी फ़ंक्शन को [परिणामों] को याद रखने के लिए बदलने का अर्थ होता है। जबकि मेमोइज़ेशन को मेमोराइज़ेशन के साथ भ्रमित किया जा सकता है (क्योंकि वे व्युत्पत्ति संबंधी संज्ञानात्मक हैं), कंप्यूटिंग में मेमोइज़ेशन का एक विशेष अर्थ है।
सिंहावलोकन
एक मेमोइज्ड फ़ंक्शन विशिष्ट इनपुट के कुछ सेट से संबंधित परिणामों को याद रखता है। याद किए गए इनपुट के साथ बाद की कॉल याद किए गए परिणाम को पुनर्गणना करने के अतिरिक्त वापस कर देती है, इस प्रकार दिए गए मापदंडों के साथ कॉल की प्राथमिक लागत को समाप्त कर देती है, किन्तु उन मापदंडों के साथ फ़ंक्शन के लिए की गई पहली कॉल। फ़ंक्शन की प्रकृति और इसके उपयोग के आधार पर याद किए गए संघों का सेट एक प्रतिस्थापन कलन विधि या एक निश्चित सेट द्वारा नियंत्रित एक निश्चित आकार का सेट हो सकता है। किसी फ़ंक्शन को केवल तभी याद किया जा सकता है जब वह संदर्भात्मक पारदर्शिता हो; अर्थात्, केवल तभी जब फ़ंक्शन को कॉल करने का ठीक वैसा ही प्रभाव होता है जैसा कि उस फ़ंक्शन कॉल को उसके रिटर्न मान से बदलने पर होता है। (चूंकि , इस प्रतिबंध के लिए विशेष स्थितियों के अपवाद उपस्थित हैं।) तालिका देखो से संबंधित होने के अतिरिक्त , मेमोइज़ेशन अक्सर इसके कार्यान्वयन में ऐसी तालिकाओं का उपयोग करता है, मेमोइज़ेशन अपने परिणामों के कैश को पारदर्शी रूप से फ्लाई पर, आवश्यकतानुसार, अग्रिम रूप से पॉप्युलेट करता है।
मेमोइज़ेशन अंतरिक्ष लागत के बदले फ़ंक्शन की समय लागत को कम करने का एक विधि है; अर्थात्, स्मृति स्पेस के उच्च उपयोग के बदले मेमोइज्ड फ़ंक्शंस गति के लिए अनुकूलित हो जाते हैं। एल्गोरिदम के समय/स्थान लागत का कंप्यूटिंग में एक विशिष्ट नाम है: कम्प्यूटेशनल जटिलता सिद्धांत। सभी कार्यों में समय में एक कम्प्यूटेशनल जटिलता होती है (अर्थात उन्हें निष्पादित करने में समय लगता है) और अंतरिक्ष में।
चूंकि एक स्पेस-टाइम ट्रेडऑफ़ होता है (यानी, इस्तेमाल किया गया स्थान गति प्राप्त होता है), यह कुछ अन्य अनुकूलन से अलग होता है जिसमें टाइम-स्पेस ट्रेड-ऑफ़ सम्मलित होता है, जैसे कि ताकत में कमी, उस मेमोइज़ेशन में एक रन टाइम (प्रोग्राम जीवनचक्र चरण) होता है| संकलन-समय अनुकूलन के अतिरिक्त रन-टाइम। इसके अतिरिक्त , शक्ति में कमी संभावित रूप से एक महंगे ऑपरेशन को बदल देती है जैसे कि कम खर्चीले ऑपरेशन जैसे कि जोड़, और बचत में परिणाम अत्यधिक मशीन-निर्भर (मशीनों में गैर-पोर्टेबल) हो सकते हैं, जबकि मेमोइज़ेशन एक अधिक मशीन-स्वतंत्र, क्रॉस है -मंच की रणनीति।
N के भाज्य की गणना करने के लिए निम्नलिखित स्यूडोकोड फ़ंक्शन पर विचार करें:
फ़ंक्शन कारख़ाने का (एन एक गैर-ऋणात्मक पूर्णांक है) अगर एन 0 है तो वापसी 1 [सम्मेलन द्वारा कि '0! = 1'] अन्य वापसी फैक्टोरियल (एन - 1) गुना एन [पुनरावर्ती रूप से फैक्टोरियल का आह्वान करें पैरामीटर 1 n से कम के साथ] अगर अंत अंत फ़ंक्शन
प्रत्येक पूर्णांक n के लिए ऐसा है कि n ≥ 0, फ़ंक्शन का अंतिम परिणाम factorial अपरिवर्तनीय (कंप्यूटर विज्ञान) है; अगर के रूप में आह्वान किया x = factorial(3), परिणाम ऐसा है कि x को हमेशा मान 6 असाइन किया जाएगा। उपरोक्त गैर-ज्ञात कार्यान्वयन, सम्मलित प्रत्यावर्तन एल्गोरिदम की प्रकृति को देखते हुए, एन + 1 आमंत्रण की आवश्यकता होगी factorial एक परिणाम पर पहुंचने के लिए, और इनमें से प्रत्येक आमंत्रण, बदले में, गणना किए गए मान को वापस करने के लिए कार्य करने में लगने वाले समय में संबद्ध लागत होती है। मशीन के आधार पर, यह लागत निम्न का योग हो सकती है:
- कार्यात्मक कॉल स्टैक फ्रेम स्थापित करने की लागत।
- n से 0 की तुलना करने की लागत।
- n से 1 घटाने की लागत।
- रिकर्सिव कॉल स्टैक फ्रेम सेट अप करने की लागत। (ऊपरोक्त अनुसार।)
- पुनरावर्ती कॉल के परिणाम को गुणा करने की लागत
factorialएन द्वारा। - रिटर्न रिजल्ट को स्टोर करने की लागत ताकि इसे कॉलिंग कॉन्टेक्स्ट द्वारा इस्तेमाल किया जा सके।
एक गैर-ज्ञात कार्यान्वयन में, प्रत्येक शीर्ष-स्तरीय कॉल to factorial चरण 2 से 6 तक की संचयी लागत n के प्रारंभिक मूल्य के अनुपात में सम्मलित है।
का एक यादगार संस्करण factorial फ़ंक्शन इस प्रकार है:
फ़ंक्शन फैक्टोरियल (एन एक गैर-ऋणात्मक पूर्णांक है)
अगर एन 0 है तो
वापसी 1 [सम्मेलन द्वारा कि '0! = 1']
और अगर n लुकअप-टेबल में है तो
रिटर्न लुकअप-टेबल-वैल्यू-फॉर-एन
अन्य
मान लीजिए x = फैक्टोरियल (n – 1) गुणा n [रिकर्सिवली इनवोक फैक्टोरियल
पैरामीटर 1 n से कम के साथ]
n में लुकअप-टेबल में x स्टोर करेंवां स्लॉट [n! का परिणाम याद रखें! बाद के लिए]
वापसी एक्स
अगर अंत
अंत फ़ंक्शन
इस विशेष उदाहरण में, यदि factorial पहले 5 के साथ लागू किया जाता है, और फिर बाद में पांच से कम या उसके बराबर किसी भी मूल्य के साथ लागू किया जाता है, उन वापसी मूल्यों को भी याद किया जाएगा, क्योंकि factorial 5, 4, 3, 2, 1, और 0 के मानों के साथ पुनरावर्ती रूप से बुलाया जाएगा, और उनमें से प्रत्येक के लिए वापसी मान संग्रहीत किए जाएंगे। यदि इसे 5 से बड़ी संख्या के साथ कॉल किया जाता है, जैसे 7, केवल 2 पुनरावर्ती कॉल किए जाएंगे (7 और 6), और 5 के लिए मान! पिछले कॉल से संग्रहीत किया जाएगा। इस तरह, संस्मरण एक फ़ंक्शन को अधिक समय-कुशल बनने की अनुमति देता है, जितनी बार इसे कहा जाता है, इस प्रकार अंततः समग्र गति-अप होता है।
कुछ अन्य विचार
कार्यात्मक प्रोग्रामिंग
कार्यात्मक प्रोग्रामिंग भाषाओं के लिए संकलक में मेमोइज़ेशन का अत्यधिक उपयोग किया जाता है, जो अक्सर नाम मूल्यांकन रणनीति द्वारा कॉल का उपयोग करते हैं। तर्क मूल्यों की गणना के साथ ओवरहेड से बचने के लिए, इन भाषाओं के संकलक तर्क मूल्यों की गणना करने के लिए थंक नामक सहायक कार्यों का भारी उपयोग करते हैं, और बार-बार होने वाली गणनाओं से बचने के लिए इन कार्यों को याद करते हैं।
स्वचालित संस्मरण
जबकि मेमोइज़ेशन को कंप्यूटर प्रोग्रामर द्वारा आंतरिक रूप से और स्पष्ट रूप से फ़ंक्शंस में जोड़ा जा सकता है, उसी तरह उपरोक्त मेमोइज़्ड संस्करण factorial लागू किया गया है, संदर्भित रूप से पारदर्शी कार्यों को स्वचालित रूप से बाह्य रूप से याद किया जा सकता है।[1]पीटर नॉरविग द्वारा नियोजित तकनीकों का न केवल सामान्य लिस्प (जिस भाषा में उनके पेपर ने स्वचालित मेमोइज़ेशन प्रदर्शित किया था) में, बल्कि विभिन्न अन्य प्रोग्रामिंग भाषाओं में भी आवेदन किया है। शब्द पुनर्लेखन के अध्ययन में स्वचालित संस्मरण के अनुप्रयोगों का भी औपचारिक रूप से पता लगाया गया है[4] और कृत्रिम बुद्धि।[5]
प्रोग्रामिंग भाषाओं में जहां कार्य प्रथम श्रेणी की वस्तुएं हैं (जैसे लुआ (प्रोग्रामिंग भाषा), पायथन (प्रोग्रामिंग भाषा), या पर्ल[6]), पैरामीटर के दिए गए सेट के लिए मान की गणना करने के बाद स्वचालित मेमोइज़ेशन को (रन-टाइम पर) फ़ंक्शन को इसकी गणना मूल्य के साथ कार्यान्वित किया जा सकता है। फ़ंक्शन जो इस वैल्यू-फॉर-फ़ंक्शन-ऑब्जेक्ट प्रतिस्थापन को करता है, सामान्य रूप से किसी भी संदर्भित पारदर्शी फ़ंक्शन को लपेट सकता है। निम्नलिखित स्यूडोकोड पर विचार करें (जहां यह माना जाता है कि कार्य प्रथम श्रेणी के मान हैं):
फ़ंक्शन मेमोइज्ड-कॉल (एफ फ़ंक्शन ऑब्जेक्ट पैरामीटर है)
यदि F के पास कोई संलग्न सरणी मान नहीं है
मान नामक एक साहचर्य सरणी आवंटित करें;
एफ को मान संलग्न करें;
अगर अंत;
अगर F.values[arguments] तब खाली है
F. मान [तर्क] = F (तर्क);
अगर अंत;
वापसी F.values [तर्क];
अंत फ़ंक्शन
स्वचालित रूप से याद किए गए संस्करण को कॉल करने के लिए factorial कॉल करने के अतिरिक्त उपरोक्त रणनीति का उपयोग करना factorial सीधे, कोड आमंत्रित करता है memoized-call(factorial(n)). इस तरह की प्रत्येक कॉल पहले यह देखने के लिए जांच करती है कि क्या परिणामों को संग्रहीत करने के लिए एक धारक सरणी आवंटित की गई है, और यदि नहीं, तो वह सरणी संलग्न करती है। यदि स्थिति पर कोई प्रविष्टि उपस्थित नहीं है values[arguments] (कहाँ arguments साहचर्य सरणी की कुंजी के रूप में उपयोग किया जाता है), एक वास्तविक कॉल किया जाता है factorial प्रदान किए गए तर्कों के साथ। अंत में, कुंजी स्थिति में सरणी में प्रविष्टि कॉलर को वापस कर दी जाती है।
उपरोक्त रणनीति के लिए प्रत्येक कॉल पर एक फ़ंक्शन के लिए स्पष्ट रैपिंग की आवश्यकता होती है जिसे याद किया जाना है। उन भाषाओं में जो क्लोजर (कंप्यूटर विज्ञान) की अनुमति देते हैं, मेमोइज़ेशन को फ़ंक्शन वस्तु फ़ैक्टरी के माध्यम से स्पष्ट रूप से प्रभावित किया जा सकता है जो एक डेकोरेटर पैटर्न में लिपटे मेमोइज़्ड फ़ंक्शन ऑब्जेक्ट को लौटाता है। स्यूडोकोड में, इसे इस प्रकार व्यक्त किया जा सकता है:
फ़ंक्शन कंस्ट्रक्शन-मेमोइज़्ड-फ़ंक्टर (F एक फ़ंक्शन ऑब्जेक्ट पैरामीटर है)
memoized-version नामक फ़ंक्शन ऑब्जेक्ट आवंटित करें;
मेमोइज्ड-वर्जन (तर्क) होने दें
यदि स्वयं के पास कोई संलग्न सरणी मान नहीं है तो ['स्वयं' इस (कंप्यूटर विज्ञान) वस्तु का एक संदर्भ है]
मान नामक एक साहचर्य सरणी आवंटित करें;
स्वयं को मूल्य संलग्न करें;
अगर अंत;
अगर self.values[arguments] तब खाली है
स्व। मूल्य [तर्क] = एफ (तर्क);
अगर अंत;
वापसी स्व। मान [तर्क];
अंत चलो;
संस्मरण-संस्करण लौटाएं;
अंत फ़ंक्शन
कॉल करने के अतिरिक्त factorial, एक नया फ़ंक्शन ऑब्जेक्ट memfact निम्नानुसार बनाया गया है:
memfact = निर्माण-ज्ञापन-फ़ंक्टर (फैक्टोरियल)
उपरोक्त उदाहरण मानता है कि function factorial को कॉल करने से पहले ही परिभाषित कर दिया गया है construct-memoized-functor से बना। इस बिंदु से आगे, memfact(n) जब कभी n का क्रमगुणन वांछित होता है तब उसे कॉल किया जाता है। लुआ जैसी भाषाओं में, अधिक परिष्कृत तकनीकें उपस्थित हैं जो एक फ़ंक्शन को उसी नाम से एक नए फ़ंक्शन द्वारा प्रतिस्थापित करने की अनुमति देती हैं, जो अनुमति देगा:
फैक्टोरियल = कंस्ट्रक्शन-मेमोइज्ड-फंक्टर (फैक्टोरियल)
अनिवार्य रूप से, इस तरह की तकनीकों में मूल फ़ंक्शन ऑब्जेक्ट को बनाए गए फ़ंक्टर को संलग्न करना और कॉल को अग्रेषित करना मूल फ़ंक्शन को उपनाम के माध्यम से याद किया जाता है जब वास्तविक फ़ंक्शन के लिए कॉल की आवश्यकता होती है (अंतहीन पुनरावर्तन से बचने के लिए), जैसा कि नीचे दिखाया गया है:
फ़ंक्शन कंस्ट्रक्शन-मेमोइज़्ड-फ़ंक्टर (F एक फ़ंक्शन ऑब्जेक्ट पैरामीटर है)
memoized-version नामक फ़ंक्शन ऑब्जेक्ट आवंटित करें;
मेमोइज्ड-वर्जन (तर्क) होने दें
यदि स्वयं के पास कोई संलग्न सरणी मान नहीं है तो ['स्वयं' इस वस्तु का संदर्भ है]
मान नामक एक साहचर्य सरणी आवंटित करें;
स्वयं को मूल्य संलग्न करें;
उपनाम नामक एक नया फ़ंक्शन ऑब्जेक्ट आवंटित करें;
स्वयं को उपनाम संलग्न करें; [बाद में अप्रत्यक्ष रूप से 'एफ' का आह्वान करने की क्षमता के लिए]
स्वयं उपनाम = एफ;
अगर अंत;
अगर self.values[arguments] तब खाली है
स्व.मूल्य [तर्क] = स्व.उपनाम (तर्क); ['एफ' को सीधी कॉल नहीं']
अगर अंत;
वापसी स्व। मान [तर्क];
अंत चलो;
संस्मरण-संस्करण लौटाएं;
अंत फ़ंक्शन
(नोट: ऊपर दिखाए गए कुछ चरणों को कार्यान्वयन भाषा द्वारा अप्रत्यक्ष रूप से प्रबंधित किया जा सकता है और उदाहरण के लिए प्रदान किया गया है।)
पार्सर्स
जब एक टॉप-डाउन पदच्छेद | टॉप-डाउन पार्सर एक अस्पष्ट संदर्भ-मुक्त व्याकरण (CFG) के संबंध में एक सिंटैक्टिक अस्पष्टता इनपुट को पार्स करने का प्रयास करता है, तो उसे चरणों की एक घातीय संख्या (इनपुट की लंबाई के संबंध में) की आवश्यकता हो सकती है सभी संभावित पार्स पेड़ बनाने के लिए सीएफजी के सभी विकल्पों का प्रयास करें। इसके लिए अंततः घातीय मेमोरी स्पेस की आवश्यकता होगी। 1991 में पीटर नॉरविग द्वारा मेमोइज़ेशन को एक पार्सिंग रणनीति के रूप में खोजा गया था, जिन्होंने दिखाया कि अर्ली पार्सर में गतिशील प्रोग्रामिंग और स्टेट-सेट के उपयोग के समान सीवाईके एल्गोरिदम कसमी, घातीय समय जटिलता की समस्या को हल करने के लिए एक साधारण बैक ट्रैकिंग पुनरावर्ती वंश पार्सर को स्वचालित ज्ञापन शुरू करके उत्पन्न किया जा सकता है।[1]नॉरविग के दृष्टिकोण में मूल विचार यह है कि जब एक पार्सर इनपुट पर लागू होता है, तो परिणाम बाद के पुन: उपयोग के लिए यादगार में संग्रहीत किया जाता है यदि उसी पार्सर को कभी भी उसी इनपुट पर दोबारा लागू किया जाता है। रिचर्ड फ्रॉस्ट ने पार्सर कॉम्बिनेटर की घातीय समय जटिलता को कम करने के लिए ज्ञापन का भी उपयोग किया, जिसे "विशुद्ध रूप से कार्यात्मक टॉप-डाउन बैकट्रैकिंग" पार्सिंग तकनीक के रूप में देखा जा सकता है।[7] उन्होंने दिखाया कि सीएफजी के निष्पादन योग्य विनिर्देशों के रूप में जटिल पार्सर बनाने के लिए बुनियादी मेमोइज्ड पार्सर कॉम्बिनेटर का उपयोग बिल्डिंग ब्लॉक के रूप में किया जा सकता है।[8][9] 1995 में जॉनसन द्वारा पार्सिंग के संदर्भ में इसे फिर से खोजा गया और डोरे।[10][11] 2002 में, फोर्ड द्वारा पैकराट पार्सर नामक रूप में इसकी काफी गहराई से जांच की गई थी।[12] 2007 में, फ्रॉस्ट, हाफिज और कैलाघन[citation needed] ने एक टॉप-डाउन पार्सिंग एल्गोरिदम का वर्णन किया है जो बहुपद समय (बिग ओ नोटेशन|Θ(n)4) बाएँ पुनरावर्तन के लिए | बाएँ-पुनरावर्ती व्याकरण और Θ(n3) गैर वाम-पुनरावर्ती व्याकरण के लिए)। उनके टॉप-डाउन पार्सिंग एल्गोरिदम को 'कॉम्पैक्ट प्रतिनिधित्व' और 'स्थानीय अस्पष्टता समूह' द्वारा संभावित घातीय अस्पष्ट पार्स पेड़ के लिए बहुपद स्थान की भी आवश्यकता होती है। उनका कॉम्पैक्ट प्रतिनिधित्व टॉमिटा के नीचे-ऊपर पार्सिंग के कॉम्पैक्ट प्रतिनिधित्व के साथ तुलनीय है।[13] मेमोइज़ेशन का उनका उपयोग केवल पहले से गणना किए गए परिणामों को पुनर्प्राप्त करने तक ही सीमित नहीं है जब एक पार्सर को एक ही इनपुट स्थिति पर बार-बार लागू किया जाता है (जो बहुपद समय की आवश्यकता के लिए आवश्यक है); यह निम्नलिखित अतिरिक्त कार्यों को करने के लिए विशिष्ट है:
- मेमोइज़ेशन प्रक्रिया (जिसे किसी भी पार्सर निष्पादन के आसपास 'रैपर' के रूप में देखा जा सकता है) इनपुट लंबाई और वर्तमान इनपुट स्थिति के संबंध में गहराई प्रतिबंध लगाकर एक निरंतर बढ़ते प्रत्यक्ष बाएं-पुनरावर्ती पार्स को समायोजित करती है।
- एल्गोरिदम की मेमो-टेबल 'लुकअप' प्रक्रिया सहेजे गए परिणाम के कम्प्यूटेशनल संदर्भ की पार्सर के वर्तमान संदर्भ के साथ तुलना करके सहेजे गए परिणाम की पुन: प्रयोज्यता को भी निर्धारित करती है। यह प्रासंगिक तुलना अप्रत्यक्ष (या छिपी हुई) वाम-पुनरावृत्ति को समायोजित करने की कुंजी है।
- एक मेमोटेबल में एक सफल लुकअप करते समय, पूर्ण परिणाम-सेट वापस करने के अतिरिक्त , प्रक्रिया केवल वास्तविक परिणाम के संदर्भों को वापस करती है और अंततः समग्र गणना को गति देती है।
- मेमोटेबल को अपडेट करने के दौरान, मेमोइज़ेशन प्रक्रिया समूह (संभावित रूप से घातीय) अस्पष्ट परिणाम देती है और बहुपद स्थान की आवश्यकता को सुनिश्चित करती है।
फ्रॉस्ट, हाफिज और कैलाघन ने भी PADL'08 में एल्गोरिथम के कार्यान्वयन का वर्णन किया[citation needed] हास्केल (प्रोग्रामिंग भाषा) में उच्च-क्रम के कार्यों (पार्सर कॉम्बिनेटर कहा जाता है) के एक सेट के रूप में, जो भाषा प्रोसेसर के रूप में सीएफजी के सीधे निष्पादन योग्य विनिर्देशों के निर्माण को सक्षम बनाता है। टॉप-डाउन पार्सिंग के साथ 'अस्पष्ट सीएफजी के किसी भी रूप' को समायोजित करने के लिए उनके बहुपद एल्गोरिदम की शक्ति का महत्व प्राकृतिक भाषा प्रसंस्करण के दौरान वाक्यविन्यास और शब्दार्थ विश्लेषण के संबंध में महत्वपूर्ण है। X-SAIGA साइट में एल्गोरिथम और कार्यान्वयन विवरण के बारे में अधिक जानकारी है।
जबकि नॉरविग ने मेमोइज़ेशन के माध्यम से पार्सर की शक्ति में वृद्धि की, संवर्धित पार्सर अभी भी अर्ली के एल्गोरिथ्म के रूप में जटिल था, जो गति अनुकूलन के अतिरिक्त किसी अन्य चीज़ के लिए मेमोइज़ेशन के उपयोग के स्थितियों को प्रदर्शित करता है। जॉनसन और डोरे[11]मेमोइज़ेशन के ऐसे अन्य गैर-गति संबंधी अनुप्रयोग को प्रदर्शित करता है: भाषाई बाधाओं के समाधान में विलंब करने के लिए मेमोइज़ेशन का उपयोग एक पार्स में एक बिंदु पर जहां उन बाधाओं को हल करने के लिए पर्याप्त जानकारी जमा की गई है। इसके विपरीत, मेमोइज़ेशन के स्पीड ऑप्टिमाइज़ेशन एप्लिकेशन में, फोर्ड ने प्रदर्शित किया कि मेमोइज़ेशन गारंटी दे सकता है कि पार्सिंग अभिव्यक्ति व्याकरण बिग ओ नोटेशन समय में पार्स कर सकते हैं, यहां तक कि उन औपचारिक भाषाओं में भी जो सबसे खराब स्थिति वाले बैकट्रैकिंग व्यवहार का परिणाम हैं।[12]
निम्नलिखित औपचारिक व्याकरण पर विचार करें:
एस → (ए सी) | (बी डी) ए → एक्स (ए | बी) बी → एक्स बी एक्स → एक्स [एक्स]
(नोटेशन नोट: उपरोक्त उदाहरण में, औपचारिक व्याकरण # व्याकरण का वाक्य विन्यास S → (A c) | (B d) पढ़ता है: एक S या तो एक 'A' है जिसके बाद a c या 'a' है 'बी के बाद एक डी। उत्पादन एक्स → एक्स [एक्स] एक 'एक्स' पढ़ता है एक एक्स एक वैकल्पिक 'एक्स' के बाद होता है।)
यह व्याकरण स्ट्रिंग (कंप्यूटर विज्ञान) के निम्नलिखित तीन रूपों में से एक उत्पन्न करता है: xac, xbc, या xbd (जहाँ x का अर्थ यहाँ समझा जाता है एक या अधिक x's।) इसके बाद, विचार करें कि पार्स विनिर्देश के रूप में उपयोग किया जाने वाला यह व्याकरण कैसे प्रभाव डाल सकता है स्ट्रिंग xxxxxbd का एक टॉप-डाउन, बाएँ-दाएँ पार्स:
- नियम ए xxxxxb को पहचान लेगा (पहले एक एक्स को पहचानने के लिए एक्स में उतरकर, और फिर से एक्स में तब तक उतरता है जब तक कि सभी x's का उपभोग नहीं हो जाता है, और फिर बी को पहचानते हैं), और फिर वापस लौटें एस, और सी को पहचानने में विफल। S का अगला खंड तब B में उतरेगा, जो बदले में 'फिर से X में उतरता है' और x's को कई रिकर्सिव कॉल के माध्यम से X को पहचानता है, और फिर ab, और S पर वापस लौटता है और अंत में एक डी को पहचानता है।
यहाँ मुख्य अवधारणा 'फिर से एक्स में उतरती है' वाक्यांश में निहित है। आगे देखने, विफल होने, बैक अप लेने और फिर अगले विकल्प को पुनः प्रयास करने की प्रक्रिया को बैकट्रैकिंग के रूप में पार्सिंग में जाना जाता है, और यह मुख्य रूप से बैकट्रैकिंग है जो पार्सिंग में संस्मरण के अवसर प्रस्तुत करता है। एक फ़ंक्शन पर विचार करें RuleAcceptsSomeInput(Rule, Position, Input), जहां पैरामीटर इस प्रकार हैं:
Ruleविचाराधीन नियम का नाम है।Positionइनपुट में वर्तमान में ऑफ़सेट विचाराधीन है।Inputइनपुट विचाराधीन है।
फ़ंक्शन का वापसी मान दें RuleAcceptsSomeInput द्वारा स्वीकार किए गए इनपुट की लंबाई हो Rule, या 0 यदि वह नियम स्ट्रिंग में उस ऑफ़सेट पर कोई इनपुट स्वीकार नहीं करता है। इस तरह के मेमोइज़ेशन के साथ बैकट्रैकिंग परिदृश्य में, पार्सिंग प्रक्रिया इस प्रकार है:
- जब नियम A ऑफसेट 0 पर X में उतरता है, तो यह उस स्थिति और नियम X के विरुद्ध लंबाई 5 को याद करता है। मेमोइज़ेशन इंजन, और 5 की लंबाई लौटा दी जाती है, इस प्रकार वास्तव में एक्स में फिर से उतरने की बचत होती है, और यह इस तरह चलता रहता है जैसे कि यह पहले की तरह कई बार एक्स में उतरा हो।
उपरोक्त उदाहरण में, एक्स में एक या कई अवरोही हो सकते हैं, जैसे कि xxxxxxxxxxxxxxxxbd के लिए अनुमति देते हैं। वास्तव में, b से पहले x's की कितनी भी संख्या हो सकती है। जबकि S को कॉल बार-बार X में उतनी ही बार उतरनी चाहिए जितनी बार x's हैं, B को कभी भी X में उतरना नहीं पड़ेगा, क्योंकि का वापसी मान RuleAcceptsSomeInput(X, 0, xxxxxxxxxxxxxxxxbd) 16 होगा (इस विशेष स्थितियों में)।
वे पार्सर जो सिंटैक्टिक विधेय का उपयोग करते हैं, वे विधेय पार्स के परिणामों को भी याद रखने में सक्षम होते हैं, जिससे इस तरह के निर्माण को कम किया जा सकता है:
एस → (ए)? ए ए → /* कुछ नियम */
ए में एक वंश के लिए।
यदि कोई पार्सर एक पार्स के दौरान एक पार्स ट्री बनाता है, तो उसे न केवल उस इनपुट की लंबाई को याद रखना चाहिए जो किसी दिए गए नियम के विरुद्ध कुछ ऑफ़सेट पर मेल खाता है, बल्कि उस उप-ट्री को भी स्टोर करना चाहिए जो उस ऑफ़सेट में उस नियम द्वारा उत्पन्न होता है। इनपुट, क्योंकि पार्सर द्वारा नियम के बाद की कॉल वास्तव में उस पेड़ से नहीं उतरेंगी और उसका पुनर्निर्माण नहीं करेंगी। इसी कारण से, मेमोइज्ड पार्सर एल्गोरिदम जो बाहरी कोड (कभी-कभी सिमेंटिक एक्शन रूटीन कहा जाता है) को कॉल उत्पन्न करते हैं, जब एक नियम मिलान को यह सुनिश्चित करने के लिए कुछ योजना का उपयोग करना चाहिए कि ऐसे नियमों को अनुमानित क्रम में लागू किया जाता है।
चूंकि, किसी दिए गए बैकट्रैकिंग या सिंटैक्टिक विधेय सक्षम पार्सर के लिए प्रत्येक व्याकरण को बैकट्रैकिंग या विधेय चेक की आवश्यकता नहीं होगी, इनपुट में प्रत्येक ऑफ़सेट के खिलाफ प्रत्येक नियम के पार्स परिणामों को संग्रहीत करने का ओवरहेड (और पार्सिंग प्रक्रिया को अंतर्निहित रूप से करता है तो पार्स पेड़ को संग्रहित करना) हो सकता है वास्तव में एक पार्सर धीमा करें। इस प्रभाव को उन नियमों के स्पष्ट चयन से कम किया जा सकता है जिन्हें पार्सर याद रखेगा।[14]
यह भी देखें
- अनुमानित कंप्यूटिंग - दक्षता में सुधार के लिए तकनीकों की श्रेणी
- कम्प्यूटेशनल जटिलता सिद्धांत - एल्गोरिथम जटिलता पर अधिक जानकारी
- निदेशक स्ट्रिंग - भावों में तेजी से मुक्त चर का पता लगाना
- फ्लाईवेट पैटर्न - एक ऑब्जेक्ट प्रोग्रामिंग डिज़ाइन पैटर्न (कंप्यूटर साइंस), जो एक तरह के मेमोइज़ेशन का भी उपयोग करता है
- हैशलाइफ - सेल्यूलर आटोमेटा की गणना को गति देने के लिए एक यादगार तकनीक
- आलसी मूल्यांकन - मेमोइज़ेशन के साथ कुछ अवधारणाओं को साझा करता है
- भौतिक दृश्य - डेटाबेस प्रश्नों में समान कैशिंग
- आंशिक मूल्यांकन - स्वचालित प्रोग्राम अनुकूलन के लिए एक संबंधित तकनीक
संदर्भ
- ↑ 1.0 1.1 1.2 Norvig, Peter (1991). "प्रसंग-मुक्त पार्सिंग के अनुप्रयोगों के साथ स्वचालित संस्मरण की तकनीकें". Computational Linguistics. 17 (1): 91–98.
- ↑ Warren, David. "टेबलिंग और डेटालॉग प्रोग्रामिंग". Retrieved 29 May 2009.
- ↑ Michie, Donald (1968). "'मेमो' कार्य और मशीन लर्निंग" (PDF). Nature. 218 (5136): 19–22. Bibcode:1968Natur.218...19M. doi:10.1038/218019a0. S2CID 4265138.
- ↑ Hoffman, Berthold (1992). "Term Rewriting with Sharing and Memoïzation". In Kirchner, H.; Levi, G. (eds.). Algebraic and Logic Programming: Third International Conference, Proceedings, Volterra, Italy, 2–4 September 1992. Lecture Notes in Computer Science. Vol. 632. Berlin: Springer. pp. 128–142. doi:10.1007/BFb0013824. ISBN 978-3-540-55873-6.
- ↑ Mayfield, James; et al. (1995). "Using Automatic Memoization as a Software Engineering Tool in Real-World AI Systems" (PDF). Proceedings of the Eleventh IEEE Conference on Artificial Intelligence for Applications (CAIA '95). pp. 87–93. doi:10.1109/CAIA.1995.378786. hdl:11603/12722. ISBN 0-8186-7070-3. S2CID 8963326.
- ↑ "Bricolage: Memoization".
- ↑ Frost, Richard; Szydlowski, Barbara (1996). "विशुद्ध रूप से कार्यात्मक टॉप-डाउन बैकट्रैकिंग भाषा प्रोसेसर को याद रखना". Sci. Comput. Program. 27 (3): 263–288. doi:10.1016/0167-6423(96)00014-7.
- ↑ Frost, Richard (1994). "गैर-नियतात्मक टॉप-डाउन पार्सर्स के विशुद्ध रूप से कार्यात्मक निष्पादन योग्य विनिर्देशों की बहुपद जटिलता प्राप्त करने के लिए मेमोइज़ेशन का उपयोग करना". SIGPLAN Notices. 29 (4): 23–30. doi:10.1145/181761.181764. S2CID 10616505.
- ↑ Frost, Richard (2003). "Monadic Memoization towards Correctness-Preserving Reduction of Search". Canadian Conference on AI 2003. Lecture Notes in Computer Science. Vol. 2671. pp. 66–80. doi:10.1007/3-540-44886-1_8. ISBN 978-3-540-40300-5.
- ↑ Johnson, Mark (1995). "टॉप-डाउन पार्सिंग का संस्मरण". Computational Linguistics. 21 (3): 405–417. arXiv:cmp-lg/9504016. Bibcode:1995cmp.lg....4016J.
- ↑ 11.0 11.1 Johnson, Mark & Dörre, Jochen (1995). "Memoization of Coroutined Constraints". Proceedings of the 33rd Annual Meeting of the Association for Computational Linguistics. Cambridge, Massachusetts. arXiv:cmp-lg/9504028.
{{cite book}}: CS1 maint: location missing publisher (link) - ↑ 12.0 12.1 Ford, Bryan (2002). Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking (Master’s thesis). Massachusetts Institute of Technology. hdl:1721.1/87310.
- ↑ Tomita, Masaru (1985). प्राकृतिक भाषा के लिए कुशल पार्सिंग. Boston: Kluwer. ISBN 0-89838-202-5.
- ↑ Acar, Umut A.; et al. (2003). "Selective Memoization". Proceedings of the 30th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 15–17 January 2003. pp. 14–25. arXiv:1106.0447. doi:10.1145/640128.604133.
{{cite book}}:|journal=ignored (help)CS1 maint: location missing publisher (link)
बाहरी संबंध
- Examples of memoization in various programming languages
- groovy.lang.Closure#memoize() – Memoize is an Apache Groovy 1.8 language feature.
- Memoize – Memoize is a small library, written by Tim Bradshaw, for performing memoization in Common Lisp.
- IncPy – A custom Python interpreter that performs automatic memoization (with no required user annotations)
- Dave Herman's Macros for defining memoized procedures in Racket.
- Memoize.pm – a Perl module that implements memoized functions.
- Java memoization – an example in Java using dynamic proxy classes to create a generic memoization pattern.
- memoization.java - A Java memoization library.
- C++Memo[permanent dead link] – A C++ memoization framework.
- C-Memo – Generic memoization library for C, implemented using pre-processor function wrapper macros.
- Tek271 Memoizer – Open source Java memoizer using annotations and pluggable cache implementations.
- memoizable – A Ruby gem that implements memoized methods.
- Python memoization – A Python example of memoization.
- OCaml memoization – Implemented as a Camlp4 syntax extension.
- Memoization in Lua – Two example implementations of a general memoize function in Lua.
- Memoization in Mathematica – Memoization and limited memoization in Mathematica.
- Memoization in Javascript – Extending the Function prototype in JavaScript ( archived version of http://talideon.com/weblog/2005/07/javascript-memoization.cfm ).
- Memoization in Javascript – Examples of memoization in javascript using own caching mechanism and using the YUI library
- X-SAIGA – eXecutable SpecificAtIons of GrAmmars. Contains publications related to top-down parsing algorithm that supports left-recursion and ambiguity in polynomial time and space.
- Memoization in Scheme – A Scheme example of memoization on a class webpage.
- Memoization in Combinatory Logic – A web service to reduce Combinatory Logic while memoizing every step in a database.
- MbCache – Cache method results in .NET.
