फ़िल्टर एल्गोरिदम में लापता तर्क

Question

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

नोट कृपया मुझे बेक्ड कोड न दें क्योंकि यह coursera सम्मान कोड का उल्लंघन करेगा। मुझे बस इतना कुछ चाहिए जो मुझे मेरे तर्क को डीबग करने में मदद करेगा और मुझे यह देखने में मदद करेगा कि मैं कहां गड़बड़ कर रहा हूं और परीक्षण क्यों विफल हो जाते हैं।

abstract class TweetSet { 

    def isEmpty: Boolean 
    /** 
    * This method takes a predicate and returns a subset of all the elements 
    * in the original set for which the predicate is true. 
    * 
    * Question: Can we implment this method here, or should it remain abstract 
    * and be implemented in the subclasses? 
    */ 
    def filter(p: Tweet => Boolean): TweetSet 

    /** 
    * This is a helper method for `filter` that propagetes the accumulated tweets. 
    */ 
    def filterAcc(p: Tweet => Boolean, acc: TweetSet): TweetSet 

    /** 
    * Returns a new `TweetSet` that is the union of `TweetSet`s `this` and `that`. 
    * 
    * Question: Should we implment this method here, or should it remain abstract 
    * and be implemented in the subclasses? 
    */ 
    def union(that: TweetSet): TweetSet; 

    /** 
    * Returns the tweet from this set which has the greatest retweet count. 
    * 
    * Calling `mostRetweeted` on an empty set should throw an exception of 
    * type `java.util.NoSuchElementException`. 
    * 
    * Question: Should we implment this method here, or should it remain abstract 
    * and be implemented in the subclasses? 
    */ 
    def mostRetweeted: Tweet = ??? 

    /** 
    * Returns a list containing all tweets of this set, sorted by retweet count 
    * in descending order. In other words, the head of the resulting list should 
    * have the highest retweet count. 
    * 
    * Hint: the method `remove` on TweetSet will be very useful. 
    * Question: Should we implment this method here, or should it remain abstract 
    * and be implemented in the subclasses? 
    */ 
    def descendingByRetweet: TweetList = ??? 


    /** 
    * The following methods are already implemented 
    */ 

    /** 
    * Returns a new `TweetSet` which contains all elements of this set, and the 
    * the new element `tweet` in case it does not already exist in this set. 
    * 
    * If `this.contains(tweet)`, the current set is returned. 
    */ 
    def incl(tweet: Tweet): TweetSet 

    /** 
    * Returns a new `TweetSet` which excludes `tweet`. 
    */ 
    def remove(tweet: Tweet): TweetSet 

    /** 
    * Tests if `tweet` exists in this `TweetSet`. 
    */ 
    def contains(tweet: Tweet): Boolean 

    /** 
    * This method takes a function and applies it to every element in the set. 
    */ 
    def foreach(f: Tweet => Unit): Unit 
} 

class Empty extends TweetSet { 


    def union(that: TweetSet): TweetSet = that 
    def isEmpty = true 

    def filter(p: Tweet=> Boolean): TweetSet = new Empty() 

    def filterAcc(p: Tweet => Boolean, acc: TweetSet): TweetSet = new Empty() 


    /** 
    * The following methods are already implemented 
    */ 

    def contains(tweet: Tweet): Boolean = false 

    def incl(tweet: Tweet): TweetSet = new NonEmpty(tweet, new Empty, new Empty) 

    def remove(tweet: Tweet): TweetSet = this 

    def foreach(f: Tweet => Unit): Unit =() 
} 

class NonEmpty(elem: Tweet, left: TweetSet, right: TweetSet) extends TweetSet { 

    def union(that: TweetSet): TweetSet = (left.union(right)).union(that).incl(elem) 
    val isEmpty = false 

    def filter(p: Tweet => Boolean): TweetSet = filterAcc(p,left.union(right)) 

