Vectors

目次

ベクタ

リストを処理するアルゴリズムが先頭のみを処理するように注意していればリストはとても効率的です。 リストの先頭に対するアクセス・追加・削除は定数時間しかかかりませんが、 リストの後の方の要素に対するアクセスや変更は、リストの深さに対して線形時間かかります。

ベクタ(Vector)はScala 2.8の新しいコレクション型で、リストのランダムアクセスに対する遅さの解決を目指したものです。 ベクタはリスト内の任意の要素に「実質的に」定数時間でアクセスできます。 リストの先頭に対するアクセスや配列の要素の読み取りよりも大きな定数ですが、それでも定数です。 結果としてベクタを使うアルゴリズムは列の先頭にのみアクセスするよう注意する必要がありません。 任意の場所の要素に対してアクセスや変更ができるため、書きやすくなっています。

ベクタは他の列と同じ様に作成し、変更できます。

scala> val vec = scala.collection.immutable.Vector.empty

vec: scala.collection.immutable.Vector[Nothing] = Vector()

scala> val vec2 = vec :+ 1 :+ 2

vec2: scala.collection.immutable.Vector[Int] = Vector(1, 2)

scala> val vec3 = 100 +: vec2

vec3: scala.collection.immutable.Vector[Int] = Vector(100, 1, 2)

scala> vec3(0)

res1: Int = 100

ベクタは大きな分岐数を持つ木として表現されています。² 木の全てのノードは32個までの要素か、32個までの他のノードを含みます。 32要素までのベクタは1つのノードとして表現できます。 32 * 32 = 1024要素までのベクタは1つの間接参照で表現できます。 2¹⁵要素までならば根から最終的な要素ノードまで2ホップあれば十分であり、 3ホップのベクタなら2²⁰まで、 4ホップのベクタなら2²⁵まで、 5ホップのベクタなら2³⁰まで大丈夫です。 そのため、全ての適当なサイズのベクタは、プリミティブな配列からの選択を高々5回までしか伴いません。 これが要素に対するアクセスが「実質的に定数時間である」と書いた意味です。

ベクタは不変であり、新しいベクタを保持したままベクタの要素を変更できません。 しかし、updatedメソッドを使うと与えられたベクタと1要素のみが異なる新しいベクタを作成できます:

scala> val vec = Vector(1, 2, 3)

vec: scala.collection.immutable.Vector[Int] = Vector(1, 2, 3)

scala> vec updated (2, 4)

res0: scala.collection.immutable.Vector[Int] = Vector(1, 2, 4)

scala> vec

res1: scala.collection.immutable.Vector[Int] = Vector(1, 2, 3)

上記の最後の行が示す通り、updatedの呼び出しは元のベクタvecに対して何の影響もありません。選択と同じように、ベクタの関数的な更新も「実質的定数時間」です。 ベクタの中間にある要素の更新はその要素を含むノードおよびそのノードを指す各ノードを木の根から順にコピーして実施されます。 その結果、関数的な更新はそれぞれが32個の要素またはサブツリーを含むノードを1から5個作成します。 これは確かに変更可能な配列を直接更新するよりは高価ですが、全てのベクタをコピーするよりはずっと安価です。

ベクタは高速でランダムな選択と高速でランダムで関数的な更新のバランスを上手く取るので、 不変な添字付き列の現時点でのデフォルト実装です:

scala> collection.immutable.IndexedSeq(1, 2, 3)

res2: scala.collection.immutable.IndexedSeq[Int] = Vector(1, 2, 3)

続いては: 不変なスタック

Vectors

目次