最近のDoubleArrayの性能
DoubleArrayの性能に関して、最近は少し改善されているかも知れませんとあるので、具体的にどれぐらい改善されているのか、少し書いてみます。もちろん、現実逃避です。
まず、DoubleArrayがなんなのかというところから説明をします。DoubleArrayは、簡単に言うとTrieを実現するためのデータ構造の一種です。日本語ではダブル配列と呼ばれているようです。Trieに関しては横着プログラミング 第6回: chatty: 小うるさい端末あたりを読めば良いでしょうか。要するにTreeを表現するためのデータ構造です。使い道はいろいろありますが、辞書的なものに使われることが多いでしょうか。
Trieを単純に実現しようとすると、すごくたくさんメモリを使ってすごく速い実装をするか、速度を多少犠牲にしてメモリ消費量を削減するかの選択を迫られます。多くの場合はメモリを節約しないと使いものにならないので、速度を多少犠牲にしてメモリ消費量を削減します。
DoubleArrayのアルゴリズムは、基本的にはキーの値にしたがってbaseという名前の配列を移動してゆくのですが、その際に移動が可能であるかどうかをcheckという配列を使って確認します。（2つの配列を使うのでDoubleArrayというわけです。）具体的なアルゴリズムに関しては詳しく説明し出すと長いので省略。Trieを実現するための構造としては、他にTernary Search TreeやPatricia Trieなどがあります。
そんなDoubleArrayですが、オリジナルのアルゴリズムは探索は非常に速いもののキーの挿入/削除が非常に遅く、ハッシュ代わりなどに気軽に使うのは難しいものでした。そのため、これまでは一度更新したらほとんど変更がないような、辞書データなどに対して使われてきました。しかし、近年の研究により、キーの挿入/削除に関しても、それなりの改善が行われています。
まず、キーの挿入の速度に関してですが、これはMoritaらの2004年のFast and compact updating algorithms of a double-array structureの方法を適用する事で、だいぶ速くできます。この手法は以下のようなものです。
- キーを挿入する際のボトルネックは、要素が衝突した際に新しい空き要素を探してくるところである（配列の最初から線形に探索してるので、要素数が増えるとすごく時間がかかる。）
- 空き要素の値として、次の空き要素へのインデックスを入れる事で、空き要素の単方向連結リストを作り、空き要素をすぐに探索できるようにする事で、このボトルネックを解消する
拙作ライブラリdaryでこの方法を実装した所、9万3000程度の要素の挿入にかかる時間が0.98秒程度にまで短縮されました。元がどれぐらいだったかを忘れたので何倍だかわかりませんが。論文には「190〜1600倍の高速化である」と書いてありました。また、比較対象として、同条件でglibのハッシュテーブルを試してみた所、かかった時間は0.14秒程度でした。つまり、ハッシュには負けているが、話にならん程遅いという訳でもない、という感じです。
次に、削除に関してはまだ実装してないので実験結果は出せませんが、Oonoらの2003年のA fast and compact elimination method of empty elements from a double-array structureによると、彼らの実装した削除手法は、空間使用効率を非常に高いレベル（彼らの実験結果では100%）に保ったまま、削除にかかる時間を以前の30〜330倍も早くできたそうです。この手法は以下のようなものです。
- キーを削除すると、空き要素が出来る
- 配列を圧縮するために配列の一番後ろの要素を空き要素のところに移動したいが、常に移動が可能であるとは限らない
- そのままでは移動が不可能である場合は、兄弟要素を持たないようなノード（シングルノードという）を移動させて空き要素を作ることで、移動を可能にする
- シングルノードがたくさんない場合にはこの手法は成り立たないが、シングルノードが大量に存在することは実験的にわかっている
新しい手法では、10万個の単語が登録されたDoubleArrayから1万個の単語を削除するのにかかる時間が0.9秒程度（以前のMoritaらの手法では26秒）であると報告しています。（論文にはもっとたくさんの要素を削除した場合に関してもデータがあります。）
まとめると、
- DoubleArrayは動的データ構造が欲しい場合にハッシュ代わりとして使えなくもないが、単に辞書として使うならハッシュを使った方がたぶん性能が良い。
- 静的なTrieが欲しい場合には是非検討してみるべきである
- 動的なTrieが欲しい場合にも検討してみる価値はありそう
という感じでしょうか。他にもメモリ使用量に関する改善などもありますが、今回は速度に関するものを紹介してみました。
ちなみに、現在のdaryにはバグがあるので、使用はお薦めしません。手元では既に直してあるのですが、他の変更を加えてから忙しくていじれなくなってしまったので、今のところ放置状態です。
