foldRight क्षमता?

Question

मैंने सुना है कि अधिकतर परिचालनों में फोल्ड लाइफ्ट अधिक कुशल है, लेकिन स्कैला स्कूल (ट्विटर से) ने निम्नलिखित उदाहरण दिया है। क्या कोई अपनी दक्षता का विश्लेषण कर सकता है और क्या हमें foldLeft का उपयोग करके एक ही ऑपरेशन प्राप्त करना चाहिए?

val numbers = List(1,2,3,4,5,...10) 
def ourMap(numbers: List[Int], fn: Int => Int): List[Int] = { 
    numbers.foldRight(List[Int]()) { (x: Int, xs: List[Int]) => 
    fn(x) :: xs 
    } 
} 

scala> ourMap(numbers, timesTwo(_)) 
res0: List[Int] = List(2, 4, 6, 8, 10, 12, 14, 16, 18, 20) 

Answer 1

जैसा कि आप दस्तावेज़ों से देख सकते हैं, List की फ़ोल्ड राइट और फ़ोल्ड लाइफ विधियों को LinearSeqOptimized में परिभाषित किया गया है। तो स्रोत पर एक नज़र डालें:

override /*TraversableLike*/ 
def foldLeft[B](z: B)(f: (B, A) => B): B = { 
    var acc = z 
    var these = this 
    while (!these.isEmpty) { 
    acc = f(acc, these.head) 
    these = these.tail 
    } 
    acc 
} 

override /*IterableLike*/ 
def foldRight[B](z: B)(f: (A, B) => B): B = 
    if (this.isEmpty) z 
    else f(head, tail.foldRight(z)(f)) 

तो foldLeft थोड़ी देर के पाश का उपयोग करता है और foldRight एक सरल पुनरावर्ती विधि का उपयोग करता। विशेष रूप से यह पूंछ-पुनरावर्ती नहीं है। इस प्रकार foldRight में नए स्टैक फ्रेम बनाने का ओवरहेड है और यदि आप इसे लंबी सूची में आज़माते हैं तो कोशिश करें (उदाहरण के लिए ((1 to 10000).toList :\ 0)(_+_)। बूम! लेकिन यह toList के बिना ठीक काम करता है, क्योंकि Range का foldRight द्वारा काम करता है फोल्डिंग बाएं उलटा)।

तो हमेशा foldLeft का उपयोग क्यों न करें? लिंक्ड सूचियों के लिए, एक दायां गुना तर्कसंगत रूप से एक अधिक प्राकृतिक कार्य है, क्योंकि लिंक्ड सूचियों को रिवर्स ऑर्डर में बनाया जाना चाहिए। आप ऊपर दी गई विधि के लिए foldLeft का उपयोग कर सकते हैं, लेकिन आपको अंत में आउटपुट reverse की आवश्यकता है। (एक बाएं गुना में सूचियाँ को जोड़कर कोशिश मत करो, के रूप में जटिलता O (n-वर्ग है)।)

के रूप में जिसके लिए व्यवहार में तेज है, foldRight या foldLeft + reverse, मैं एक साधारण परीक्षण भाग गया और foldRight है 10 और 40% के बीच सूची के लिए तेज़। यही कारण है कि सूची की foldRight इस तरह से लागू किया गया है।

Answer 2

फ़ोल्ड राइट सूची को उलट देता है और फ़ोल्ड लेफ्ट लागू करता है।