    def filterAcc(p: Tweet => Boolean, acc: TweetSet): TweetSet = { 
      if(acc.isEmpty) acc 
      else if(p(elem)) {acc.incl(elem); left.filterAcc(p,acc).union(right.filterAcc(p,acc))} 
      else new Empty 


    } 


    /** 
    * The following methods are already implemented 
    */ 

    def contains(x: Tweet): Boolean = 
    if (x.text < elem.text) left.contains(x) 
    else if (elem.text < x.text) right.contains(x) 
    else true 

    def incl(x: Tweet): TweetSet = { 
    if (x.text < elem.text) new NonEmpty(elem, left.incl(x), right) 
    else if (elem.text < x.text) new NonEmpty(elem, left, right.incl(x)) 
    else this 
    } 

    def remove(tw: Tweet): TweetSet = 
    if (tw.text < elem.text) new NonEmpty(elem, left.remove(tw), right) 
    else if (elem.text < tw.text) new NonEmpty(elem, left, right.remove(tw)) 
    else left.union(right) 

    def foreach(f: Tweet => Unit): Unit = { 
    f(elem) 
    left.foreach(f) 
    right.foreach(f) 
    } 
} 

मुझे लगता है कि इस बारे में प्रमुख गलत बात filterAcc के रूप में यह रिटर्न है empty जब कोई भी मामलों लागू होते हैं लेकिन मुझे लगता है मैं वास्तव में और क्या कर सकता है यकीन नहीं है। क्या यह सब कुछ विफल रहता है? यदि हां, तो मुझे इसके आसपास कैसे जाना चाहिए?

अद्यतन इसके अलावा, मैं इस समस्या को इस तरह से हल करने के लिए कोशिश की थी:

def filterAcc(p: Tweet => Boolean, acc: TweetSet): TweetSet = { 
      if(acc.isEmpty) acc 
      else if(p(elem)) {acc.incl(elem); left.filterAcc(p,acc).union(right.filterAcc(p,acc))} 
      else left.filterAcc(p,acc).union(right.filterAcc(p,acc)) 


    } 

इस विधि अब सुनिश्चित करती है कि यदि कुछ भी तो हालत का मिलान नहीं हुआ एक पुनरावर्ती कॉल अभी भी किया जाता है, लेकिन एक ही समय में संचयक वृद्धि नहीं करता है। परीक्षण अभी भी असफल हो जाते हैं। मेरे तर्क की दोष क्या है?

धन्यवाद

@lpiepiora और @Ende Neu सख्त मुझे बताने की कोशिश की के रूप में, एसीसी का प्रारंभिक खाली होना चाहिए। मैंने अभी भी एक संघ का उपयोग कर समाप्त कर दिया है क्योंकि मेरा दिमाग बस इस विचार से ढेर हो गया और मैं इसे बंद नहीं कर सका। कोड का अंतिम भाग यहां दिया गया है:

def filterAcc(p: Tweet => Boolean, acc: TweetSet): TweetSet = { 

    if(left.isEmpty && right.isEmpty) acc 
    else if(p(elem)){ left.filterAcc(p,acc.incl(elem)).union(right.filterAcc(p,acc.incl(elem)))} 
    else left.filterAcc(p,acc).union(right.filterAcc(p,acc)) 


    } 

Answer 1

यह मेरे लिए भी बहुत मुश्किल था।

अपने दृष्टिकोण में समस्याओं में से एक यह है कि आप संचायक सही ढंग से उपयोग नहीं कर रहे हैं, वास्तव में आप सेट संघ गुजर रहे हैं, एक संचायक केवल स्टोर परिणाम चाहिए कि किसी दिए गए विधेय p से मेल खाते हैं, जैसा कि आप एक संचायक इस्तेमाल कर सकते हैं है for या while लूप में, इसे खाली स्ट्रिंग के लिए प्रारंभिक मान (उदाहरण के लिए Int0 के लिए प्रारंभ किया जाना चाहिए)।

उदाहरण के रूप में, मान लीजिए कि आप एक List[Int] है और आप सकारात्मक पूर्णांक की संख्या की गणना करना चाहते हैं:

