जावास्क्रिप्ट पूंछ पुनरावृत्ति अनुकूलन

नमस्कार पाठक।

कभी-कभी समस्या को हल करने के लिए आपको रिकर्सियन का उपयोग करना पड़ता है, जिसमें इसके पेशेवरों और विपक्ष हैं। मैं ढेर अतिप्रवाह समस्या में भाग गया।

अधिकतम पुनरावृत्ति की गहराई जावास्क्रिप्ट इंजन द्वारा सीमित है। आप 10,000 नेस्टेड कॉल पर सटीक रूप से भरोसा कर सकते हैं, कुछ दुभाषिए अधिक की अनुमति देते हैं, लेकिन उनमें से ज्यादातर के लिए 100,000 कॉल क्षमताओं के दायरे से परे हैं। स्वचालित अनुकूलन हैं जो कॉल स्टैक ("पूंछ पुनरावृत्ति अनुकूलन") के अतिप्रवाह से बचने में मदद करते हैं, लेकिन वे अभी तक हर जगह समर्थित नहीं हैं और केवल सरल मामलों के लिए काम करते हैं।

एक पुनरावर्ती कार्य का एक उदाहरण:

function sum(n) { return n === 0 ? 0 : n + sum(n - 1) } sum(5) // 1 + 2 + 3 + 4 + 5 = 15 sum(100000) // Error: Maximum call stack size exceeded. 

पूंछ पुनरावृत्ति संकलक द्वारा कॉल का अनुकूलन करने की अनुमति देता है और पहले से ही ES6 मानक में है, लेकिन ब्राउज़र समर्थन वांछित होने के लिए बहुत कुछ छोड़ देता है ।

एक पूंछ पुनरावर्ती कार्य का एक उदाहरण:

 function sum(number, s = 0){ return number === 0 ? s : sum(number - 1, s + number) } 

लेकिन, ब्राउज़र समर्थन के बिना, हम एक ही समस्या का सामना करेंगे - स्टैक ओवरफ्लो। हम Trampolining के साथ मिलकर उपयोग करने का प्रयास कर सकते हैं।

हम एक डेकोरेटर लिखेंगे जो संशोधित पुनरावर्ती फ़ंक्शन (अगला चरण) को स्वीकार करेगा और कॉल की गहराई को बढ़ाए बिना इसे लूप में निष्पादित करेगा।

 function trampoline(fn) { return function(...args) { let result = fn.apply(fn.context, args) while (typeof result === 'function') { result = result() } return result } } 

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

 function sum(number, s = 0) { return number === 0 ? s : () => sum(number - 1, s + number) } 

हम उपयोग करते हैं:

 const trampolineSum = trampoline(sum) trampolineSum(100000) // 5000050000 

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

आपका ध्यान के लिए धन्यवाद। आपका दिन शुभ रहे :)

अद्यतन
प्रदर्शन:

# 1 पुनरावृत्ति




# 2 Iteration




# 3 पूंछ पुनरावृत्ति और trampoline




# 4 पूंछ पुनरावृत्ति और trampoline (एक बड़ी संख्या)




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