मेमोइजेशन

Not to be confused with मेमोइजेशन.

"सारणी" redirects here. For संसदीय प्रक्रिया, see तालिका (संसदीय प्रक्रिया).

कम्प्यूटिंग में, मेमोइज़ेशन या मेमोइज़ेशन एक ऑप्टिमाइज़ेशन (कंप्यूटर विज्ञान) तकनीक है जो मुख्य रूप से महंगे सबरूटीन के परिणामों को संग्रहीत करके कंप्यूटर प्रोग्राम को गति देने के लिए उपयोग किया जाता है और जब वही इनपुट फिर से होता है तो कैश्ड परिणाम लौटाता है। मेमोइज़ेशन का उपयोग अन्य संदर्भों में भी किया गया है (और गति लाभ के अतिरिक्त अन्य उद्देश्यों के लिए), जैसे कि सरल पारस्परिक पुनरावर्तन अवतरण पार्सिंग में। चूंकि कैश (कंप्यूटिंग) से संबंधित, मेमोइज़ेशन इस अनुकूलन के एक विशिष्ट स्थितियों को संदर्भित करता है, इसे बफर (कंप्यूटर विज्ञान) या पृष्ठ प्रतिस्थापन एल्गोरिदम जैसे कैशिंग के रूपों से अलग करता है। कुछ तर्क प्रोग्रामिंग लैंग्वेज के संदर्भ में मेमोइज़ेशन को प्रोलॉग टेबलिंग के रूप में भी जाना जाता है।

व्युत्पत्ति

मेमोइज़ेशन शब्द 1968 में डोनाल्ड मिक्सी द्वारा गढ़ा गया था और लैटिन शब्द ज्ञापन (याद रखने के लिए) से लिया गया है, जिसे सामान्यतः अमेरिकी अंग्रेजी में मेमो के रूप में छोटा किया जाता है, और इस प्रकार किसी फ़ंक्शन को [परिणामों] को याद रखने के लिए बदलने का अर्थ होता है। जबकि मेमोइज़ेशन को मेमोराइज़ेशन के साथ भ्रमित किया जा सकता है (क्योंकि वे व्युत्पत्ति संबंधी संज्ञानात्मक हैं), कंप्यूटिंग में मेमोइज़ेशन का एक विशेष अर्थ है।

सिंहावलोकन

एक मेमोइज्ड फ़ंक्शन विशिष्ट इनपुट के कुछ सेट से संबंधित परिणामों को याद रखता है। याद किए गए इनपुट के साथ बाद की कॉल याद किए गए परिणाम को पुनर्गणना करने के अतिरिक्त वापस कर देती है, इस प्रकार दिए गए मापदंडों के साथ कॉल की प्राथमिक लागत को समाप्त कर देती है, किन्तु उन मापदंडों के साथ फ़ंक्शन के लिए की गई पहली कॉल। फ़ंक्शन की प्रकृति और इसके उपयोग के आधार पर याद किए गए संघों का सेट एक प्रतिस्थापन कलन विधि या एक निश्चित सेट द्वारा नियंत्रित एक निश्चित आकार का सेट हो सकता है। किसी फ़ंक्शन को केवल तभी याद किया जा सकता है जब वह संदर्भात्मक पारदर्शिता हो; अर्थात्, केवल तभी जब फ़ंक्शन को कॉल करने का ठीक वैसा ही प्रभाव होता है जैसा कि उस फ़ंक्शन कॉल को उसके रिटर्न मान से बदलने पर होता है। (चूंकि , इस प्रतिबंध के लिए विशेष स्थितियों के अपवाद उपस्थित हैं।) तालिका देखो से संबंधित होने के अतिरिक्त , मेमोइज़ेशन अक्सर इसके कार्यान्वयन में ऐसी तालिकाओं का उपयोग करता है, मेमोइज़ेशन अपने परिणामों के कैश को पारदर्शी रूप से फ्लाई पर, आवश्यकतानुसार, अग्रिम रूप से पॉप्युलेट करता है।

