我正在优化递归函数。最后,结果将是acc.reverse ::: b
。这是 O(n) 因为reverse
和:::
。有没有更好的性能方式来组合这两个列表?谢谢。
前任。结合List(3, 2, 1)
并 List(4, 5, 6)
_List(1, 2, 3, 4, 5, 6)
我正在优化递归函数。最后,结果将是acc.reverse ::: b
。这是 O(n) 因为reverse
和:::
。有没有更好的性能方式来组合这两个列表?谢谢。
前任。结合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
在幕后使用 a ,因此可能表现不同。