scala - 比 acc.reverse:::b 更高效？

Question

我正在对递归函数进行尾部优化。最后，结果将是 acc.reverse::: b。这是 O(n)，因为 reverse 和 :::。有没有更好的性能方法来组合这两个列表？谢谢。

例。合并 List(3, 2, 1) 和 List(4, 5, 6) 到 List(1, 2, 3, 4, 5, 6)

Answer 1

标准库包括 reverse_:::: 方法:

scala> List(3, 2, 1) reverse_::: List(4, 5, 6)
res0: List[Int] = List(1, 2, 3, 4, 5, 6)

这仍然是 O(n)，但避免了对 ::: 的单独调用。

---

只是为了好玩和学习，您可以轻松地将其实现为尾递归函数:

@tailrec
def reverseConcat[A](lefts: List[A], rights: List[A]): List[A] =
  lefts match {
    case Nil => rights
    case head::tail => reverseConcat(tail, head::rights)
  }

或者使用foldLeft:

def reverseConcat[A](lefts: List[A], rights: List[A]): List[A] =
  lefts.foldLeft(rights)((xs, x) => x :: xs)

请注意，reverse_::: 不是使用尾递归实现的；它在幕后使用了一个 var，因此可能会有不同的表现。