3
我是尾巴优化递归函数。最后,结果将是acc.reverse ::: b
。由于reverse
和:::
,这是O(n)。是否有更好的性能方式来组合这两个列表?谢谢。比acc.reverse更高效::: b?
Ex。结合List(3, 2, 1)
和List(4, 5, 6)
到List(1, 2, 3, 4, 5, 6)
我是尾巴优化递归函数。最后,结果将是acc.reverse ::: b
。由于reverse
和:::
,这是O(n)。是否有更好的性能方式来组合这两个列表?谢谢。比acc.reverse更高效::: b?
Ex。结合List(3, 2, 1)
和List(4, 5, 6)
到List(1, 2, 3, 4, 5, 6)
标准库包括用于此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
,所以可能会有不同的表现。
哈,来自api的非常整齐的方法。它一次完成,甚至表明它在文档中效率更高。 – ferk86