val list = List(0, -1, -2, 4, 9, -7) 

def countPositive(list: List[Int]): Int = { 
    def loop(list: List[Int], acc: Int): Int = list match { 
    case Nil => acc 
    case head :: tail => { 
     if(head > 0) loop(tail, acc + 1) 
     else loop(tail, acc) 
    } 
    } 
    loop(list, 0) 
} 

इस संचायक के लिए प्रारंभ मूल्य उदाहरण के लिए 0 है, एक ही दृष्टिकोण के लिए इस्तेमाल किया जाना चाहिए filterAcc फ़ंक्शन में संचयक।

जो आप करने की कोशिश कर रहे हैं उसके पास सेट का एक संघ है और फिर उन्हें एक मानक संग्रह के रूप में उपयोग करें जहां आप पुनरावृत्त कर सकते हैं, मुझे लगता है कि समस्या का बिंदु इस तरह की पूरी तरह कार्यात्मक डेटा संरचना को संभालना है, क्या सेट का कोई संग्रह नहीं है लेकिन ऑब्जेक्ट का एक गुच्छा जो किसी भी तरह से जुड़ा हुआ है। यदि आपको व्याख्यान 3.1 पर लगभग 7.20 पर वीडियो याद हैं तो ओडर्सकी दिखाता है कि contains और include संचालन तीन संरचनाओं को संशोधित नहीं करते हैं बल्कि वे एक नया बनाते हैं, मेरी समझ यह है कि यह समस्या की भावना है।

कोड पर वापस, आप इसके बारे में सोच सकता है के रूप में एक संग्रह है कि आप पर recurse कर सकते हैं, मेरे दृष्टिकोण कस्टम tail और head फ़ंक्शन का उपयोग किया गया था, tail मौजूद है यदि आप अगले वस्तु और head जोड़ने के लिए बार-बार दोहराना रख सकते तत्व जो संचयक को भविष्यवाणी को पूरा करते हैं। हर बार जब आप पुन: प्रयास करते हैं तो आप जिस हिस्से को पहले से चेक कर चुके हैं उससे बचने के लिए एक नई तीन संरचना बनाते हैं, तो आप जानते हैं कि NonEmptyisEmpty विधि का उपयोग कर बाएं या तंग तीन के रूप में है।

ध्यान दें कि यह विधि (tail और head) कर सकता है (मेरे कार्यान्वयन में वे कर रहे हैं) पुनरावर्ती हो, बहुत मुश्किल बात यह है कि tail हमेशा नए threes वस्तुओं लौट (के रूप में वीडियो पर दिखाया जब Odersky संरचना पूरी तरह कार्यात्मक को परिभाषित करता है) है ।

एक अन्य सुझाव मैं एक नीचे-ऊपर रणनीति इस्तेमाल करने की कोशिश कर रहा है दे सकते हैं, कि हमेशा बाईं के अंतिम तत्व को recurse है (या सही) जहां तीन सिरों की जाँच करने के left.isEmpty (या right.isEmpty) का उपयोग कर, देखें कि क्या आप head के साथ संचयक में तत्व जोड़ना होगा और फिर tail का उपयोग करके तत्व के बिना एक नया तीन बनाएं।

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

Answer 2

आपकी कक्षा "खाली" फ़िल्टरएसीसी फ़ंक्शन के लिए गलत मान देता है! (इसलिए बहुत अधिक अनावश्यक कोड & मैं एक ही मुद्दे से फंस गया)

यदि आप इसके बारे में सोचते हैं - tweetSet बाइनरी पेड़ हमेशा खाली कक्षाओं के साथ समाप्त हो जाता है - तो खाली वापसी पर फ़िल्टर क्या करना चाहिए?

class Empty extends TweetSet { 
    def filterAcc(p: Tweet => Boolean, acc: TweetSet): TweetSet = ??? 

सुझाव, संकेत -> सूचना है कि संचायक भी खाली वर्ग