मेमोइज़ेशन अंतरिक्ष लागत के बदले फ़ंक्शन की समय लागत को कम करने का एक विधि है; अर्थात्, स्मृति स्पेस के उच्च उपयोग के बदले मेमोइज्ड फ़ंक्शंस गति के लिए अनुकूलित हो जाते हैं। एल्गोरिदम के समय/स्थान लागत का कंप्यूटिंग में एक विशिष्ट नाम है: कम्प्यूटेशनल जटिलता सिद्धांत। सभी कार्यों में समय में एक कम्प्यूटेशनल जटिलता होती है (अर्थात उन्हें निष्पादित करने में समय लगता है) और अंतरिक्ष में।

चूंकि एक स्पेस-टाइम ट्रेडऑफ़ होता है (यानी, इस्तेमाल किया गया स्थान गति प्राप्त होता है), यह कुछ अन्य अनुकूलन से अलग होता है जिसमें टाइम-स्पेस ट्रेड-ऑफ़ सम्मलित होता है, जैसे कि ताकत में कमी, उस मेमोइज़ेशन में एक रन टाइम (प्रोग्राम जीवनचक्र चरण) होता है| संकलन-समय अनुकूलन के अतिरिक्त रन-टाइम। इसके अतिरिक्त , शक्ति में कमी संभावित रूप से एक महंगे ऑपरेशन को बदल देती है जैसे कि कम खर्चीले ऑपरेशन जैसे कि जोड़, और बचत में परिणाम अत्यधिक मशीन-निर्भर (मशीनों में गैर-पोर्टेबल) हो सकते हैं, जबकि मेमोइज़ेशन एक अधिक मशीन-स्वतंत्र, क्रॉस है -मंच की रणनीति।

N के भाज्य की गणना करने के लिए निम्नलिखित स्यूडोकोड फ़ंक्शन पर विचार करें:

function factorial (n is a non-negative integer)
    if n is 0 then
        return 1 [by the convention that 0! = 1]
    else
        return factorial(n – 1) times n [recursively invoke factorial
                                         with the parameter 1 less than n]
    end if
end function

प्रत्येक पूर्णांक n के लिए ऐसा है कि n ≥ 0, फ़ंक्शन का अंतिम परिणाम factorial अपरिवर्तनीय (कंप्यूटर विज्ञान) है; अगर के रूप में आह्वान किया x = factorial(3), परिणाम ऐसा है कि x को हमेशा मान 6 असाइन किया जाएगा। उपरोक्त गैर-ज्ञात कार्यान्वयन, सम्मलित प्रत्यावर्तन एल्गोरिदम की प्रकृति को देखते हुए, एन + 1 आमंत्रण की आवश्यकता होगी factorial एक परिणाम पर पहुंचने के लिए, और इनमें से प्रत्येक आमंत्रण, बदले में, गणना किए गए मान को वापस करने के लिए कार्य करने में लगने वाले समय में संबद्ध लागत होती है। मशीन के आधार पर, यह लागत निम्न का योग हो सकती है:

1. कार्यात्मक कॉल स्टैक फ्रेम स्थापित करने की लागत।
2. n से 0 की तुलना करने की लागत।
3. n से 1 घटाने की लागत।
4. रिकर्सिव कॉल स्टैक फ्रेम सेट अप करने की लागत। (ऊपरोक्त अनुसार।)
5. पुनरावर्ती कॉल के परिणाम को गुणा करने की लागत factorial एन द्वारा।
6. रिटर्न रिजल्ट को स्टोर करने की लागत ताकि इसे कॉलिंग कॉन्टेक्स्ट द्वारा इस्तेमाल किया जा सके।

एक गैर-ज्ञात कार्यान्वयन में, प्रत्येक शीर्ष-स्तरीय कॉल to factorial चरण 2 से 6 तक की संचयी लागत n के प्रारंभिक मूल्य के अनुपात में सम्मलित है।

का एक यादगार संस्करण factorial फ़ंक्शन इस प्रकार है:

