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

Question

我有点不好意思承认这一点,但我似乎对应该是一个简单的编程问题感到非常难过.我正在构建一个决策树实现,并且一直使用递归来获取标记样本列表,递归地将列表拆分为一半,然后将其转换为树.

不幸的是,对于深树,我遇到堆栈溢出错误(哈!),所以我的第一个想法是使用continuation将其转换为尾递归.不幸的是,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"函数中处理的,所以我们可以忽略它.代码非常简单!尽管如此,我仍然难以找到一个基于堆栈的解决方案,它不仅仅使用闭包而且有效地变成了蹦床.我知道我们至少要在堆栈中保留少量"参数"框架,但我想避免关闭调用.

我知道我应该在递归解决方案中明确地写出callstack和程序计数器为我处理的内容,但是如果没有continuation,我就很难做到这一点.在这一点上,它几乎没有效率,我只是好奇.所以,请不要提醒我,过早优化是所有邪恶的根源,基于蹦床的解决方案可能会正常工作.我知道它可能会 - 这基本上是一个谜题,它本身就是为了它.

任何人都可以告诉我这种规范的基于循环和堆栈的规范解决方案是什么？

更新:基于Thipor Kong的优秀解决方案,我编写了一个基于while循环/堆栈/哈希表的算法实现,它应该是递归版本的直接转换.这正是我所寻找的:

最终更新:我使用了顺序整数索引,并将所有内容放回到数组而不是地图中以获得性能,添加了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

只需将二叉树存储在数组中，如维基百科所述：对于节点i，左子节点进入2*i+1，右子节点进入2*i+2。当执行“向下”操作时，您会保留一组待办事项，但仍需要将其拆分才能到达叶子。一旦你只有叶子，就向上（在数组中从右到左）构建决策节点：

更新：一个清理版本，还支持存储在分支中的功能（类型参数 B），并且功能更强大/更纯粹，并且支持带有 ron 建议的地图的稀疏树。

Update2-3：经济地使用节点 id 的名称空间并抽象 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)