级联迭代
的我看到了“编程在斯卡拉”第24章“深度集合”这个例子。这个例子显示了两种可选的方式来实现一棵树：级联迭代
通过延长
Traversable[Int]- 这里的def foreach[U](f: Int => U): Unit复杂性将是O(N)。通过延伸
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遍历。
????
为什么的级联迭代需要计算得到的左侧或右侧迭代器的叶子？
回答：
在此实现中，最顶端的分支不知道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等。因此，增加了复杂性。
我希望这能回答你的问题。
回答：
关于“收集深度”的双关语是恰当的。数据结构的深度很重要。
当你调用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}"
}
以上是 级联迭代 的全部内容， 来源链接： utcz.com/qa/261259.html
