whileループ+スタックを使用した再帰的なツリー作成のエンコード

Question

これを認めるにはちょっと恥ずかしいですが、単純なプログラミング上の問題ではないかと思われます。私はデシジョンツリーの実装を構築しており、再帰を使ってラベル付きサンプルのリストを取得し、再帰的にリストを半分に分割し、それをツリーに変換しています。

残念なことに、深い木ではスタックオーバーフローエラー（ha！）が発生するため、最初の考えでは継続を使用して末尾再帰にしていました。残念ながら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"関数で処理されるので、無視することができます。コードは本当に簡単です！それでも、クロージャを使用してトランポリンになるスタックベースのソリューションを見つけ出すのに問題があります。私は少なくとも、スタック内の引数の "フレーム"を少しでも保持しなければならないことは知っていますが、私はクロージャ呼び出しを避けたいと思います。

私は、呼び出しスタックとプログラムカウンタが暗黙のうちに再帰的な解決法で何を処理するのかを明示的に書くべきですが、私はそれを続行することなく問題を抱えています。この時点では効率についてさえほとんど問題ではありません。ただ興味があります。だから、時期尚早最適化がすべての悪の根源であり、トランポリンベースのソリューションがうまくいくことを私に思い出させる必要はありません。私はおそらくそれを知っています - これは基本的にそれ自身のためのパズルです。

標準的なwhileループとスタックベースの解決策は誰にでも分かりますか？

更新：Thipor Kongの優れたソリューションに基づいて、再帰バージョンの直接変換であるアルゴリズムのwhile-loops/stacks/hashtableに基づく実装をコーディングしました。

最終更新日：私はシーケンシャルな整数インデックスを使用し、パフォーマンスのためにマップの代わりにすべてを配列に戻し、maxDepthサポートを追加し、最後に同じものを持つソリューションを用意しましたWikipediaに説明するように

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になります。 「ダウン」するときは、まだ葉に到達するために分割する必要があるトードルのコレクションを保持します。葉が1つだけ得られたら、（配列の右から左に）上向きに移動して決定ノードを構築します。

更新：更新されたバージョンは、ブランチに格納された機能もサポートしますパラメタB）、それはもっと機能的である/完全に純粋であり、ronによって提案されるようなマップで疎木をサポートする。

Update2-3：ノードアイデンティティと抽象型のIDのためのネームスペースを経済的に使用して、大きなツリーを使用できるようにします。ストリームからノー​​ド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)