पूंछ-पुनरावर्ती कार्य भी तेज नहीं होना चाहिए?

मेरे पास एक निश्चित "तथ्यात्मक" संपत्ति के साथ किसी संख्या की गणना करने के लिए निम्न क्लोजर कोड है। (कोड वास्तव में क्या करता है माध्यमिक है)।पूंछ-पुनरावर्ती कार्य भी तेज नहीं होना चाहिए?

(defn factor-9 
    ([] 
    (let [digits (take 9 (iterate #(inc %) 1)) 
      nums (map (fn [x] ,(Integer. (apply str x))) (permutations digits))] 
     (some (fn [x] (and (factor-9 x) x)) nums))) 
    ([n] 
     (or 
     (= 1 (count (str n))) 
     (and (divisible-by-length n) (factor-9 (quot n 10))))))

अब, मैं TCO में हूँ और महसूस करते हैं कि Clojure केवल पूंछ-प्रत्यावर्तन प्रदान कर सकते हैं स्पष्ट रूप से ऐसा recur कीवर्ड का उपयोग बताया। तो मुझे लगता है कि (पुनरावृत्ति होना फर्क सिर्फ इतना होने के साथ कारक-9 की जगह) करने के लिए कोड फिर से लिख दिया:

(defn factor-9 
    ([] 
    (let [digits (take 9 (iterate #(inc %) 1)) 
      nums (map (fn [x] ,(Integer. (apply str x))) (permutations digits))] 
     (some (fn [x] (and (factor-9 x) x)) nums))) 
    ([n] 
     (or 
     (= 1 (count (str n))) 
     (and (divisible-by-length n) (recur (quot n 10))))))

मेरी जानकारी के लिए, TCO एक डबल लाभ है। पहला यह है कि यह स्टैक को गैर पूंछ-रिकर्सिव कॉल के रूप में भारी रूप से उपयोग नहीं करता है और इस प्रकार इसे बड़े रिकर्सन पर नहीं उड़ाता है। दूसरा, मुझे लगता है कि परिणामस्वरूप यह तेज़ है क्योंकि इसे लूप में परिवर्तित किया जा सकता है।

अब, मैंने बहुत मोटा बेंचमार्क बनाया है और हालांकि दो कार्यान्वयन के बीच कोई अंतर नहीं देखा है। क्या मैं अपनी दूसरी धारणा में गलत हूं या क्या इसे प्राप्त करने के लिए एक चाल का उपयोग कर JVM (जिसमें स्वचालित टीसीओ नहीं है) और recur पर चलने के साथ कुछ करना है?

धन्यवाद।

स्रोत

2011-01-09 Balint Erdi

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

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

प्रारूपण कारणों के लिए, ' हमने इस gist में परीक्षण और परिणाम डाले हैं।

संक्षेप में तुलनात्मक रूप से तुलना करने के लिए, यदि रिकर्सिव टेस्ट 1 है, तो लूपिंग परीक्षण लगभग 0.45 है, और टीसीओ 0.87 के बारे में परीक्षण करता है और रिकर्सिव और टीसीओ परीक्षणों के बीच पूर्ण अंतर लगभग 3ns होता है।

बेशक, सभी बेंचमार्किंग के बारे में चेतावनी लागू होती है।

स्रोत

2011-01-09 22:51:33 hutch

यह दिलचस्प है, मैंने कारक 9 को मापने के लिए मानदंड स्थापित किया है और पाया कि टीसीओ संस्करण वास्तव में गैर-अनुकूलित संस्करण की तुलना में कुछ हद तक धीमा है। Https://gist.github.com/773060 देखें। –

आश्चर्यजनक रूप से (मेरे लिए कम से कम :)) एक साधारण फिबोनाकी गणना के लिए दो संस्करणों की तुलना करते समय अंतर की दुनिया है: https://gist.github.com/773068 –

यह नाटकीय है, है ना? बेंचमार्क की खुशी। कम से कम आपके पास एक दृढ़ तर्क है कि टीसीओ एक बड़ा अंतर बनाता है :-) – hutch

-1

factor-9 (quot n 10) एक and मूल्यांकन करने के बाद और एक or समारोह लौट सकते हैं पहले मूल्यांकन किया जाना है। इस प्रकार यह पूंछ-पुनरावर्ती नहीं है।

स्रोत

2011-01-09 13:17:09 Oswald

अन्य लिस्प्स (जो मुझे संदेह है) की तुलना में क्लोजर में 'और' और' या 'अलग-अलग कार्य करते हैं, यह सच नहीं है। '(और x y)' '(यदि x y false)' और '(या x y)' to '(यदि x true y)' के बराबर होना चाहिए, तो 'y' दोनों मामलों में पूंछ की स्थिति में है। – sepp2k

@ sepp2k इसका मतलब है कि प्रोग्राम को बराबर पूंछ-रिकर्सिव में परिवर्तित किया जा सकता है। लेकिन क्या यह प्रोग्राम खुद को पूंछ-रिकर्सिव बनाता है? यदि हां, तो मैं अपना जवाब कैसे वोट दे सकता हूं? – Oswald

चूंकि मैक्रो-विस्तार संकलन-समय पर होता है और मैक्रो-विस्तार के बाद आपके पास पूंछ-पुनरावर्ती कार्यक्रम होता है, हां यह प्रोग्राम पूंछ-पुनरावर्ती बनाता है। इसके अलावा: यदि आप ऐसी स्थिति में 'रिकूर' का उपयोग करते हैं जो पूंछ नहीं है, तो आपको वास्तव में एक त्रुटि मिलती है। आप अपने उत्तर को कम नहीं कर सकते हैं, लेकिन आप अपने उत्तर के शरीर और टिप्पणियों के बीच "हटाएं" लिंक पर क्लिक करके इसे हटा सकते हैं। – sepp2k

किसी भी कोड को अनुकूलित करते समय, संभावित या वास्तविक बाधाओं से शुरू करना और पहले अनुकूलित करना अच्छा होता है।

मुझे ऐसा लगता है कि कोड के इस विशेष टुकड़ा अपने CPU समय के सबसे अधिक खा रहा है:

(map (fn [x] ,(Integer. (apply str x))) (permutations digits))

और वह किसी भी तरह से TCO पर निर्भर नहीं करता है - यह एक ही तरीके से मार डाला जाता है। इसलिए, इस विशेष उदाहरण में पूंछ कॉल आपको सभी ढेर का उपयोग न करने की अनुमति देगा, लेकिन बेहतर प्रदर्शन प्राप्त करने के लिए, इसे अनुकूलित करने का प्रयास करें।

स्रोत

2011-01-09 13:17:25

मुझे नहीं लगता कि उत्तर सही है। सबसे पहले, क्रमिकता एक आलसी सीक प्रदान करती है ताकि (कुछ ...) का मूल्यांकन केवल आवश्यकतानुसार क्रमपरिवर्तन गणना को ट्रिगर करेगा। दूसरा, कारक 9 के रनटाइम व्यवहार के आधार पर यह प्रासंगिक हो सकता है या नहीं। दूसरी तरफ आप ऑप्टिमाइज़ करने के लिए * क्या * विश्लेषण करने के बारे में सामान्य सलाह सही है। यदि फंक्शन फैक्टर-9 बाधा है, तो टीसीओ या नहीं सवाल केवल स्टैक आकार, और न ही रनटाइम प्रदर्शन का मामला है। – ordnungswidrig

@ordnungswidrig: काफी संभव है। कोड चलाने में असमर्थ होने के कारण, मैंने अभी सबसे संदिग्ध टुकड़ा चुना है। मैं बैलिंट से प्रतिक्रिया के लिए इंतजार करूंगा और फिर इसे आवश्यकतानुसार संपादित करूँगा। बाधाओं की पहचान करने के बारे में सलाह * किसी भी * कोड अनुकूलन समस्या के लिए लागू है। –

गोरान, मुझे लगता है कि ordnungswidrig सही है, परमिटेशन आवश्यकतानुसार प्राप्त किए जाएंगे, लेकिन क्या आपको पता है कि एक प्रोफाइलर क्लोजर होगा, मैं इस धारणा को देख सकता हूं? –

सिर्फ एक गैर-यहूदी याद दिलाते हैं कि clojure कोई TCO

स्रोत

2011-01-09 19:54:54

जो जेवीएम क्लोजर चलता है, उसके पास स्वचालित टीसीओ नहीं होता है लेकिन इसे स्वयं-पुनरावर्तन के लिए करने में धोखा दिया जा सकता है और इसके बारे में 'recur' –

' के साथ स्पष्ट होने पर इसे रिकर नामक लूपिंग निर्माण नहीं होता है। यह वाक्य रचनात्मक रूप से एक पूंछ कॉल जैसा दिखता है हालांकि यह नहीं है क्योंकि इसका उपयोग दोनों लूप और कार्यों के लिए किया जा सकता है। –

+1 इसे इंगित करने वाला एकमात्र व्यक्ति होने के लिए। मैं यह भी जोड़ूंगा कि यहां चर्चाएं पूंछ कॉल के सबसेट के लिए विशिष्ट हैं जो क्लोजर की 'रिकर' संभाल सकती है और आम तौर पर पूंछ कॉल अनुकूलन पर लागू नहीं होती है। –

पूंछ-पुनरावर्ती कार्य भी तेज नहीं होना चाहिए?

उत्तर

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