|
|
|
ベクトル | 目次 |
最新版は Scala Documentation に移行しました。
リストはアルゴリズムが慎重にリストの先頭要素 (head) のみを処理する場合、非常に効率的だ。 head の読み込み、追加、および削除は一定数時間で行われるのに対して、リストの後続の要素に対する読み込みや変更は、その要素の深さに依存した線形時間で実行される。
ベクトル (Vector) は、ランダムアクセス時の非効率性を解決するために Scala 2.8 から導入された新しいコレクション型だ。ベクトルはどの要素の読み込みも「事実上」定数時間で行う。リストの head の読み込みや配列の要素読み込みに比べると大きい定数だが、定数であることには変りない。この結果、ベクトルを使ったアルゴリズムは列の head のみを読み込むことに神経質にならなくていい。任意の場所の要素を読み込んだり、変更したりできるため、コードを書くのに便利だ。
ベクトルは、他の列と同じように作成され、変更される。
| 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 |
ベクトルは分岐度の高い木構造で表される2。全てのノードは 32以下の要素か、32以下の他のノードを格納する。32個以下の要素を持つベクトルは単一のノードで表すことができる。ベクトルは、たった一つの間接呼び出しで、32 * 32 = 1024個までの要素を扱うことができる。木構造の根ノードから末端ノードまで 2ホップで 215個、3ホップで 220個、4ホップで 230個以下までの要素をベクトルは扱うことができる。よって、普通のサイズのベクトルの要素選択は 5回以内の配列選択で行うことができる。要素選択が「事実上定数時間」と言ったのは、こういうことだ。
ベクトルは不変であるため、ベクトルの変更無しにベクトル内の要素を変更することはできない。しかし、updated メソッドを使うことで一つの要素違いの新たなベクトルを作成することができる:
| 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個の ノードを作成することを意味する。これは、可変配列の in-place での上書きに比べると、ずっと時間のかかる計算であるが、ベクトル全体をコピーするよりはずっと安いものだ。
ベクトルは高速なランダム読み込みと高速な関数型更新の丁度いいバランスを取れているため、不変添字付き列 (immutable.IndexedSeq) トレイトのデフォルトの実装となっている:
| scala> collection.immutable.IndexedSeq(1, 2, 3) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| res2: scala.collection.immutable.IndexedSeq[Int] = Vector(1, 2, 3) |
続いては、不変スタック
|
|
|
ベクトル | 目次 |