मैंने भी स्काला के साथ एफपी पर कोर्सरा कोर्स लिया है और आपके जैसा ही समस्या है। मैं भी वही कामकाजी समाधान के साथ आया था। यह जानने की कुंजी कि क्यों काम करता है और दूसरा कार्य के पुनरावर्ती अपघटन में नहीं है। सबसे पहले, आइए अपना पहला समाधान देखें जो समाप्त नहीं होता है।
tree.left.left.union(tree.left.right).union(tree.right).incl(tree.left.elem).union(that).incl(tree.elem)
अब हम कर सकते हैं:
tree.left.union(tree.right)).union(that).incl(tree.elem)
के लिए आगे का विस्तार:
val tree = NonEmpty(tweet1, NonEmpty(tweet2, Empty, Empty), NonEmpty(tweet3, Empty, Empty))
val that: TweetSet = ...
tree.union(that)
तक विस्तृत होता:
def union(that: TweetSet): TweetSet = (left union(right)) union(that) incl(elem)
को एक सरल उदाहरण पेड़ और कुछ मनमाने ढंग से पेड़ that का उपयोग करते हैं टी का आह्वान वह खाली TweetSets (tree.left.left और tree.left.right)
tree.right.incl(tree.left.elem).union(that).incl(tree.elem)
अब के लिए काफी दूर तक है कि के आधार पर मामला है, की दूसरी समाधान को देखो।
def union(that: TweetSet): TweetSet = left union(right union(that)) incl(elem)
tree.union(that)
का विस्तार करने के लिए:
tree.left.union(tree.right.union(that)).incl(tree.elem)
फिर का विस्तार करें:
tree.left.union(tree.right.left.union(tree.right.right.union(that)).incl(tree.right.elem)).incl(tree.elem)
tree.right.left और tree.right.right
tree.left.union(that.incl(tree.right.elem)).incl(tree.elem)
के लिए आधार मामले लागू करें प्रत्येक पर एक ही संख्या के चरणों के बाद आप टी देख सकते हैं टोपी हमारे पास बहुत अलग अभिव्यक्तियां हैं।
solution1 = tree.right.incl(tree.left.elem).union(that).incl(tree.elem)
Solution2 = tree.left.union(that.incl(tree.right.elem)).incl(tree.elem)
समाधान 1 में, आप देख सकते हैं कि incl कॉल अगले union की बाईं ओर स्थित होती है:
tree.right.incl(tree.left.elem).union(that).incl(tree.elem)
^^^^
जबकि समाधान 2 में , incl अगले union के दाईं ओर होता है।
tree.left.union(that.incl(tree.right.elem)).incl(tree.elem)
^^^^
तो हम देख सकते हैं कि समाधान 1 पिछले यात्रा से एक कम तत्व के साथ संघ से पहले एक नया पेड़ बनाता है। यह प्रक्रिया पेड़ में हर बाएं शाखा के लिए दोहराई जाएगी जिसे संसाधित किया जाएगा। एक एन^2 दक्षता। स्मृति आवंटन त्रुटि n^2 नए पेड़ बनाने से होती है। समाधान 2 अगले यूनियन के बाईं ओर मौजूदा पेड़ का उपयोग करता है और बेस केस (एन की दक्षता) से नया पेड़ देता है। दिए गए बेस केस के साथ एक कुशल संघ बनाने के लिए, आपको union अभिव्यक्ति के दाहिने तरफ का निर्माण करना होगा क्योंकि बाईं ओर बिल्डिंग के परिणामस्वरूप तेजी से अधिक काम होगा।
मुझे लगता है कि आपके प्रश्न का उत्तर यहां दिया गया है: http://stackoverflow.com/questions/16217304/recursive-set-union-how-does-it-work-really –
ऊपर पोस्ट किया गया लिंक बस समझाएं कि यूनिवर्सिटी कैसे काम करती है। मैं सोच रहा हूं कि यह अक्षम क्यों है और यह स्मृति समस्या प्राप्त करने से क्यों समाप्त होता है। धन्यवाद ! – SaKou