为什么尾递归在这段代码中没有带来更好的性能？

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。