More than 5 years have passed since last update.

MicroAdAdvent Calendar 2018

@b1ueskydragon(Ina)

ScalaのVectorの構造

Last updated at 2019-12-25Posted at 2018-12-07

はじめに

この記事は MicroAd Advent Calendar 2018 8日目の記事です ☕️🌲

ゴール

具体的な使い方というよりは Vector の中身そのものについて広く浅く考えてみます. まずはイメージを掴みたいなと.

Scala の Vector の話からトライ木の利点に触れながら Vector の内部の仕組みについてざっくり考えていけたらと思います.

Traversable から Vector まで継承関係

Vector さん 👀

まず、これらscala.collection.immutableパッケージに定義されているものですので、不変です(今回可変シーケンスに関しては触れません).

要素を直接書き換えることはできず、元のものと異なる新しいものを作ることになります.

Vector のパフォーマンス

こちらのドキュメントを引用しました.

eC に関しては以下の説明がついています.

効率の良い定数時間で操作が行えますが、ベクターの最大長やハッシュキーの分散など、特定条件に依存する可能性があります.

定数時間ということは、データの大きさに関係なく一定時間で操作が行えるということです.
「実質的な定数時間」や「ほぼ定数時間」という表現に関しては、リストの先頭要素へのアクセスでいう定数時間よりはやや大きいが、それでも定数時間であることは間違いないということでしょう.

また、上記表に登場する操作に関しては以下の説明がついています.

head : シーケンスの先頭要素を選択する.
tail : 先頭要素を除いた新しいシーケンスを生成する.
apply : インデクシング.
update : 不変シーケンスにおいては、関数型(副作用の無い)のアップデート
prepend : シーケンスの先頭に要素を追加する操作. 不変シーケンスにおいては既存のシーケンスを修正せず, 新たなシーケンスを生成する.
append : 要素をシーケンスの末尾に挿入する. 不変シーケンスにおいては, 新たなシーケンスを生成する.

要素をシーケンスの任意の位置に挿入するinsertに関しては、可変シーケンスが提供する操作なので、今回は省略します.

要するに、 Vector の場合不変シーケンスの提供する様々な操作が、ほぼ一定時間で行えることになります.

List との比較

一方、List や Stream の方に書いてある L は、データの深さに比例する線形時間、C は eC より速い定数時間を意味しているようです.

先頭要素に対する操作であるhead、tail、prependにおいては定数時間で行えますが、
apply, update, appendにおいては線形時間で行えるため、Vector よりは遅くなります.

そもそもリストを用いた効率の良いアルゴリズムは、先頭要素に着目して処理を行うことが多いと思います.

Vector は広くて浅い木構造

では、なぜ Vetor は上記操作において「実質的に一定時間」で行えるのでしょうか🤔
(と、ふと思ったことが今回の記事を執筆するきっかけにもなりました)

あのS本の言葉を借りてくると、ベクターは「広くて浅い木構造」で表現されます.

こちらはscala.collection.immutable.Vectorに記述されている公式 scaladoc です.

Vector (中略) provides random access and updates in effectively constant time, as well as very fast append and prepend. Because vectors strike a good balance between fast random selections and fast random functional updates, they are currently the default implementation of immutable indexed sequences. It is backed by a little endian bit-mapped vector trie with a branching factor of 32.

最初の１行は、Vector の、ほぼ一定時間での処理といったパフォーマンスそのものについて説明しています.
そこからは、少しずつ読んで行きたいと思います😇

ランダムアクセス

wiki からお図と説明を拝借👀して、
まず random accessという単語に注目します.

端から順番にアクセスするというシーケンシャルアクセスに対して、何らかのアドレス付けによる番号などにより、目的のデータがある場所がわかっていれば、それを直接アクセスできる

目的の場所が見つかるまで順に線形探索を行うのではなく、
あらかじめわかったいる場所情報をもとに、どの場所(またはその値)に対しても一定時間でアクセスできるということになります.

