为什么尾递归不会导致此代码的性能更好？

Question

我正在创建一个更快的字符串分割方法。首先，我编写了一个返回List的非尾部递归版本。接下来，使用ListBuffer然后调用toList的尾部递归(+=和toList为0(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。