algorithm - रचन - पूंछ कॉल अनुकूलन क्या है?




संरचनात्मक अनुकूलन क्या है (5)

बहुत सरलता से, पूंछ-कॉल अनुकूलन क्या है? अधिक विशेष रूप से, क्या कोई भी कुछ छोटे कोड स्निपेट दिखा सकता है जहां इसे लागू किया जा सकता है, और कहां नहीं, क्यों एक स्पष्टीकरण के साथ?


  1. हमें यह सुनिश्चित करना चाहिए कि फ़ंक्शन में कोई गेटो स्टेटमेंट न हो .. कैलिफ़ फ़ंक्शन में अंतिम कॉल होने पर फ़ंक्शन कॉल द्वारा देखभाल की गई।

  2. बड़े पैमाने पर रिकर्सन ऑप्टिमाइज़ेशन के लिए इसका उपयोग कर सकते हैं, लेकिन छोटे पैमाने पर, फंक्शन कॉल करने के लिए निर्देश ओवरहेड एक पूंछ कॉल को वास्तविक उद्देश्य को कम कर देता है।

  3. टीसीओ हमेशा के लिए चल रहे समारोह का कारण बन सकता है:

    void eternity()
    {
        eternity();
    }
    

आइए एक साधारण उदाहरण के माध्यम से चलें: सी में लागू फैक्टोरियल फ़ंक्शन।

हम स्पष्ट रिकर्सिव परिभाषा के साथ शुरू करते हैं

unsigned fac(unsigned n)
{
    if (n < 2) return 1;
    return n * fac(n - 1);
}

एक फ़ंक्शन कॉल के साथ एक फ़ंक्शन समाप्त होता है यदि फ़ंक्शन रिटर्न से पहले अंतिम ऑपरेशन एक और फ़ंक्शन कॉल है। यदि यह कॉल एक ही फ़ंक्शन को आमंत्रित करता है, तो यह पूंछ-पुनरावर्ती है।

भले ही fac() पहली नज़र में पूंछ-पुनरावर्ती दिखता है, यह वास्तव में ऐसा नहीं होता है

unsigned fac(unsigned n)
{
    if (n < 2) return 1;
    unsigned acc = fac(n - 1);
    return n * acc;
}

यानी अंतिम ऑपरेशन गुणा है और फ़ंक्शन कॉल नहीं है।

हालांकि, कॉल श्रृंखला को संचित मूल्य को एक अतिरिक्त तर्क के रूप में पास करके और वापसी के मूल्य के रूप में केवल अंतिम परिणाम को पारित करके fac() को फिर से लिखना संभव है:

unsigned fac(unsigned n)
{
    return fac_tailrec(1, n);
}

unsigned fac_tailrec(unsigned acc, unsigned n)
{
    if (n < 2) return acc;
    return fac_tailrec(n * acc, n - 1);
}

अब, यह क्यों उपयोगी है? चूंकि हम तुरंत पूंछ कॉल के बाद वापस आते हैं, हम पूंछ की स्थिति में फ़ंक्शन को आविष्कार करने से पहले पिछले स्टैकफ्रेम को त्याग सकते हैं, या रिकर्सिव फ़ंक्शंस के मामले में, स्टैकफ्रेम को पुन: उपयोग कर सकते हैं।

पूंछ-कॉल अनुकूलन हमारे रिकर्सिव कोड को बदल देता है

unsigned fac_tailrec(unsigned acc, unsigned n)
{
TOP:
    if (n < 2) return acc;
    acc = n * acc;
    n = n - 1;
    goto TOP;
}

इसे fac() में रेखांकित किया जा सकता है और हम पहुंचते हैं

unsigned fac(unsigned n)
{
    unsigned acc = 1;

TOP:
    if (n < 2) return acc;
    acc = n * acc;
    n = n - 1;
    goto TOP;
}

जो बराबर है

unsigned fac(unsigned n)
{
    unsigned acc = 1;

    for (; n > 1; --n)
        acc *= n;

    return acc;
}

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


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

यह अनुकूलन रिकर्सिव कॉल को विस्फोट के बजाए निरंतर स्टैक स्पेस ले सकता है।

उदाहरण: यह फैक्टोरियल फ़ंक्शन TCOptimizable नहीं है:

def fact(n):
    if n == 0:
        return 1
    return n * fact(n-1)

यह फ़ंक्शन इसके बदले में एक और फ़ंक्शन कॉल करने के अलावा चीजें करता है।

यह नीचे कार्य TCOptimizable है:

def fact_h(n, acc):
    if n == 0:
        return acc
    return fact_h(n-1, acc*n)

def fact(n):
    return fact_h(n, 1)

ऐसा इसलिए है क्योंकि इनमें से किसी भी कार्य में होने वाली आखिरी चीज किसी अन्य फ़ंक्शन को कॉल करना है।


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

योजना उन कुछ प्रोग्रामिंग भाषाओं में से एक है जो इस कल्पना में गारंटी देते हैं कि किसी भी कार्यान्वयन को इस अनुकूलन को प्रदान करना होगा (जावास्क्रिप्ट भी एक बार ईएस 6 को अंतिम रूप दिया जाएगा) , इसलिए योजना में फैक्टोरियल फ़ंक्शन के दो उदाहरण यहां दिए गए हैं:

(define (fact x)
  (if (= x 0) 1
      (* x (fact (- x 1)))))

(define (fact x)
  (define (fact-tail x accum)
    (if (= x 0) accum
        (fact-tail (- x 1) (* x accum))))
  (fact-tail x 1))

पहला कार्य पूंछ रिकर्सिव नहीं है क्योंकि जब रिकर्सिव कॉल किया जाता है, तो फ़ंक्शन को कॉल रिटर्न के बाद परिणाम के साथ होने वाले गुणा का ट्रैक रखने की आवश्यकता होती है। इस प्रकार, ढेर निम्नानुसार दिखता है:

(fact 3)
(* 3 (fact 2))
(* 3 (* 2 (fact 1)))
(* 3 (* 2 (* 1 (fact 0))))
(* 3 (* 2 (* 1 1)))
(* 3 (* 2 1))
(* 3 2)
6

इसके विपरीत, पूंछ रिकर्सिव फैक्टोरियल के लिए स्टैक ट्रेस निम्नानुसार है:

(fact 3)
(fact-tail 3 1)
(fact-tail 2 3)
(fact-tail 1 6)
(fact-tail 0 6)
6

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


सबसे पहले ध्यान दें कि सभी भाषाएं इसका समर्थन नहीं करती हैं।

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

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





tail-call-optimization