performance - coursera progfun1 : scala union performance

Question

在完成“Scala 中的函数式编程原则”@coursera 类(class)第 3 周的作业时，我发现当我实现视频类(class)中所示的函数联合时:

  override def union(that: TweetSet): TweetSet = {
    left union(right) union(that) incl(elem)
  }

在执行过程中花费的时间太长，但是当我以这种方式实现它时:

  override def union(that: TweetSet): TweetSet = {
    right.union(left.union(that)).incl(elem)
  }

在执行过程中花费的时间更少，我得到了满分。

问题是我无法弄清楚这两个实现之间有什么区别，一个比另一个更快？

为赋值给出的代码(带有所用数据结构的实现)是:

package objsets

import TweetReader._

/**
 * A class to represent tweets.
 */
class Tweet(val user: String, val text: String, val retweets: Int) {
  override def toString: String =
    "User: " + user + "\n" +
    "Text: " + text + " [" + retweets + "]"
}

/**
 * This represents a set of objects of type `Tweet` in the form of a binary search
 * tree. Every branch in the tree has two children (two `TweetSet`s). There is an
 * invariant which always holds: for every branch `b`, all elements in the left
 * subtree are smaller than the tweet at `b`. The elements in the right subtree are
 * larger.
 *
 * Note that the above structure requires us to be able to compare two tweets (we
 * need to be able to say which of two tweets is larger, or if they are equal). In
 * this implementation, the equality / order of tweets is based on the tweet's text
 * (see `def incl`). Hence, a `TweetSet` could not contain two tweets with the same
 * text from different users.
 *
 *
 * The advantage of representing sets as binary search trees is that the elements
 * of the set can be found quickly. If you want to learn more you can take a look
 * at the Wikipedia page [1], but this is not necessary in order to solve this
 * assignment.
 *
 * [1] http://en.wikipedia.org/wiki/Binary_search_tree
 */
abstract class TweetSet {

  /**
   * 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 filterAcc(p: Tweet => Boolean, acc: TweetSet): TweetSet = ???

  /**
   * 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 filterAcc(p: Tweet => Boolean, acc: TweetSet): TweetSet = ???


  /**
   * 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)
  }
}

trait TweetList {
  def head: Tweet
  def tail: TweetList
  def isEmpty: Boolean
  def foreach(f: Tweet => Unit): Unit =
    if (!isEmpty) {
      f(head)
      tail.foreach(f)
    }
}

object Nil extends TweetList {
  def head = throw new java.util.NoSuchElementException("head of EmptyList")
  def tail = throw new java.util.NoSuchElementException("tail of EmptyList")
  def isEmpty = true
}

class Cons(val head: Tweet, val tail: TweetList) extends TweetList {
  def isEmpty = false
}


object GoogleVsApple {
  val google = List("android", "Android", "galaxy", "Galaxy", "nexus", "Nexus")
  val apple = List("ios", "iOS", "iphone", "iPhone", "ipad", "iPad")

    lazy val googleTweets: TweetSet = ???
  lazy val appleTweets: TweetSet = ???

  /**
   * A list of all tweets mentioning a keyword from either apple or google,
   * sorted by the number of retweets.
   */
     lazy val trending: TweetList = ???
  }

object Main extends App {
  // Print the trending tweets
  GoogleVsApple.trending foreach println
}

Answer 1

我发了说明 here

这是它的内容:

一些符号:

根:树的根元素。
Left/Right :如果我们谈到联合，则为左/右树，如果我们谈到“包括左”，则为元素

A. (left union (right union (other incl elem))) 的含义

第一:您将当前访问的节点包含在其他节点中(这会探索树，沿着右叶向下，并将您的项目添加到其他节点。无需在其中调用 union)

第二:您使用正确的子树重复该步骤。

第三:您对左子树重复该步骤。

全局含义:每次，您将当前元素添加到其他元素，然后尝试向右移动。如果可以，将正确的元素添加到其他元素，然后再添加一次，直到不能正确为止。然后，你试着向左走……你可以吗？再往右走!你不能吗？左边也不能走？回溯。

您可以将其视为“优先运动”。每次添加您的项目时，您都会根据喜好向右，然后向左，然后返回并重复!通过这样做，您只需探索整个树一次，并且为每个节点将其添加到其他节点!

B. ((left union right) union other) incl elem (or left union right union other) 的含义

只是哈哈。简而言之，您想添加您拥有的当前项目，您可以立即添加，在最后一步可能。但这还不是最糟糕的部分。当您调用 (left union right) 时，您现在将左项添加到右子树，与之前所做的一样低效。这意味着:您尚未将 elem 包含到 other 中，但您必须将 left.item 包含到 right 中。然后，由于您将调用 (left.left union left.right)，因此必须将 left.left.item 包含到 left.right .. 每次执行 A.union(B) 时，都会通过复制删除 A 的一项它完全(而不是像 incl 方法返回的不可变集那样的智能副本)，然后将其添加到 B。但是由于删除 A 的项目需要调用 A.left.union(A.right)，您将首先拥有复制 A.left/A.right ... 等等。如果您可以想象一棵树，就像将每个左兄弟收集到其右兄弟，并且每次您只想将一个项目添加到另一个项目。

一些注意事项:

如果你可以说一个 empty.union(that) = that，你可以说 NonEmpty.union(that : TweetSet) = 如果那是空的那么 this then (((union ... ) .. ) other incl elem) .这就是方法和这种 Empty/NonEmpty 模式的问题，你不能将这两个基本情况集中在一个方法中，在这里，我们很多人在 empty 中实现了第一个，但在 NonEmpty 中忘记了另一个。始终确保如果 A.f(b) 是对称的 (= b.f(A))，则您实现了两种基本情况
确定并直接进入您的基本案例。然后，从它递归到您的全局解决方案。对于“left union right union other incl elem”，基本情况是other incl elem，因为您不想在最后替换为“Empty incl n1 incl n2 incl ...”。所以直接关注它，(其他包括元素)。
最后，但更重要的是:直觉!!!使用非常简单的案例，例如，如果您对我在这里的解释有困难，请想象“复制”方法的相同参数，您可以将其写为 (left copy right) incl elem 或 (left copy (right incl elem))。通过像这样的简单示例，您可以更轻松、更快速地使用替换，了解为什么某些解决方案比其他解决方案糟糕得多!
希望它会帮助一些!如果你有意见，告诉我!