मैं इस क्लोजर फ़ंक्शन को कैसे लिखूं ताकि यह ढेर को उड़ा न सके?

Question

मैं क्लोजर के लिए नया हूं और मुझे लगता है कि अब तक कोड लिखने का मेरा दृष्टिकोण "क्लोजर का तरीका" के अनुरूप नहीं है। कम से कम, मैं ऐसे लेखन कार्य रखता हूं जो बड़े मूल्यों के साथ StackOverflow त्रुटियों तक पहुंचते रहते हैं। मैंने रिकूर ​​का उपयोग करने के बारे में सीखा है जो एक अच्छा कदम आगे बढ़ रहा है। लेकिन, 2500000 जैसे मूल्यों के लिए नीचे दिए गए कार्यों की तरह कार्य कैसे करें?

(defn fib [i] 
    (if (>= 2 i) 
    1 
    (+ (fib (dec i)) 
     (fib (- i 2))))) 

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

किसी भी पॉइंटर्स की बहुत सराहना की जाएगी!

Answer 1

आपको अपना फ़ंक्शन कैसे काम करता है इसका एक मानसिक मॉडल होना चाहिए। आइए मान लें कि प्रत्येक आमंत्रण के लिए पेपर के स्क्रैप का उपयोग करके आप अपने फ़ंक्शन को निष्पादित करते हैं। पहला स्क्रैप, आप (fib 250000) लिखते हैं, फिर आप देखते हैं "ओह, मुझे (fib 249999) और (fib 249998) की गणना करने की आवश्यकता है और अंत में उन्हें जोड़ें", इसलिए आप ध्यान दें और दो नए स्क्रैप शुरू करें। आप पहले को फेंक नहीं सकते हैं, क्योंकि जब आप अन्य गणनाओं को पूरा करते हैं तो अभी भी आपके लिए चीजें होती हैं। आप कल्पना कर सकते हैं कि इस गणना के लिए बहुत सारे स्क्रैप की आवश्यकता होगी।

एक और तरीका शीर्ष पर शुरू नहीं होना है, लेकिन नीचे। आप इसे हाथ से कैसे करेंगे? आप पहली संख्या, 1, 1, 2, 3, 5, 8 और नरकिप से शुरू करेंगे; और फिर हमेशा अंतिम दो जोड़ें, जब तक कि आपने इसे i बार नहीं किया है। आप प्रत्येक चरण में अंतिम दो को छोड़कर सभी संख्याओं को भी फेंक सकते हैं, ताकि आप अधिकतर स्क्रैप का पुनः उपयोग कर सकें।

(defn fib [i] 
    (loop [a 0 
     b 1 
     n 1] 
    (if (>= n i) 
     b 
     (recur b 
       (+ a b) 
       (inc n))))) 

यह भी एक काफी स्पष्ट कार्यान्वयन है, लेकिन कैसे की, क्या की नहीं। यह हमेशा काफी सुरुचिपूर्ण लगता है जब आप केवल एक परिभाषा लिख ​​सकते हैं और यह स्वचालित रूप से एक कुशल गणना में परिवर्तित हो जाता है, लेकिन प्रोग्रामिंग वह परिवर्तन है। अगर कुछ स्वचालित रूप से बदल जाता है, तो यह विशेष समस्या पहले ही हल हो चुकी है (अक्सर एक सामान्य तरीके से)।

सोचते हुए "मैं इस कदम को पेपर पर कदम कैसे उठाऊंगा" अक्सर एक अच्छा कार्यान्वयन होता है।

Answer 2

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

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

उदाहरण के लिए, clojure.contrib.lazy-seqs में एक गैर-पुनरावर्ती कार्यान्वयन पाया जा सकता है। इस समस्या के विभिन्न दृष्टिकोणों की एक पूरी श्रृंखला Haskell wiki पर पाई जा सकती है। कार्यात्मक प्रोग्रामिंग की मूल बातें के ज्ञान के साथ समझना मुश्किल नहीं होना चाहिए।

Answer 3

;;from "The Pragmatic Programmers Programming Clojure" 
(defn fib [] (map first (iterate (fn [[a b]][b (+ a b)])[0N 1N]))) 
(nth (fib) 2500000)