रिकर्सन ओवरहेड - यह कितना गंभीर है?

Question

संभव डुप्लिकेट:
Is recursion ever faster than looping?

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

अब मैं सी, पायथन, पर्ल और कभी-कभी जावा में कोड करता हूं, और मुझे कभी-कभी रिकर्सन के बारे में आश्चर्य होता है। क्या उन्हें अभी भी लिखकर कुछ हासिल किया जा सकता है? क्या होगा यदि वे पूंछ रिकर्स हैं? क्या आधुनिक कंपाइलर्स ने इन सभी मुद्दों को हल किया है? क्या ऐसी चिंताओं को व्याख्या की गई भाषाओं के लिए अप्रासंगिक है?

Answer 1

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

यह कहा गया कि, यदि रिकर्सन से बचने का आपका विचार स्वयं ढेर जैसी संरचना बनाना है, तो देखें - यह अधिक सरल पुनरावर्ती दृष्टिकोण से कहीं अधिक तेज़ नहीं हो सकता है। फिर, प्रोफाइलिंग आपका दोस्त है।

अंत में, याद रखें कि प्रोग्रामर समय CPU समय से अधिक महंगा है। अपने कोड को माइक्रो-ऑप्टिमाइज़ करने से पहले, यह वास्तव में एक मुद्दा होगा कि यह वास्तव में एक मुद्दा होगा या नहीं।

Answer 2

मुझे नहीं लगता कि आपके द्वारा उल्लिखित भाषाओं में से कोई भी की आवश्यकता है कि प्लेटफ़ॉर्म/कंपाइलर tail call elimination लागू करता है। आप ऐसी भाषाएं पा सकते हैं जो करें इस अनुकूलन की आवश्यकता है - अधिकांश कार्यात्मक भाषाओं में यह आवश्यकता है।

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

एक चीज जो आप करते हैं स्टैक बहने के बारे में चिंता करने की आवश्यकता है। यदि ऐसा होने का कोई खतरा है तो इसके बजाय एक पुनरावर्ती तरीके से एक पुनरावर्ती कार्य को फिर से लिखना उचित हो सकता है।

Answer 3

यह गंभीर है। जिन भाषाओं में मैं कोड करता हूं उनमें से अधिकांश भाषाओं में कॉल करने के लिए वास्तविक लागत होती है (उनके लिए कंपाइलर्स आम तौर पर पूंछ रिकर्सन कर सकते हैं, इसलिए कभी-कभी यह कोई मुद्दा नहीं है)।

वह लागत, और तथ्य यह है कि स्टैक असीमित संसाधन नहीं है, आम तौर पर मुझे केवल उन मामलों के लिए रिकर्सन का उपयोग करने लगता है जहां मुझे पता है कि गहराई पर एक सीमा है।

उदाहरण के लिए, मुझे पता है कि एक संतुलित बाइनरी पेड़ खोज केवल एक चौथाई प्रविष्टियों के लिए पचास स्तर गहरी जाएगी। मुझे नहीं है, तथापि, का प्रयोग करेंगे:

def sum1through (n): 
    if n == 0 return 0 
    return n + sum1through (n-1) 

दो करोड़ की n के लिए कर रही है कि जब एक ढेर के लिए स्वस्थ नहीं होगा।

Answer 4

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

Answer 5

लोग प्रदर्शन के बारे में बहुत सी मूर्ख बातें कहते हैं।

1. आप जरूरत प्रत्यावर्तन, गहराई-प्रथम पेड़ की पैदल दूरी पर करना पसंद है, तो आप इसकी आवश्यकता है, तो यह उपयोग करें।

2. के कुछ भी के प्रदर्शन के बारे में चिंता करने से पहले, पता लगाएं कि क्या आपको कोई समस्या है और यह कहां है।
   प्रदर्शन समस्याएं पुरुष और ट्रिकस्टर्स की तरह हैं - वे कम से कम अपेक्षा करते हैं, इसलिए यदि आप रिकर्सन जैसी विशिष्ट चीज़ के बारे में चिंतित हैं, तो आप लगभग गलत चीज़ के बारे में चिंता करने की गारंटी देते हैं।

मेरी राय में, प्रदर्शन की समस्याओं को खोजने के लिए सबसे अच्छा तरीका है ही नहीं, माप हो रही है और चाहते हैं कि वे क्या मतलब द्वारा, दीवार घड़ी समय पर ढेर नमूना से है, और examining the samples to see what the program is doing।

यह कहा गया है कि, यदि आपको रिकर्सिव कॉल में 10% या अधिक समय लगता है, और रिकर्सिव रूटीन के अंदर और कुछ भी नहीं होता है, और आप इसे लूप कर सकते हैं, तो इसे लूप करने से शायद मदद मिलेगी।