我在“Programming in Scala”第 24 章“Collections in depth”中看到了这个例子。此示例显示了实现树的两种替代方法:
通过扩展
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
的实现,他们说:
traversing a balanced tree takes time proportional to the number of elements in the tree. To see this, consider that for a balanced tree with
N
leaves you will haveN - 1
interior nodes of class Branch. So the total number of steps to traverse the tree isN + N - 1
.
这是有道理的。 :)
但是,他们提到 iterator
方法中两个迭代器的串联具有 log(N)
的时间复杂度,因此该方法的总复杂度为N log(N)
:
Every time an element is produced by a concatenated iterator such as
l.iterator ++ r.iterator
, the computation needs to follow one indirection to get at the right iterator (eitherl.iterator
, orr.iterator
). Overall, that makeslog(N)
indirections to get at a leaf of a balanced tree with N leaves. So the cost of visiting all elements of a tree went up from about2N
for theforeach
traversal method toN log(N)
for the traversal withiterator
.
????
为什么级联迭代器的计算需要到达左迭代器或右迭代器的叶子?
最佳答案
“集合深度”的双关语很贴切。数据结构的深度很重要。
当您调用 top.iterator.next()
时,每个内部 Branch
委托(delegate)给 Branch
或 Node 的迭代器
下面是一个调用链,它是log(N)
。
您在每个 next()
上都会产生该调用链。
使用 foreach
,您只需访问每个 Branch
或 Node
一次。
编辑:不确定这是否有帮助,但这是一个急切定位叶子但延迟生成值的示例。它会在旧版本的 Scala 中出现 stackoverflow 或变慢,但是链式 ++
的实现得到了改进。现在它是一条扁平链,随着它的消耗而变短。
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}"
}
关于algorithm - 迭代器的连接,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/38713347/