function factorial (n is a non-negative integer)
    if n is 0 then
        return 1 [by the convention that 0! = 1]
    else if n is in lookup-table then
         return lookup-table-value-for-n
    else
        et x = factorial(n – 1) times n [recursively invoke factorial
                                         with the parameter 1 less than n]
        store x in lookup-table in the nth slot [remember the result of n! for later]
        return x
    end if
end function 

इस विशेष उदाहरण में, यदि factorial पहले 5 के साथ लागू किया जाता है, और फिर बाद में पांच से कम या उसके बराबर किसी भी मूल्य के साथ लागू किया जाता है, उन वापसी मूल्यों को भी याद किया जाएगा, क्योंकि factorial 5, 4, 3, 2, 1, और 0 के मानों के साथ पुनरावर्ती रूप से बुलाया जाएगा, और उनमें से प्रत्येक के लिए वापसी मान संग्रहीत किए जाएंगे। यदि इसे 5 से बड़ी संख्या के साथ कॉल किया जाता है, जैसे 7, केवल 2 पुनरावर्ती कॉल किए जाएंगे (7 और 6), और 5 के लिए मान! पिछले कॉल से संग्रहीत किया जाएगा। इस तरह, संस्मरण एक फ़ंक्शन को अधिक समय-कुशल बनने की अनुमति देता है, जितनी बार इसे कहा जाता है, इस प्रकार अंततः समग्र गति-अप होता है।

कुछ अन्य विचार

कार्यात्मक प्रोग्रामिंग

Main article: थंक § कार्यात्मक प्रोग्रामिंग

कार्यात्मक प्रोग्रामिंग भाषाओं के लिए संकलक में मेमोइज़ेशन का अत्यधिक उपयोग किया जाता है, जो अक्सर नाम मूल्यांकन रणनीति द्वारा कॉल का उपयोग करते हैं। तर्क मूल्यों की गणना के साथ ओवरहेड से बचने के लिए, इन भाषाओं के संकलक तर्क मूल्यों की गणना करने के लिए थंक नामक सहायक कार्यों का भारी उपयोग करते हैं, और बार-बार होने वाली गणनाओं से बचने के लिए इन कार्यों को याद करते हैं।

स्वचालित संस्मरण

जबकि मेमोइज़ेशन को कंप्यूटर प्रोग्रामर द्वारा आंतरिक रूप से और स्पष्ट रूप से फ़ंक्शंस में जोड़ा जा सकता है, उसी तरह उपरोक्त मेमोइज़्ड संस्करण factorial लागू किया गया है, संदर्भित रूप से पारदर्शी कार्यों को स्वचालित रूप से बाह्य रूप से याद किया जा सकता है।पीटर नॉरविग द्वारा नियोजित तकनीकों का न केवल सामान्य लिस्प (जिस भाषा में उनके पेपर ने स्वचालित मेमोइज़ेशन प्रदर्शित किया था) में, बल्कि विभिन्न अन्य प्रोग्रामिंग भाषाओं में भी आवेदन किया है। शब्द पुनर्लेखन के अध्ययन में स्वचालित संस्मरण के अनुप्रयोगों का भी औपचारिक रूप से पता लगाया गया है और कृत्रिम बुद्धि। प्रोग्रामिंग भाषाओं में जहां कार्य प्रथम श्रेणी की वस्तुएं हैं (जैसे लुआ (प्रोग्रामिंग भाषा), पायथन (प्रोग्रामिंग भाषा), या पर्ल), पैरामीटर के दिए गए सेट के लिए मान की गणना करने के बाद स्वचालित मेमोइज़ेशन को (रन-टाइम पर) फ़ंक्शन को इसकी गणना मूल्य के साथ कार्यान्वित किया जा सकता है। फ़ंक्शन जो इस वैल्यू-फॉर-फ़ंक्शन-ऑब्जेक्ट प्रतिस्थापन को करता है, सामान्य रूप से किसी भी संदर्भित पारदर्शी फ़ंक्शन को लपेट सकता है। निम्नलिखित स्यूडोकोड पर विचार करें (जहां यह माना जाता है कि कार्य प्रथम श्रेणी के मान हैं):

    function memoized-call (F is a function object parameter)
      if F has no attached array values then
      allocate an associative array called values;
      attach values to F;
    end if;                                                                                                 
      if F.values[arguments] is empty then
        F.values[arguments] = F(arguments);
    end if;

    return F.values[arguments];
