scala – 是否有可能通过O(1)内存使用,尾调优化来延伸遍历一个递
|
假设我们有一个递归的数据结构,就像一个二叉树.有很多方法来遍历它们,并且它们具有不同的内存使用配置文件.例如,如果我们简单地打印每个节点的值,使用伪代码,如下面的按顺序遍历…
visitNode(node) {
if (node == null) return;
visitNode(node.leftChild);
print(node.value);
visitNode(node.rightChild);
}
…我们的内存使用将是不变的,但由于递归调用,我们将增加调用堆栈的大小.在非常大的树上,这可能会溢出来. 假设我们决定优化调用堆栈大小;假设这种语言能够正确的尾部调用,我们可以将其重写为以下预订遍历方式 visitNode(node,nodes = []) {
if (node != null) {
print(node.value);
visitNode(nodes.head,nodes.tail + [node.left,node.right]);
} else if (node == null && nodes.length != 0 ) {
visitNode(nodes.head,nodes.tail);
} else return;
}
虽然我们永远不会打栈,我们现在将看到堆使用量相对于树的大小线性增加. 假设我们试图懒惰地穿过树 – 这里是我的推理模糊的地方.我认为即使使用基本的懒惰评估策略,我们将以与尾部优化版本相同的速度增长内存.下面是使用Scala的Stream类的一个具体示例,它提供了懒惰的评估： sealed abstract class Node[A] {
def toStream: Stream[Node[A]]
def value: A
}
case class Fork[A](value: A,left: Node[A],right: Node[A]) extends Node[A] {
def toStream: Stream[Node[A]] = this #:: left.toStream.append(right.toStream)
}
case class Leaf[A](value: A) extends Node[A] {
def toStream: Stream[Node[A]] = this #:: Stream.empty
}
虽然只有流的头部被严格评估,但是随着left.toStream.append(right.toStream)被评估,我认为这实际上会评估左和右流的头部.即使没有(由于附加的聪明),我认为递归地构建这个thunk(从Haskell借用一个术语)本质上将以相同的速度增长内存.而不是说“把这个节点放在节点列表中”,我们基本上就是说,“这里有另一个值来评估它会告诉你下一步怎么做”,但是结果是一样的;线性记忆增长. 我可以想到的唯一的策略是避免这种情况在每个节点中都有可变状态,声明已经遍历了哪些路径.这将允许我们有一个透明的函数,它说：“给定一个节点,我会告诉你下一个应该遍历哪一个节点”,我们可以使用它来构建一个O(1)迭代器. 有没有另外一种方法可以完成O(1),最优化遍历二叉树,可能没有可变状态？ 解决方法
正如我在评论中所说,如果树不需要遍历遍历,你可以这样做.这是一个Haskell的例子： data T = Leaf | Node T Int T inOrder :: T -> [Int] inOrder Leaf = [] inOrder (Node Leaf x r) = x : inOrder r inOrder (Node (Node l x m) y r) = inOrder $Node l x (Node m y r) 如果我们假设垃圾收集器将清理刚刚处理的任何节点,这将占用O(1)个辅助空间,因此我们有效地将其替换为右旋转版本.然而,如果我们处理的节点不能立即被垃圾回收,那么最后一个子句可能会在创建一个O(n)个节点之前创建一个叶子. 如果你有父指针,那么它也是可行的.父指针需要可变状态,并且防止子树的共享,因此它们不是真正的功能.如果您代表一个最初(root,nil)的对(cur,prev)的迭代器,那么可以按照here所示执行迭代.但是,您需要一个具有指针比较的语言才能使其工作. 没有父指针和可变状态,您需要维护一些数据结构,至少可以跟踪树的根目录以及如何到达目录,因为在按顺序或后续顺序的某个时刻您需要这样的结构遍历.这样的结构必然需要Ω(d)空间,其中d是树的深度. （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |