为什么尾递归不能在此代码中获得更好的性能？

Question

我正在创建一个更快的字符串拆分器方法.首先,我写了一个非尾递归版本返回List.接下来,尾递归使用ListBuffer然后调用toList(+=并且toList是O(1)).我完全期望尾递归版本更快,但事实并非如此.

有谁能解释为什么？

原始版本:

def split(s: String, c: Char, i: Int = 0): List[String] = if (i < 0) Nil else {
  val p = s indexOf (c, i)
  if (p < 0) s.substring(i) :: Nil else s.substring(i, p) :: split(s, c, p + 1)
}

尾递归:

import scala.annotation.tailrec
import scala.collection.mutable.ListBuffer
def split(s: String, c: Char): Seq[String] = {
  val buffer = ListBuffer.empty[String]
  @tailrec def recurse(i: Int): Seq[String] =  {
    val p = s indexOf (c, i)
    if (p < 0) {
      buffer += s.substring(i)
      buffer.toList
    } else {
      buffer += s.substring(i, p)
      recurse(p + 1)
    }
  }
  recurse(0)
}

这与代码基准这里,其结果在这里,通过#Scala的jyxent.

Answer 1

你只是在第二种情况下做更多的工作.在第一种情况下,您可能会溢出堆栈,但每个操作都非常简单,并且::只需要您可以获得的包装器(您需要做的就是创建包装器并将其指向另一个列表的头部) .在第二种情况下,不仅最初创建一个额外的集合,还必须形成一个闭包s和buffer嵌套方法使用,但你也使用较重的ListBuffer,必须检查它们+=是否已经被复制到列表中,并使用不同的代码路径,具体取决于它是否为空(为了使O(1)附加工作).

Answer 2

由于尾部调用优化，您预计尾递归版本会更快，如果您将苹果与苹果进行比较，我认为这是正确的：

def split3(s: String, c: Char): Seq[String] = {
  @tailrec def recurse(i: Int, acc: List[String] = Nil): Seq[String] =  {
    val p = s indexOf (c, i)
    if (p < 0) {
      s.substring(i) :: acc
    } else {
      recurse(p + 1, s.substring(i, p) :: acc)
    }
  }
  recurse(0) // would need to reverse
}

我将其计时split3得更快，当然，为了获得相同的结果，需要反转结果。

它似乎ListBuffer确实引入了尾递归优化无法弥补的低效率。

编辑：考虑避免相反的情况......

def split3(s: String, c: Char): Seq[String] = {
  @tailrec def recurse(i: Int, acc: List[String] = Nil): Seq[String] =  {
    val p = s lastIndexOf (c, i)
    if (p < 0) {
      s.substring(0, i + 1) :: acc
    } else {
      recurse(p - 1, s.substring(p + 1, i + 1) :: acc)
    }
  }
  recurse(s.length - 1)
}

这具有尾调用优化和避免ListBuffer。