while 루프 + 스택을 사용한 재귀 트리 작성

Question

나는이 사실을 인정하기 위해 약간 당황 스럽지만 간단한 프로그래밍 문제가 무엇인지에 의해 꽤 난처한 것처럼 보입니다. 의사 결정 트리 구현을 구축하고 있으며 재귀를 사용하여 레이블이 지정된 샘플의 목록을 가져 왔으며 반복적으로 목록을 반으로 분할하고이를 트리로 전환했습니다.

불행히도 깊은 나무가 쌓여 스택 오버플로 오류 (하!)가 발생합니다. 따라서 첫 번째 생각은 연속을 사용하여 꼬리 재귀로 바꾸는 것입니다. 불행히도 스칼라는 이러한 종류의 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과 프로그램 카운터가 내게 재귀 적 솔루션에 대해 명시 적으로 처리해야한다는 것을 알게되었다. 그러나 나는 계속적으로 문제가있다. 이 시점에서 효율성은 거의 없습니다. 단지 궁금합니다. 조기 최적화가 모든 악의 뿌리이고 트램펄린 기반 솔루션이 잘 작동 할 것이라는 점을 상기시켜주십시오. 아마도 그럴 것입니다. 이것은 기본적으로 자신을위한 퍼즐입니다.

누군가 이런 종류의 표준적인 while-loop-and-stack-based 솔루션이 무엇인지 말해 줄 수 있습니까?

업데이트 : 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입니다. "아래로"할 때, 당신은 잎에 닿기 위해 아직도 쪼개어 져야 할 토드의 모음을 유지합니다. 만 잎을했으면, 위로 이동하기로 결정 노드 구축 (배열에 오른쪽에서 왼쪽으로) :

업데이트 : A는 또한 가지하는 int 저장 기능을 지원하는 버전을 정리 (유형 매개 변수 B), 더 기능적/완전 순수하고 론 (ron)이 제안한대로지도가있는 희소 한 나무를 지원합니다.

업데이트 2-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)