स्कैला

Question

में स्ट्रीम बनाने के लिए रिकर्सिव विधियां my previous question पर यह एक अनुवर्ती है।

मैं understand के रूप में फिबोनैकी संख्या की गणना के लिए निम्न विधि अक्षम के बाद विधि fib प्रत्येक फाइबोनैचि संख्या के लिए कहा जाता है और हर बार यह कहा जाता है कि यह एक नई धारा बनाता है।

def fib:Stream[Int] = 
    Stream.cons(1, Stream.cons(1, (fib zip fib.tail) map {case (x, y) => x + y}))

दूसरी ओर पूंछ पुनरावर्ती (here के रूप में) विधि पर काफी कुशल लग रहा है और O(1)

def fib(a:Int, b:Int):Stream[Int] = Stream.cons(a, fib(b, a+b));

में प्रत्येक फाइबोनैचि संख्या अब मैं समापन कर रहा हूँ कि पुनरावर्ती तरीकों कि स्ट्रीम बनाने के कुशल हैं की गणना करता है अगर और केवल वे पूंछ रिकर्सिव हैं। क्या यह सही है?

Answer 1

मैं पर Andy के answer में सुधार करने की कोशिश की है देखना चाहते हैं, लेकिन वह काफी इसे किसी न किसी। पहला समाधान धाराओं का एक पिरामिड बना रहा है - प्रत्येक कॉल fibअन्य फाइबोनैकी स्ट्रीम बनाता है, और इनमें से प्रत्येक नई स्ट्रीम स्वयं नई स्ट्रीम तैयार करेगी, और इसी तरह।

स्पष्ट है कि, वहाँ fib करने के लिए तीन धाराओं एक फोन से उत्पन्न कर रहे हैं:

• एक fib zip fib.tail
• एक map द्वारा बनाई में fib zip fib.tail
• एक fib.tail द्वारा बनाई में fib द्वारा बनाई गई (याद रखें, map एक नया संग्रह बनाता है)

चूंकि पहले दो को fib पर कॉल किया गया है, इसलिए वे प्रत्येक तीन स्ट्रीम बनाएंगे, और इसी तरह।

यहाँ एक किसी न किसी तरह यह "तस्वीर" है:

      1 
          1 
      1    2    1 
      1    3  1  2  1 
    1  2  1  5  1  3 1 2 1 
    1  3 1 2 1 8 1 2 1 5 1 3 1 2 1       

और इस पर और पर चला जाता है। मध्यम धारा को उच्चतम धाराओं का उपयोग करके बाएं और दाएं (फिब और fib.tail) पर गणना की जाती है। उनमें से प्रत्येक को पर पर निचले स्ट्रीम का उपयोग करके गणना की जाती है। इन निचली धाराओं में से प्रत्येक को अंतिम पंक्ति पर दिखाए गए धाराओं का उपयोग करके गणना की जाती है।

हम इसे चालू और जारी रख सकते हैं, लेकिन आप देख सकते हैं कि जब तक हमने 8 की गणना की, तब तक हमारे पास पहले से ही 14 अन्य फाइबोनैकी धाराएं चल रही हैं।

आप val को def से बदलते हैं, तो इन सभी नए धाराओं, गायब हो जाते हैं क्योंकि fib और fib.tail एक मौजूदा बजाय नई धाराओं बनाने की धारा के पास भेजेगा। और चूंकि कोई नई स्ट्रीम नहीं बनाई जाएगी, fib और fib.tail पर कोई और कॉल नहीं होगी।

अब, यदि आप दूसरे उत्तर को देखते हैं, तो आप देखेंगे कि एक fib कॉल है, और map या इसी तरह की विधि नहीं है, इसलिए कोई गुणा प्रभाव नहीं है।

Answer 2

नहीं, पूंछ रिकर्सिव स्टैक्लिंग (वैश्विक रूप से) के बजाय कंपाइलर लूपिंग में मदद करना है, यह संकलन समय अनुकूलन है।

समस्या पहले कार्यान्वयन से आई थी जहां fib पर कई कॉल कई स्ट्रीम निर्माण की ओर अग्रसर होते हैं, इसलिए एक ही कैलकुलेशन खत्म हो जाता है।

fib zip fib.tail 
//if we are at the 1000, it will compute million Streams 

आप इसे कोशिश निम्नलिखित

var i = 0 
def fib:Stream[Int] = { 
    i = i + 1 
    println("new Stream : " + i) 
    Stream.cons(1, Stream.cons(1, (fib zip fib.tail) map {case (x, y) => x + y})) 
}