end function

स्वचालित रूप से याद किए गए संस्करण को कॉल करने के लिए factorial कॉल करने के अतिरिक्त उपरोक्त रणनीति का उपयोग करना factorial सीधे, कोड आमंत्रित करता है memoized-call(factorial(n)). इस तरह की प्रत्येक कॉल पहले यह देखने के लिए जांच करती है कि क्या परिणामों को संग्रहीत करने के लिए एक धारक सरणी आवंटित की गई है, और यदि नहीं, तो वह सरणी संलग्न करती है। यदि स्थिति पर कोई प्रविष्टि उपस्थित नहीं है values[arguments] (कहाँ arguments साहचर्य सरणी की कुंजी के रूप में उपयोग किया जाता है), एक वास्तविक कॉल किया जाता है factorial प्रदान किए गए तर्कों के साथ। अंत में, कुंजी स्थिति में सरणी में प्रविष्टि कॉलर को वापस कर दी जाती है।

उपरोक्त रणनीति के लिए प्रत्येक कॉल पर एक फ़ंक्शन के लिए स्पष्ट रैपिंग की आवश्यकता होती है जिसे याद किया जाना है। उन भाषाओं में जो क्लोजर (कंप्यूटर विज्ञान) की अनुमति देते हैं, मेमोइज़ेशन को फ़ंक्शन वस्तु फ़ैक्टरी के माध्यम से स्पष्ट रूप से प्रभावित किया जा सकता है जो एक डेकोरेटर पैटर्न में लिपटे मेमोइज़्ड फ़ंक्शन ऑब्जेक्ट को लौटाता है। स्यूडोकोड में, इसे इस प्रकार व्यक्त किया जा सकता है:

    function construct-memoized-functor (F is a function object parameter)
    allocate a function object called memoized-version;
    let memoized-version(arguments) be
        if self has no attached array values then [self is a reference to this object]
            allocate an associative array called values;
            attach values to self;
        end if;

        if self.values[arguments] is empty then
            self.values[arguments] = F(arguments);
        end if;

        return self.values[arguments];
    end let;

    return memoized-version;
end function

कॉल करने के अतिरिक्त factorial, एक नया फ़ंक्शन ऑब्जेक्ट memfact निम्नानुसार बनाया गया है:

  memfact = construct-memoized-functor(factorial)

उपरोक्त उदाहरण मानता है कि function factorial को कॉल करने से पहले ही परिभाषित कर दिया गया है construct-memoized-functor से बना। इस बिंदु से आगे, memfact(n) जब कभी n का क्रमगुणन वांछित होता है तब उसे कॉल किया जाता है। लुआ जैसी भाषाओं में, अधिक परिष्कृत तकनीकें उपस्थित हैं जो एक फ़ंक्शन को उसी नाम से एक नए फ़ंक्शन द्वारा प्रतिस्थापित करने की अनुमति देती हैं, जो अनुमति देगा:

  factorial = construct-memoized-functor(factorial)

अनिवार्य रूप से, इस तरह की तकनीकों में मूल फ़ंक्शन ऑब्जेक्ट को बनाए गए फ़ंक्टर को संलग्न करना और कॉल को अग्रेषित करना मूल फ़ंक्शन को उपनाम के माध्यम से याद किया जाता है जब वास्तविक फ़ंक्शन के लिए कॉल की आवश्यकता होती है (अंतहीन पुनरावर्तन से बचने के लिए), जैसा कि नीचे दिखाया गया है:

    function construct-memoized-functor (F is a function object parameter)
         allocate a function object called memoized-version;
    let memoized-version(arguments) be
        if self has no attached array values then [self is a reference to this object]
            allocate an associative array called values;
            attach values to self;
            allocate a new function object called alias;
            attach alias to self; [for later ability to invoke F indirectly]
            self.alias = F;
        end if;

        if self.values[arguments] is empty then
            self.values[arguments] = self.alias(arguments); [not a direct call to F]
        end if;

        return self.values[arguments];
    end let;

    return memoized-version;