そして Vector の場合、「高速なランダム読み込み」と「高速な関数型更新」の丁度いいバランスを取れていると
(そのためimmutable.IndexedSeqトレイトのデフォルトの実装となっているとか)、
公式 doc にも説明されています.

それはどういうことでしょう.

Vector Trie

backed by a little endian bit-mapped vector trie with a branching factor of 32

肝心なのはこの文章だと思いました🤔後ろから見ていきます.

branching factor

branching factor は 1ノードが持つ子ノードの個数なので、
1ノードあたりに32個の子を持つ bit-mapped vector Trie ということになります.

トライ木 / bit-mapped vector trie

bit-mapped vector trie に関してはこの原文を参考しています.

(この図では2個単位で一つの塊を描いてますが、Scala における実際の Vector Trie は、要素数 32個が一つの塊となっています)

全体的に二分木と似た構造をしていますが、通常の二分木は各々のノード(節)に要素が格納されます.
一方、トライ木の場合、全てのノードに直接データ(要素)を与えるわけではなく、実際のデータは末端ノードである葉に与えられます. さらに、ブランチ(枝)にはキーの情報を持たせます.

シンプルな例で、単語(string)が与えられ、単語を構成する文字(char)をキーとし、その出現頻度をマッピングして構造体を構成していく操作を考えます.

キーを辿って目的の単語に連結できるようにNodeを以下の通りに(多少雑に)定義してみます.
実装は python の例です.

.py

class Node:
    def __init__(self):
        self.children = {} # {char : Node} のマッピング
        self.isEnd = false # その単語の終端なのか
        self.count = 0     # 文字の出現頻度
        ...

上記コードと関係せず、中身を 多少無理をして(いろいろ省略したり変形して) json で表します.
本来なら木構造の図で表すのが無難できれいな気がします.

先に "abc" を記録します. 単語の終わりには $ を入れています.

.json

{"a":
    {"b":
        {"c": "$"
        }
    }
 }

次に "abcd" を記録します.
もとの "abc" が存在するので、それを辿り、新しいキーを記録します.
(abc の c のあと空のキーを入れたのは表現上のバランスのため)

.json

{"a":
    {"b":
        {"c": { "": "$",
                "d": "$"
              }
        }
    }
 }

リトルエンディアン

省略したリトルエンディアン形式の話と繋げます.

まず、エンディアン(バイトオーダ)は２バイト以上の数値データを、コンピュータが記録・転送する際の順番のことでした.

16進数の110022AAを例に

11 | 00 | 22 | AA

2バイト以上のデータを１バイトごとに分割して

AA | 22 | 00 | 11
(AAが n 番目, 22が n+1 番目...)

後ろ(最下位のバイト)から順番に配置・記録する形式がリトルエンディアンです.

Little endian bit-mapped

["one", "two", "four", "six"] を格納する例を考えます
(String というより、相応する数字データという意味で).

2進数にすると [001, 010, 100, 110] です.
最下位ビットから記録するので先に分岐するのも最下位ビットです
(右から数えて1番目のビットが0か1か, 2番目のビットが0か1か, 3番目のビットが0か1かの順で分岐していく).

今回はビットの終わりにはそのビットの値を与えました.

.json

{"1": {"0": {"0": "one"}},
 "0":
     {"1": {"1": "six",
            "0": "two"
           },
      "0": {"1": "four"
           }
     }
}

← 方向で連結して読むと、その値になるように表してみました.

最下位ビットが1なのは001のみ、最下位ビットが0かつ2番目のビットが0なのは100のみなので、"1" と "4" のキーはくっつけて表現しても良いかも、しれません。

.json

{"100": "one",
 "0":
     {"1": {"1": "six",
            "0": "two"
           },
      "01": "four"
     }

}

