algorithm - 迭代器的连接

Question

我在“Programming in Scala”第 24 章“Collections in depth”中看到了这个例子。此示例显示了实现树的两种替代方法:

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 的实现，他们说:

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 have N - 1 interior nodes of class Branch. So the total number of steps to traverse the tree is N + 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 (either l.iterator, or r.iterator). Overall, that makes log(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 about 2N for the foreach traversal method to N log(N) for the traversal with iterator.

????

为什么级联迭代器的计算需要到达左迭代器或右迭代器的叶子？

Answer 1

“集合深度”的双关语很贴切。数据结构的深度很重要。

当您调用 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}"
}