scala - acc.reverseよりも効率的:::b？

Question

再帰関数をテール最適化しています。最後に、結果はになりますacc.reverse ::: b。reverseとのため、これはO（n）です:::。2つのリストを組み合わせるより良いパフォーマンスの方法はありますか？ありがとう。

元。組み合わせる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舞台裏で使用するため、パフォーマンスが異なる場合があります。