2012-02-21 12 views
7

यह मेरे हिस्से पर सिर्फ जिज्ञासा है, लेकिन अधिक कुशल, रिकर्सन या लूप क्या है?क्षमता: रिकर्सन बनाम लूप

को देखते हुए दो कार्य (आम तुतलाना उपयोग करते हुए):

(defun factorial_recursion (x) 
    (if (> x 0) 
     (* x (factorial_recursion (decf x))) 
     1)) 

और

(defun factorial_loop (x) 
    (loop for i from 1 to x for result = 1 then 
     (* result i) finally 
     (return result))) 

कौन सा अधिक कुशल है?

+0

यदि आपका कार्य पूंछ-पुनरावर्ती है, तो यह मूल रूप से लूप के समान है। पूंछ रिकर्सन को एक साधारण लूप में अनुकूलित किया जा सकता है, जिससे उन्हें समान बनाया जा सकता है। आपका काम पूंछ-पुनरावर्ती नहीं है, यद्यपि। – Gabe

+0

1- के साथ डीसीएफ को प्रतिस्थापित करें। –

+0

@Gabe, जबकि पूंछ रिकर्सन को लूप में अनुकूलित किया जा सकता है, यह ध्यान देने योग्य है कि पूंछ कॉल को अनुकूलित करने के लिए सामान्य लिस्प कार्यान्वयन की आवश्यकता नहीं है, हालांकि कई कार्यान्वयन करते हैं। –

उत्तर

22

मुझे अपना कोड भी पढ़ना नहीं है।

लूप फैक्टोरियल के लिए अधिक कुशल है। जब आप रिकर्सन करते हैं, तो आपके पास स्टैक पर x फ़ंक्शन कॉल हैं।

आप प्रदर्शन कारणों से लगभग कभी भी रिकर्सन का उपयोग नहीं करते हैं। आप समस्या को और अधिक सरल बनाने के लिए रिकर्सन का उपयोग करते हैं।

+0

मैं और अधिक सहमत नहीं हो सका (भले ही सैम मुझे मैटलैब पसंद नहीं है: पी जेके), स्टैक रिकर्सन के लिए महत्वपूर्ण है। उत्तर के लिए – macduff

+0

thnx, मैंने वही सोचा। – Rusty

7

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

सैम आई एम सही है हालांकि, पुनरावृत्त कार्य आमतौर पर उनके रिकर्सिव समकक्षों की तुलना में तेज़ होते हैं। यदि एक रिकर्सिव फ़ंक्शन एक पुनरावृत्ति फ़ंक्शन के रूप में तेज़ होना है जो एक ही काम करता है, तो आपको ऑप्टिमाइज़र पर भरोसा करना होगा।

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

आपके द्वारा दिया गया कार्य पूंछ रिकर्सिव नहीं है क्योंकि आप factorial_recursion पर कॉल करते हैं और फिर आप इसे x से गुणा करते हैं। एक पूंछ पुनरावर्ती संस्करण का एक उदाहरण

(defun factorial-recursion-assist (x cur) 
    (if (> x 1) 
     (factorial-recursion-assist (- x 1) (+ cur (* (- x 1) x))) 
     cur)) 

(defun factorial-recursion (x) 
    (factorial-recursion-assist x 1)) 

(print (factorial-recursion 4)) 
+0

आम लिस्प मानक किसी भी तरह से पूंछ रिकर्सन का उल्लेख नहीं करता है। हालांकि कुछ सीएल कंपाइलर्स इसका समर्थन करते हैं। टीसीओ करने के लिए कंपाइलर को मजबूर करने के तरीके को देखने के लिए किसी को अपने मैनुअल को पढ़ने की जरूरत है। –

+1

@RainerJoswig हाँ, यही कारण है कि मैंने पूंछ रिकर्सन –

+0

के लिए पूर्व शर्त की सूची में कंपाइलर/दुभाषिया का भी उल्लेख किया ... टेल रिकर्सन ऑप्टिमाइज़ेशन –

-2

होगा यहाँ एक पूंछ पुनरावर्ती भाज्य (मुझे लगता है कि) है:

