Скажем, что мы имеем рекурсивную структуру данных, как двоичное дерево. Есть много способов пройти его, и у них разные профили использования памяти. Например, если бы мы просто напечатали значение каждого узла, используя псевдокод, например следующее обход в порядке...
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;
}
Хотя мы никогда бы не взорвали стек, теперь мы увидим, что использование кучи увеличивается линейно по отношению к размеру дерева.
Скажем, мы должны были попытаться лениво пройтись по дереву - вот где мои рассуждения размываются. Я думаю, что даже используя базовую ленивую стратегию оценки, мы будем выращивать память с той же скоростью, что и оптимизированная версия tailcall. Вот конкретный пример, использующий класс 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), оптимизированный обход хвостового двоичного дерева двоичного дерева, возможно, без изменчивого состояния?