end function

(नोट: ऊपर दिखाए गए कुछ चरणों को कार्यान्वयन भाषा द्वारा अप्रत्यक्ष रूप से प्रबंधित किया जा सकता है और उदाहरण के लिए प्रदान किया गया है।)

पार्सर्स

जब एक टॉप-डाउन पदच्छेद | टॉप-डाउन पार्सर एक अस्पष्ट संदर्भ-मुक्त व्याकरण (CFG) के संबंध में एक सिंटैक्टिक अस्पष्टता इनपुट को पार्स करने का प्रयास करता है, तो उसे चरणों की एक घातीय संख्या (इनपुट की लंबाई के संबंध में) की आवश्यकता हो सकती है सभी संभावित पार्स पेड़ बनाने के लिए सीएफजी के सभी विकल्पों का प्रयास करें। इसके लिए अंततः घातीय मेमोरी स्पेस की आवश्यकता होगी। 1991 में पीटर नॉरविग द्वारा मेमोइज़ेशन को एक पार्सिंग रणनीति के रूप में खोजा गया था, जिन्होंने दिखाया कि अर्ली पार्सर में गतिशील प्रोग्रामिंग और स्टेट-सेट के उपयोग के समान सीवाईके एल्गोरिदम कसमी, घातीय समय जटिलता की समस्या को हल करने के लिए एक साधारण बैक ट्रैकिंग पुनरावर्ती वंश पार्सर को स्वचालित ज्ञापन शुरू करके उत्पन्न किया जा सकता है।नॉरविग के दृष्टिकोण में मूल विचार यह है कि जब एक पार्सर इनपुट पर लागू होता है, तो परिणाम बाद के पुन: उपयोग के लिए यादगार में संग्रहीत किया जाता है यदि उसी पार्सर को कभी भी उसी इनपुट पर दोबारा लागू किया जाता है। रिचर्ड फ्रॉस्ट ने पार्सर कॉम्बिनेटर की घातीय समय जटिलता को कम करने के लिए ज्ञापन का भी उपयोग किया, जिसे "विशुद्ध रूप से कार्यात्मक टॉप-डाउन बैकट्रैकिंग" पार्सिंग तकनीक के रूप में देखा जा सकता है। उन्होंने दिखाया कि सीएफजी के निष्पादन योग्य विनिर्देशों के रूप में जटिल पार्सर बनाने के लिए बुनियादी मेमोइज्ड पार्सर कॉम्बिनेटर का उपयोग बिल्डिंग ब्लॉक के रूप में किया जा सकता है। 1995 में जॉनसन द्वारा पार्सिंग के संदर्भ में इसे फिर से खोजा गया और डोरे। 2002 में, फोर्ड द्वारा पैकराट पार्सर नामक रूप में इसकी काफी गहराई से जांच की गई थी। 2007 में, फ्रॉस्ट, हाफिज और कैलाघन ने एक टॉप-डाउन पार्सिंग एल्गोरिदम का वर्णन किया है जो बहुपद समय (बिग ओ नोटेशन|Θ(n)⁴) बाएँ पुनरावर्तन के लिए | बाएँ-पुनरावर्ती व्याकरण और Θ(n³) गैर वाम-पुनरावर्ती व्याकरण के लिए)। उनके टॉप-डाउन पार्सिंग एल्गोरिदम को 'कॉम्पैक्ट प्रतिनिधित्व' और 'स्थानीय अस्पष्टता समूह' द्वारा संभावित घातीय अस्पष्ट पार्स पेड़ के लिए बहुपद स्थान की भी आवश्यकता होती है। उनका कॉम्पैक्ट प्रतिनिधित्व टॉमिटा के नीचे-ऊपर पार्सिंग के कॉम्पैक्ट प्रतिनिधित्व के साथ तुलनीय है। मेमोइज़ेशन का उनका उपयोग केवल पहले से गणना किए गए परिणामों को पुनर्प्राप्त करने तक ही सीमित नहीं है जब एक पार्सर को एक ही इनपुट स्थिति पर बार-बार लागू किया जाता है (जो बहुपद समय की आवश्यकता के लिए आवश्यक है); यह निम्नलिखित अतिरिक्त कार्यों को करने के लिए विशिष्ट है:

