联合无限循环scala

Question

我正在学习 scala 并通过在线参加 Odersky 课程。在第三个作业中有一个练习，你必须使用推文集。推文集应该支持的操作之一是 union。也就是说，两个集合之间的并集是一个包含来自两个集合的推文的新集合。

我按如下方式实现了这个操作：

abstract class TweetSet {
   def union(that: TweetSet): TweetSet
   def incl(tweet: Tweet): TweetSet
}

class Empty extends TweetSet {
 def union(that:TweetSet): TweetSet = that
 def incl(tweet: Tweet): TweetSet = new NonEmpty(tweet, new Empty, new Empty)
}

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

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

   def union(that: TweetSet): TweetSet =
    (left union (right union that)) incl elem //:: 1 Okay
   // ((right union left) union that) incl elem //:: 2 Infinite loop
}

我不明白为什么合并集合的顺序很重要。这对我来说真的没有任何意义。我的代码中的第一行工作正常，而第二行导致无限循环。联合操作数的顺序无关紧要，我应该独立于我决定使用哪一行来获得相同的结果。

我使用的顺序是Odersky在其在线讲座中使用的顺序，所以我不明白为什么它在某些情况下会导致死循环。

我认为我的代码中有错误，但我找不到它。任何帮助将不胜感激。

Answer 1

其实不是死循环。这是有限循环，但第二种变体涉及更多操作。

假设

case class Tweet(text: String)

我们可以定义简单的

var unionsCalled = 0

并添加行

unionsCalled += 1

Empty 和 NonEmpty 联合实现

然后运行行

(1 to 30).view map (_.toString) map Tweet map (new NonEmpty(_, new Empty, new Empty)) reduce (_ union _)
println(unionsCalled)

为第一个实现变体提供 unionsCalled 的最终 899 值，为第二个

提供 149489 的最终值

发生这种情况是因为树不平衡。在最坏的情况下，您对 union 单个项目和 n 项目集的算法应该创建新的 n - 1 元素集，然后包含 elem，然后包含 that.elem。有时可能会降级为 2^(n/2)。

要准确实施高效集，您应该在 this article

中搜索链接

我敢于使用最简单的代码 randomized search tree 重新实现您的任务

import scala.util.Random

case class Tweet(text: String)

abstract class TweetSet {
  def union(that: TweetSet): TweetSet
  def rankInsert(tweet: Tweet, rank: Int): TweetSet
  def incl(tweet: Tweet): TweetSet = rankInsert(tweet, Random.nextInt())
  def toList: List[Tweet]
  def depth: Int
}

case object Empty extends TweetSet {
  def depth = 0
  def union(that: TweetSet): TweetSet = that
  def rankInsert(tweet: Tweet, rank: Int) = NonEmpty(tweet, Empty, Empty, rank)
  def toList = List()
}

case class NonEmpty(elem: Tweet, 
                    left: TweetSet, 
                    right: TweetSet, 
                    rank: Int) extends TweetSet {
  lazy val depth = (left.depth max right.depth) + 1
  def attachToParent(tweet: Tweet, rank: Int) = if (tweet.text < elem.text)
    NonEmpty(tweet, Empty, this, rank)
  else NonEmpty(tweet, this, Empty, rank)

  def rankInsert(tweet: Tweet, rank: Int) =
    if (tweet.text == elem.text) this
    else if (rank > this.rank) attachToParent(tweet, rank)
    else if (tweet.text < elem.text) copy(left = left.rankInsert(tweet, rank))
    else copy(right = right.rankInsert(tweet, rank))

  def toList = left.toList ++ (elem :: right.toList)
  def union(that: TweetSet): TweetSet = if (depth > that.depth) that.union(this)
  else (that /: toList)(_ incl _ )
}

object TweetSet {
  def empty: TweetSet = Empty
  def apply(tweets: Tweet*) = (empty /:  tweets)( _ incl _ )
}

联合无限循环scala

union infinite loop scala

recursion

union

scala