scala - 使用 while 循环 + 堆栈编码递归树创建

Question

我有点不好意思承认这一点，但我似乎被一个简单的编程问题难住了。我正在构建一个决策树实现，并且一直在使用递归来获取标记样本列表，递归地将列表分成两半，然后将其变成一棵树。

不幸的是，使用深树时，我遇到了堆栈溢出错误(哈!)，所以我的第一个想法是使用延续将其转换为尾递归。不幸的是，Scala 不支持这种 TCO，因此唯一的解决方案是使用蹦床。蹦床似乎有点低效，我希望有一些简单的基于堆栈的命令式解决方案来解决这个问题，但我很难找到它。

递归版本看起来有点像(简化):

private def trainTree(samples: Seq[Sample], usedFeatures: Set[Int]): DTree = {
  if (shouldStop(samples)) {
    DTLeaf(makeProportions(samples))
  } else {
    val featureIdx = getSplittingFeature(samples, usedFeatures)
    val (statsWithFeature, statsWithoutFeature) = samples.partition(hasFeature(featureIdx, _))
    DTBranch(
      trainTree(statsWithFeature, usedFeatures + featureIdx), 
      trainTree(statsWithoutFeature, usedFeatures + featureIdx),
      featureIdx)
  }
}

所以基本上我根据数据的某些特征递归地将列表分割为两个，并通过一个使用过的特征列表，所以我不重复 - 所有这些都在“getSplittingFeature”函数中处理，所以我们可以忽略它。代码真的很简单!尽管如此，我仍然无法找出一个基于堆栈的解决方案，它不仅使用闭包而且有效地变成了蹦床。我知道我们至少必须在堆栈中保留一些小的“框架”参数，但我想避免闭包调用。

我知道我应该在递归解决方案中明确地写出调用堆栈和程序计数器为我处理的内容，但是我在没有延续的情况下无法做到这一点。在这一点上，它甚至与效率无关，我只是很好奇。所以请不要提醒我，过早优化是万恶之源，基于蹦床的解决方案可能会很好地工作。我知道它可能会 - 这本身就是一个难题。

谁能告诉我这种基于循环和堆栈的规范解决方案是什么？

更新:基于 Thipor Kong 的优秀解决方案，我编写了一个基于 while-loops/stacks/hashtable 的算法实现，它应该是递归版本的直接翻译。这正是我要找的:

最终更新:我使用了连续整数索引，并将所有内容放回数组而不是映射中以提高性能，添加了 maxDepth 支持，最后有一个与递归版本具有相同性能的解决方案(不确定内存使用情况，但我会少猜):

private def trainTreeNoMaxDepth(startingSamples: Seq[Sample], startingMaxDepth: Int): DTree = {
  // Use arraybuffer as dense mutable int-indexed map - no IndexOutOfBoundsException, just expand to fit
  type DenseIntMap[T] = ArrayBuffer[T]
  def updateIntMap[@specialized T](ab: DenseIntMap[T], idx: Int, item: T, dfault: T = null.asInstanceOf[T]) = {
    if (ab.length <= idx) {ab.insertAll(ab.length, Iterable.fill(idx - ab.length + 1)(dfault)) }
    ab.update(idx, item)
  }
  var currentChildId = 0 // get childIdx or create one if it's not there already
  def child(childMap: DenseIntMap[Int], heapIdx: Int) =
    if (childMap.length > heapIdx && childMap(heapIdx) != -1) childMap(heapIdx)
    else {currentChildId += 1; updateIntMap(childMap, heapIdx, currentChildId, -1); currentChildId }
  // go down
  val leftChildren, rightChildren = new DenseIntMap[Int]() // heapIdx -> childHeapIdx
  val todo = Stack((startingSamples, Set.empty[Int], startingMaxDepth, 0)) // samples, usedFeatures, maxDepth, heapIdx
  val branches = new Stack[(Int, Int)]() // heapIdx, featureIdx
  val nodes = new DenseIntMap[DTree]() // heapIdx -> node
  while (!todo.isEmpty) {
    val (samples, usedFeatures, maxDepth, heapIdx) = todo.pop()
    if (shouldStop(samples) || maxDepth == 0) {
      updateIntMap(nodes, heapIdx, DTLeaf(makeProportions(samples)))
    } else {
      val featureIdx = getSplittingFeature(samples, usedFeatures)
      val (statsWithFeature, statsWithoutFeature) = samples.partition(hasFeature(featureIdx, _))
      todo.push((statsWithFeature, usedFeatures + featureIdx, maxDepth - 1, child(leftChildren, heapIdx)))
      todo.push((statsWithoutFeature, usedFeatures + featureIdx, maxDepth - 1, child(rightChildren, heapIdx)))
      branches.push((heapIdx, featureIdx))
    }
  }
  // go up
  while (!branches.isEmpty) {
    val (heapIdx, featureIdx) = branches.pop()
    updateIntMap(nodes, heapIdx, DTBranch(nodes(child(leftChildren, heapIdx)), nodes(child(rightChildren, heapIdx)), featureIdx))
  }
  nodes(0)
}