(defun fact (x) 
    (funcall (alambda (i ret) 
      (cond ((> i 1) 
        (self (1- i) (* ret i))) 
        (t 
        ret))) 
      x 1)) 
9

म्यू।

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

अब, यदि आप वास्तव में जानना चाहते हैं कि कौन तेज़ है, तो उन्हें मापें। एसबीसीएल पर, आप प्रत्येक फंक्शन को लूप में कॉल कर सकते हैं और समय को माप सकते हैं। चूंकि आपके पास दो सरल कार्य हैं, time पर्याप्त है। यदि आपका प्रोग्राम अधिक जटिल था, तो profiler अधिक उपयोगी होगा। संकेत: अगर आपको अपने माप के लिए प्रोफाइलर की आवश्यकता नहीं है, तो आपको शायद प्रदर्शन के बारे में चिंता करने की आवश्यकता नहीं है।

मेरी मशीन पर (SBCL 64 बिट), मैं अपने कार्यों भाग गया और यह मिल गया:

CL-USER> (time (loop repeat 1000 do (factorial_recursion 1000))) 
Evaluation took: 
    0.540 seconds of real time 
    0.536034 seconds of total run time (0.496031 user, 0.040003 system) 
    [ Run times consist of 0.096 seconds GC time, and 0.441 seconds non-GC time. ] 
    99.26% CPU 
    1,006,632,438 processor cycles 
    511,315,904 bytes consed 

NIL 
CL-USER> (time (loop repeat 1000 do (factorial_loop 1000))) 
Evaluation took: 
    0.485 seconds of real time 
    0.488030 seconds of total run time (0.488030 user, 0.000000 system) 
    [ Run times consist of 0.072 seconds GC time, and 0.417 seconds non-GC time. ] 
    100.62% CPU 
    902,043,247 processor cycles 
    511,322,400 bytes consed 

NIL 

शीर्ष पर (declaim (optimize speed)) के साथ एक फ़ाइल में अपने कार्यों डालने के बाद, प्रत्यावर्तन समय 504 मिलीसेकंड और को गिरा दिया लूप का समय 475 मिलीसेकंड तक गिर गया।

और यदि आप वास्तव में जानना चाहते हैं कि क्या हो रहा है, तो अपने कार्यों पर dissasemble आज़माएं और देखें कि वहां क्या है।

फिर से, यह मेरे लिए एक गैर-मुद्दे की तरह दिखता है। व्यक्तिगत रूप से, मैं प्रोटोटाइपिंग के लिए एक स्क्रिप्टिंग भाषा की तरह सामान्य लिस्प का उपयोग करने का प्रयास करता हूं, फिर प्रोफाइल को धीमा कर देता हूं और धीमा कर देता हूं। 500ms से 475ms तक प्राप्त करना कुछ भी नहीं है। उदाहरण के लिए, कुछ व्यक्तिगत कोड में, मुझे एक सरणी में एक तत्व प्रकार जोड़कर परिमाण गतिशीलता के कुछ आदेश मिलते हैं (इस प्रकार मेरे मामले में सरणी भंडारण 64 गुना छोटा बनाते हैं)। निश्चित रूप से, सिद्धांत रूप में यह उस सरणी (इसे छोटा करने के बाद) का पुन: उपयोग करने के लिए तेज़ होता और इसे आवंटित नहीं किया जाता। लेकिन बस मेरी स्थिति के लिए :element-type bit जोड़ना पर्याप्त था - अधिक परिवर्तनों के लिए बहुत कम अतिरिक्त लाभ के लिए अधिक समय की आवश्यकता होगी। शायद मैं मैला हूँ, लेकिन 'तेज़' और 'धीमी' का मतलब मेरे लिए बहुत मायने नहीं रखता है। मैं 'पर्याप्त तेज़' और 'बहुत धीमी' पसंद करता हूं। ज्यादातर मामलों में आपके दोनों कार्य 'तेजी से पर्याप्त' हैं (या दोनों कुछ मामलों में 'बहुत धीमे' हैं) इसलिए उनके बीच कोई वास्तविक अंतर नहीं है।

संबंधित मुद्दे