• मेमोइज़ेशन प्रक्रिया (जिसे किसी भी पार्सर निष्पादन के आसपास 'रैपर' के रूप में देखा जा सकता है) इनपुट लंबाई और वर्तमान इनपुट स्थिति के संबंध में गहराई प्रतिबंध लगाकर एक निरंतर बढ़ते प्रत्यक्ष बाएं-पुनरावर्ती पार्स को समायोजित करती है।
• एल्गोरिदम की मेमो-टेबल 'लुकअप' प्रक्रिया सहेजे गए परिणाम के कम्प्यूटेशनल संदर्भ की पार्सर के वर्तमान संदर्भ के साथ तुलना करके सहेजे गए परिणाम की पुन: प्रयोज्यता को भी निर्धारित करती है। यह प्रासंगिक तुलना अप्रत्यक्ष (या छिपी हुई) वाम-पुनरावृत्ति को समायोजित करने की कुंजी है।
• एक मेमोटेबल में एक सफल लुकअप करते समय, पूर्ण परिणाम-सेट वापस करने के अतिरिक्त , प्रक्रिया केवल वास्तविक परिणाम के संदर्भों को वापस करती है और अंततः समग्र गणना को गति देती है।
• मेमोटेबल को अपडेट करने के दौरान, मेमोइज़ेशन प्रक्रिया समूह (संभावित रूप से घातीय) अस्पष्ट परिणाम देती है और बहुपद स्थान की आवश्यकता को सुनिश्चित करती है।

फ्रॉस्ट, हाफिज और कैलाघन ने भी PADL'08 में एल्गोरिथम के कार्यान्वयन का वर्णन किया हास्केल (प्रोग्रामिंग भाषा) में उच्च-क्रम के कार्यों (पार्सर कॉम्बिनेटर कहा जाता है) के एक सेट के रूप में, जो भाषा प्रोसेसर के रूप में सीएफजी के सीधे निष्पादन योग्य विनिर्देशों के निर्माण को सक्षम बनाता है। टॉप-डाउन पार्सिंग के साथ 'अस्पष्ट सीएफजी के किसी भी रूप' को समायोजित करने के लिए उनके बहुपद एल्गोरिदम की शक्ति का महत्व प्राकृतिक भाषा प्रसंस्करण के दौरान वाक्यविन्यास और शब्दार्थ विश्लेषण के संबंध में महत्वपूर्ण है। X-SAIGA साइट में एल्गोरिथम और कार्यान्वयन विवरण के बारे में अधिक जानकारी है।

जबकि नॉरविग ने मेमोइज़ेशन के माध्यम से पार्सर की शक्ति में वृद्धि की, संवर्धित पार्सर अभी भी अर्ली के एल्गोरिथ्म के रूप में जटिल था, जो गति अनुकूलन के अतिरिक्त किसी अन्य चीज़ के लिए मेमोइज़ेशन के उपयोग के स्थितियों को प्रदर्शित करता है। जॉनसन और डोरेमेमोइज़ेशन के ऐसे अन्य गैर-गति संबंधी अनुप्रयोग को प्रदर्शित करता है: भाषाई बाधाओं के समाधान में विलंब करने के लिए मेमोइज़ेशन का उपयोग एक पार्स में एक बिंदु पर जहां उन बाधाओं को हल करने के लिए पर्याप्त जानकारी जमा की गई है। इसके विपरीत, मेमोइज़ेशन के स्पीड ऑप्टिमाइज़ेशन एप्लिकेशन में, फोर्ड ने प्रदर्शित किया कि मेमोइज़ेशन गारंटी दे सकता है कि पार्सिंग अभिव्यक्ति व्याकरण बिग ओ नोटेशन समय में पार्स कर सकते हैं, यहां तक ​​​​कि उन औपचारिक भाषाओं में भी जो सबसे खराब स्थिति वाले बैकट्रैकिंग व्यवहार का परिणाम हैं।