Answer 1

只需将二叉树存储在一个数组中，如 Wikipedia 所述: 对于节点 i ，左 child 进入2*i+1和右边的 child 在 2*i+2 .在执行“向下”操作时，您保留了一组待办事项，这些待办事项仍然需要拆分才能到达一片叶子。一旦你只有叶子，向上(在数组中从右到左)构建决策节点:

更新:一个清理过的版本，它也支持存储在分支中的特性(类型参数 B)，并且功能更强大/完全纯粹，并且支持带有 ron 建议的 map 的稀疏树。

更新 2-3:经济地使用节点 id 的 namespace 并抽象 id 的类型以允许大树。从 Stream 中获取节点 ID。

sealed trait DTree[A, B]
case class DTLeaf[A, B](a: A, b: B) extends DTree[A, B]
case class DTBranch[A, B](left: DTree[A, B], right: DTree[A, B], b: B) extends DTree[A, B]

def mktree[A, B, Id](a: A, b: B, split: (A, B) => Option[(A, A, B)], ids: Stream[Id]) = {
  @tailrec
  def goDown(todo: Seq[(A, B, Id)], branches: Seq[(Id, B, Id, Id)], leafs: Map[Id, DTree[A, B]], ids: Stream[Id]): (Seq[(Id, B, Id, Id)], Map[Id, DTree[A, B]]) =
    todo match {
      case Nil => (branches, leafs)
      case (a, b, id) :: rest =>
        split(a, b) match {
          case None =>
            goDown(rest, branches, leafs + (id -> DTLeaf(a, b)), ids)
          case Some((left, right, b2)) =>
            val leftId #:: rightId #:: idRest = ids
            goDown((right, b2, rightId) +: (left, b2, leftId) +: rest, (id, b2, leftId, rightId) +: branches, leafs, idRest)
        }
    }

  @tailrec
  def goUp[A, B](branches: Seq[(Id, B, Id, Id)], nodes: Map[Id, DTree[A, B]]): Map[Id, DTree[A, B]] =
    branches match {
      case Nil => nodes
      case (id, b, leftId, rightId) :: rest =>
        goUp(rest, nodes + (id -> DTBranch(nodes(leftId), nodes(rightId), b)))
    }

  val rootId #:: restIds = ids
  val (branches, leafs) = goDown(Seq((a, b, rootId)), Seq(), Map(), restIds)
  goUp(branches, leafs)(rootId)
}

// try it out

def split(xs: Seq[Int], b: Int) =
  if (xs.size > 1) {
    val (left, right) = xs.splitAt(xs.size / 2)
    Some((left, right, b + 1))
  } else {
    None
  }

val tree = mktree(0 to 1000, 0, split _, Stream.from(0))
println(tree)