使用 Scala 进行 N 树遍历导致堆栈溢出 [英] N-Tree Traversal with Scala Causes Stack Overflow

问题描述

我试图从 N 树数据结构返回小部件列表.在我的单元测试中，如果我有大约 2000 个小部件，每个小部件都有一个依赖项，我将遇到堆栈溢出.我认为正在发生的是 for 循环导致我的树遍历不是尾递归.在 Scala 中写这个的更好方法是什么?这是我的功能:

I am attempting to return a list of widgets from an N-tree data structure. In my unit test, if i have roughly about 2000 widgets each with a single dependency, i'll encounter a stack overflow. What I think is happening is the for loop is causing my tree traversal to not be tail recursive. what's a better way of writing this in scala? Here's my function:

protected def getWidgetTree(key: String) : ListBuffer[Widget] = {
  def traverseTree(accumulator: ListBuffer[Widget], current: Widget) : ListBuffer[Widget] = {
    accumulator.append(current)

    if (!current.hasDependencies) {
      accumulator
    }  else {
      for (dependencyKey <- current.dependencies) {
        if (accumulator.findIndexOf(_.name == dependencyKey) == -1) {
          traverseTree(accumulator, getWidget(dependencyKey))
        }
      }

      accumulator
    }
  }

  traverseTree(ListBuffer[Widget](), getWidget(key))
}

推荐答案

它不是尾递归的原因是您在函数内部进行了多次递归调用.要成为尾递归，递归调用只能是函数体中的最后一个表达式.毕竟，重点是它的工作方式类似于 while 循环(因此可以转换为循环).循环不能在一次迭代中多次调用自身.

The reason it's not tail-recursive is that you are making multiple recursive calls inside your function. To be tail-recursive, a recursive call can only be the last expression in the function body. After all, the whole point is that it works like a while-loop (and, thus, can be transformed into a loop). A loop can't call itself multiple times within a single iteration.

要进行这样的树遍历，可以使用队列来转发需要访问的节点.

To do a tree traversal like this, you can use a queue to carry forward the nodes that need to be visited.

假设我们有这棵树:

//        1
//       / \  
//      2   5
//     / \
//    3   4

用这个简单的数据结构表示:

Represented with this simple data structure:

case class Widget(name: String, dependencies: List[String]) {
  def hasDependencies = dependencies.nonEmpty
}

我们有这张地图指向每个节点:

And we have this map pointing to each node:

val getWidget = List(
  Widget("1", List("2", "5")),
  Widget("2", List("3", "4")),
  Widget("3", List()),
  Widget("4", List()),
  Widget("5", List()))
  .map { w => w.name -> w }.toMap

现在我们可以将您的方法重写为尾递归:

Now we can rewrite your method to be tail-recursive:

def getWidgetTree(key: String): List[Widget] = {
  @tailrec
  def traverseTree(queue: List[String], accumulator: List[Widget]): List[Widget] = {
    queue match {
      case currentKey :: queueTail =>        // the queue is not empty
        val current = getWidget(currentKey)  // get the element at the front
        val newQueueItems =                  // filter out the dependencies already known
          current.dependencies.filterNot(dependencyKey => 
            accumulator.exists(_.name == dependencyKey) && !queue.contains(dependencyKey))
        traverseTree(newQueueItems ::: queueTail, current :: accumulator) // 
      case Nil =>                            // the queue is empty
        accumulator.reverse                  // we're done
    }
  }

  traverseTree(key :: Nil, List[Widget]())
}

并测试一下:

for (k <- 1 to 5)
  println(getWidgetTree(k.toString).map(_.name))

印刷品:

ListBuffer(1, 2, 3, 4, 5)
ListBuffer(2, 3, 4)
ListBuffer(3)
ListBuffer(4)
ListBuffer(5)

这篇关于使用 Scala 进行 N 树遍历导致堆栈溢出的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！