具体的にこの話をどうように結びつければいいか、悩むところはありますが、一旦は、本質だと思われる「全ノードに直接そのままの値を格納するわけではない」「なにかを共有している」ところだけ押さえて読み進めたいと思います.

Bitmapped Vector Trie

図はこちらから 👀

0から160000までの整数を、5 step 空けて格納している Bitmapped Vector Trie の例です.

Vector が要素を格納するとき、まず先に32長の配列(Array) -- A を作ります.
そして要素数が32に達したら、32長の配列の配列 -- [A] の要素として、先の32長の配列 -- A を配列の配列 -- [A] に格納します.

この作業を繰り返していくことで [50 から 531], [532 から 571] ... と、具体的なデータは32長ずつ木の**末端(葉)**に配置されます.
枝(→)にはそれぞれ末端にある値に辿り着くための情報を持たせます.

さて Vector に登録された要素数(インデックス)を N と置くと、データアクセスにかかる時間は

.math

O(\log_{32}N)

となります.

N がインデックスということは、JVM で扱うインデックスの型は Integer なので、最大登録できる数は 2147483647(== Int.MaxValue) のようです.
ということは、この式の結果は必ず7未満ということで、これがいわゆる「ほぼ」定数時間O(1)とみなされる時間になります.

不変 Vector においての「更新」

原文だともっといろんな例が紹介されていますが、一つ選別して、値の入れ替えの更新の例を持ってきました.

不変な Vector なので、そのまま値を更新することはできません.
あくまでも新しい Vector を作ることになりますが、木全体をそのままいくつもコピーするわけにもいかないので、「効率良くコピーする」ことが求められます.

コピー(新しく作る)の話なので、ここでの「効率の良い」を言い換えると、
「新しく作るパーツ数を最小限に抑える」ことになるでしょうか.

先ほどの図です.
これが 0, 1, 2, 3, 4, 5, 6, 7, 8 の9つの要素をもっている Vector だとみなしちゃいましょう.

先ほど少し触れましたが、この図は最初から2個単位で配列の配列(の配列の配列の...)に格納することを前提としているので、9つの要素だけで深さ4の木になっていますが、実際の Scala では総要素数が32個に満たないと、深さは0のままのはずです.

ここで要素5のみを別要素に入れ替えた新しい Vector を生成する例を考えます.
Scala 目線だと型安全のことがとても気になる例になりますが (もしくは beef は48879なのか)、底にある目的の値までの経路共有に注目します.

値の入れ替えなので、それぞれの Vector の要素数(9)は同じですね.

オレンジ色が「既存の Vector」で、
青色が「既存の Vector から要素5のみを更新した新しい Vector」に該当します.

修正対象外の他の末端にはアクセスできるように、かつ、
修正対象の要素が含まれた末端の配列の 4, 5 には手を出さず、参照もせず、
新しい末端の配列 4, beef を生成し、そこに辿りつくための新しい経路を持つ Vector が生成されたというイメージです.

効率でないと思われる時

要素が32個までの Vector は1個のノードで表現されますが、
単一要素の Vector を作る場合も、わざわざこのノードを形成することになります.

32長さの Array 単位で配列の配列の配列...の間接処理を発生させるので、
仮に33個の要素を持つ Vector の場合は、わざわざ1回分のホップ(間接処理)を挟む形の Vector Trie を構築することになるでしょうか.

こちらの記事では、各データ構造の効率比較を行った表が乗っています (Memory use of Immutable Collections など).

表の数値を参考してみても、非常に小さいサイズの Vector を多く生成してしまう場合は、むしろ Vector Trie の構築など間接処理の方に時間が使われるのはもちろん、スペースの無駄遣いになる恐れがあると考えられます.

おわりまして

Scala のコレクション絡みで木構造に触れられたこと自体で、とても興味深いものでした

調べきれていない話、書ききれていない話が少し残っていますが、
今回は一旦ここまでとまとめたいと思います.

参考

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up