निम्नलिखित औपचारिक व्याकरण पर विचार करें:

S → (A c) | (B d)
A → X (a|b)
B → X b
X → x [X]

(नोटेशन नोट: उपरोक्त उदाहरण में, औपचारिक व्याकरण # व्याकरण का वाक्य विन्यास 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 होगा (इस विशेष स्थितियों में)।

वे पार्सर जो सिंटैक्टिक विधेय का उपयोग करते हैं, वे विधेय पार्स के परिणामों को भी याद रखने में सक्षम होते हैं, जिससे इस तरह के निर्माण को कम किया जा सकता है:

S → (A)? A
A → /* some rule */

ए में एक वंश के लिए।

यदि कोई पार्सर एक पार्स के दौरान एक पार्स ट्री बनाता है, तो उसे न केवल उस इनपुट की लंबाई को याद रखना चाहिए जो किसी दिए गए नियम के विरुद्ध कुछ ऑफ़सेट पर मेल खाता है, बल्कि उस उप-ट्री को भी स्टोर करना चाहिए जो उस ऑफ़सेट में उस नियम द्वारा उत्पन्न होता है। इनपुट, क्योंकि पार्सर द्वारा नियम के बाद की कॉल वास्तव में उस पेड़ से नहीं उतरेंगी और उसका पुनर्निर्माण नहीं करेंगी। इसी कारण से, मेमोइज्ड पार्सर एल्गोरिदम जो बाहरी कोड (कभी-कभी सिमेंटिक एक्शन रूटीन कहा जाता है) को कॉल उत्पन्न करते हैं, जब एक नियम मिलान को यह सुनिश्चित करने के लिए कुछ योजना का उपयोग करना चाहिए कि ऐसे नियमों को अनुमानित क्रम में लागू किया जाता है।

चूंकि, किसी दिए गए बैकट्रैकिंग या सिंटैक्टिक विधेय सक्षम पार्सर के लिए प्रत्येक व्याकरण को बैकट्रैकिंग या विधेय चेक की आवश्यकता नहीं होगी, इनपुट में प्रत्येक ऑफ़सेट के खिलाफ प्रत्येक नियम के पार्स परिणामों को संग्रहीत करने का ओवरहेड (और पार्सिंग प्रक्रिया को अंतर्निहित रूप से करता है तो पार्स पेड़ को संग्रहित करना) हो सकता है वास्तव में एक पार्सर धीमा करें। इस प्रभाव को उन नियमों के स्पष्ट चयन से कम किया जा सकता है जिन्हें पार्सर याद रखेगा।

यह भी देखें

• अनुमानित कंप्यूटिंग - दक्षता में सुधार के लिए तकनीकों की श्रेणी
• कम्प्यूटेशनल जटिलता सिद्धांत - एल्गोरिथम जटिलता पर अधिक जानकारी
• निदेशक स्ट्रिंग - भावों में तेजी से मुक्त चर का पता लगाना
• फ्लाईवेट पैटर्न - एक ऑब्जेक्ट प्रोग्रामिंग डिज़ाइन पैटर्न (कंप्यूटर साइंस), जो एक तरह के मेमोइज़ेशन का भी उपयोग करता है
• हैशलाइफ - सेल्यूलर आटोमेटा की गणना को गति देने के लिए एक यादगार तकनीक
• आलसी मूल्यांकन - मेमोइज़ेशन के साथ कुछ अवधारणाओं को साझा करता है
• भौतिक दृश्य - डेटाबेस प्रश्नों में समान कैशिंग
• आंशिक मूल्यांकन - स्वचालित प्रोग्राम अनुकूलन के लिए एक संबंधित तकनीक

बाहरी संबंध

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 – 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.