performance - 为什么尾递归不会在此代码中产生更好的性能？

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)
}

这是用代码 here 进行基准测试的。 , 结果 here ，由#scala 的 jyxent 提供。

Answer 1

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