級聯迭代

Question

的我看到了「編程在斯卡拉」第24章「深度集合」這個例子。這個例子顯示了兩種可選的方式來實現一棵樹：

1. 通過延長Traversable[Int] - 這裏的def foreach[U](f: Int => U): Unit複雜性將是O(N)。

2. 通過延伸Iterable[Int] - 在這裏複雜的def iterator: Iterator[Int]將是O(N log(N))。

這是爲了證明爲什麼它會是有幫助的兩個獨立的特質，Traversable和Iterable。

sealed abstract class Tree 
    case class Branch(left: Tree, right: Tree) extends Tree 
    case class Node(elem: Int) extends Tree 

    sealed abstract class Tree extends Traversable[Int] { 
    def foreach[U](f: Int => U) = this match { 
    case Node(elem) => f(elem) 
    case Branch(l, r) => l foreach f; r foreach f 
    } 
    } 

    sealed abstract class Tree extends Iterable[Int] { 
    def iterator: Iterator[Int] = this match { 
     case Node(elem) => Iterator.single(elem) 
     case Branch(l, r) => l.iterator ++ r.iterator 
    } 
    } 

關於foreach實施他們說：

遍歷平衡樹需要的時間與樹 元素的數量。要看到這一點，考慮到對於平衡樹 與N葉，你將有N - 1類Branch的內部節點。因此， 遍歷樹的步驟總數爲N + N - 1。

這是有道理的。 :)

然而，他們提到在iterator方法的兩個迭代的級聯有時間的log(N)複雜，因此該方法的總的複雜性將是N log(N)：

元件被產生每次通過級聯迭代器（如 l.iterator ++ r.iterator），計算需要間接地沿着一個 以得到右迭代器（l.iterator或 r.iterator）。總體而言，這使得log(N)間接尋找具有N片樹葉的平衡樹的葉子 。因此，即使瀏覽樹中的所有元素的成本約2N的foreach遍歷方法走到N log(N)與iterator遍歷。

????

爲什麼的級聯迭代需要計算得到的左側或右側迭代器的葉子？

Answer 1

在此實現中，最頂端的分支不知道left和right子分支中有多少個元素。

因此，迭代器與鴻溝遞歸建成並征服的做法，是在iterator方法上清楚地表示 - 你到每一個節點（case Branch），你生產的單個節點case Node => ...的迭代器，然後你加入他們。如果不進入每個節點，它不知道有哪些元素以及樹是如何構造的（奇數分支允許而不允許等）。

編輯： 讓我們來看看Iterator的++方法。

def ++[B >: A](that: => GenTraversableOnce[B]): Iterator[B] = new Iterator.JoinIterator(self, that) 

，然後在Iterator.JoinIterator

private[scala] final class JoinIterator[+A](lhs: Iterator[A], that: => GenTraversableOnce[A]) extends Iterator[A] { 
    private[this] var state = 0 // 0: lhs not checked, 1: lhs has next, 2: switched to rhs 
    private[this] lazy val rhs: Iterator[A] = that.toIterator 
    def hasNext = state match { 
     case 0 => 
     if (lhs.hasNext) { 
      state = 1 
      true 
     } else { 
      state = 2 
      rhs.hasNext 
     } 
     case 1 => true 
     case _ => rhs.hasNext 
    } 
    def next() = state match { 
     case 0 => 
     if (lhs.hasNext) lhs.next() 
     else { 
      state = 2 
      rhs.next() 
     } 
     case 1 => 
     state = 0 
     lhs.next() 
     case _ => 
     rhs.next() 
    } 

    override def ++[B >: A](that: => GenTraversableOnce[B]) = 
     new ConcatIterator(this, Vector(() => that.toIterator)) 
    } 

從此我們可以看出，加入迭代器只是會在rhs領域的遞歸結構。此外，讓我們更多地關注它。 考慮具有結構的偶數樹level1 [A]; level2 [B][C]; level 3[D][E][F][F]

當您在迭代器上調用JoinIterator時，您將保留現有的lhs迭代器。然而，你總是.toIterator在rhs。這意味着對於每個後續級別，rhs部分將被重建。因此對於B ++ C，您會看到A.lhs (stands for B)和A.rhs (stands for C.toIterator)，其中C.toIterator代表C.lhs and C.rhs等。因此，增加了複雜性。

我希望這能回答你的問題。

Answer 2

關於「收集深度」的雙關語是恰當的。數據結構的深度很重要。

當你調用top.iterator.next()，每個內部Branch委託給Branch或Node低於它，這是log(N)調用鏈的迭代器。

您在每個next()上產生該呼叫鏈。

使用foreach，您只需訪問Branch或Node一次。

編輯：不知道這是否有幫助，但這是一個熱切地尋找葉片但懶惰地產生值的例子。它會在舊版本的Scala中疊加或者更慢，但是鏈接++的實現得到了改進。現在它是一個扁平鏈，因爲它被消耗而變短。

sealed abstract class Tree extends Iterable[Int] { 
    def iterator: Iterator[Int] = { 
    def leafIterator(t: Tree): List[Iterator[Int]] = t match { 
     case Node(_) => t.iterator :: Nil 
     case Branch(left, right) => leafIterator(left) ::: leafIterator(right) 
    } 
    this match { 
     case n @ Node(_) => Iterator.fill(1)(n.value) 
     case Branch(left @ Node(_), right @ Node(_)) => left.iterator ++ right.iterator 
     case b @ Branch(_, _) => 
     leafIterator(b).foldLeft(Iterator[Int]())((all, it) => all ++ it) 
    } 
    } 
} 

case class Branch(left: Tree, right: Tree) extends Tree { 
    override def toString = s"Branch($left, $right)" 
} 
case class Node(elem: Int) extends Tree { 
    def value = { 
    Console println "An expensive leaf calculation" 
    elem 
    } 
    override def toString = s"Node($elem)" 
} 

object Test extends App { 
    // many leaves 
    val n = 1024 * 1024 
    val ns: List[Tree] = (1 to n).map(Node(_)).toList 
    var b = ns 
    while (b.size > 1) { 
    b = b.grouped(2).map { case left :: right :: Nil => Branch(left, right) }.toList 
    } 
    Console println s"Head: ${b.head.iterator.take(3).toList}" 
}