7

2 つのリストaとがある場合b、これら 2 つ (順序は関係ありません) を効率的な方法で新しいリストに連結するにはどうすればよいでしょうか?

a ::: bとa ++ bが効率的であるかどうか、Scala API からはわかりませんでした。多分私は何かを逃した。

4

1 に答える 1

9

Scala 2.9では、:::（リストに追加）のコードは次のとおりです。

def :::[B >: A](prefix: List[B]): List[B] =
  if (isEmpty) prefix
  else (new ListBuffer[B] ++= prefix).prependToList(this)

一方、++より一般的です。これは、パラメーターを受け取るためです。つまり、 ：CanBuildFromとは異なるコレクションタイプを返すことができます。List

override def ++[B >: A, That](that: GenTraversableOnce[B])(implicit bf: CanBuildFrom[List[A], B, That]): That = {
  val b = bf(this)
  if (b.isInstanceOf[ListBuffer[_]]) (this ::: that.seq.toList).asInstanceOf[That]
  else super.++(that)
}

したがって、リターンタイプがList、の場合、2つは同じように機能します。

これListBufferは、ミューティングビルダーとして使用できるという点で巧妙なメカニズムですが、最終的にはtoListメソッドによって「消費」されます。つまり、最初に（例では）の(new ListBuffer[B] ++= prefix).prependToList(this)すべての要素を順番に追加し、O（| a |）時間を取ります。次に、を呼び出します。これは定数時間の操作です（レシーバー、または、を分解する必要はありません）。したがって、全体の時間はO（| a |）です。prefixaprependToListb

一方、pstが指摘したように、次のようになりますreverse_:::。

def reverse_:::[B >: A](prefix: List[B]): List[B] = {
  var these: List[B] = this
  var pres = prefix
  while (!pres.isEmpty) {
    these = pres.head :: these
    pres = pres.tail
  }
  these
}

したがって、を使用するとa reverse_::: b、これもO（| a |）を使用するため、他の2つの方法よりも効率的ではありません（ただし、リストサイズが小さい場合は、中間ListBuffer作成のオーバーヘッドを節約できます）。

つまり、との相対的なサイズについて知っている場合は、プレフィックスが2つのリストのうち小さい方であることを確認する必要があります。あなたがその知識を持っていない場合、あなたができることは何もありません。なぜなら、aの操作はO（N）を取ります:)absizeList

一方、将来のScalaバージョンでは、このScalaDaysトークVectorで示されているように、連結アルゴリズムが改善される可能性があります。O（log N）時間でタスクを解決することを約束します。

于 2012-07-19T20:10:28.863 に答える