DoubleArray: ソート済みデータからの構築
近況
ここしばらくは、ひたすらC++でDoubleArrayの実装に取り組んでいる。
もともとは、シンプルなものを一つ作って終わりにしようかと考えていたのだが、検索・挿入効率とかメモリ使用量(ファイルサイズ)とか大きい(千万程度)のキーセットに対して効率的な実装とか、小さい(百万未満)のキーセットに対して効率的な実装とか、思いつくままにいろいろ試していたら、なかなか収集がつかなくなってしまい、今に至っている。
で、その結果、なかなか性能の良い(と思う)実装ができつつあるので、それはライブラリにまとめて、SourceForgeのプロジェクトとして管理していこうかと思っている(いまいち使い方が分からないけど)。
というのが近況。
今回は、そのいろいろ試したうち最新(昨日の夜中)の成果(というほどでもない)を書いておく。
ソート済みテキストからのDoubleArray構築
「ソート済みのテキストを使えば、簡単にDoubleArrayが作れる」ということは、前々から知ってはいたのだが、僕がDoubleArrayを勉強する取っ掛かりとした論文が、それとは別の(キーの動的追加が可能な)実装方法を採用していたので、実際にどうすれば簡単に作成できるのかは、知らなかった。
それで今回(挿入速度を上げるために)いろいろ試行錯誤する内に、「ソート済みテキスト云々」の実装方法に(多分)辿りついたわけなのだが、本当に簡単で、しかも挿入・検索・サイズ効率がかなり良いので、少し感動した。
下にそれを実装した部分のソースコードを載せる。
まだ開発中のコードの、しかも断片なので、これだけ見ても何をやっているのか、把握できないとは思うが、build_implメソッド内で、DoubleArrayの構築を行っている。
#include <vector> #include "mmap_t.h" #include "types.h" #include "node_list.h" #include "key_stream.h" // ソート済みテキストからDoubleArrayを作成するクラス class Builder { // KeyStream: char*のインクリメントをラップしたクラス (おおまかに云えば) typedef std::vector<KeyStream> KeyList; public: Builder(const char* filepath) : mm(filepath,true) { // char*の配列(のようなもの)を用意する char *cur = (char*)mm.ptr; const char* end = cur+mm.size; while(cur < end) { keys.push_back(KeyStream(cur)); cur = strchr(cur,'\n'); if(!cur) break; *cur = '\0'; cur++; } } bool save(const char* filepath); void build() { build_impl(0,keys.size(),1); shrink_tail(); // TAIL配列の圧縮 } /***************************/ /* ここでDoubleArrayを作成 */ /* keysは、挿入するキーの配列で、keys[0]が0行目のキーに対応する */ void build_impl(int ky_beg, int ky_end, NodeIndex root_idx) { if(ky_end-ky_beg==1) { // 4] 終端に達したら、TAIL配列に残りを挿入する insert_tail(keys[ky_beg],root_idx); return; } std::vector<unsigned> ranges; CodeList jump_codes; Code prev=0; // 1] root_idxから遷移するコード(文字)を集める for(int i=ky_beg; i < ky_end; i++) { Code cur = keys[i].read(); if(prev != cur) { cs.push_back(cur); prev = cur; ranges.push_back(i); } } ranges.push_back(ky_end); // 2-1] 上の遷移コード群を格納できる場所を探す NodeIndex base_idx = x_check(cs); // 2-2] 遷移コードを書き込む(set_node) // 3] 遷移先(base_idx+遷移文字)を、root_idxとして再帰的に構築を進める for(int i=0; i < jump_codes.size(); i++) build_impl(ranges[i], ranges[i+1], set_node(jump_code[i], root_idx, base_idx)); } private: unsigned x_check(const CodeList& codes, NodeIndex hint=0); NodeIndex set_node(Code code, NodeIndex prev, NodeIndex x_node); void insert_tail(KeyStream in, NodeIndex node); void shrink_tail(); private: mmap_t mm; // 対象のファイルの中身保持用のmmap KeyList keys; // 挿入するキーの配列 NodeList nodes; // BASEとCHCKの配列 Tail tail; // TAIL配列 };
簡単に云えば、build_implメソッドでは、次の四つのことを行っている。
- (trie木の)ルートノードの、子ノードを集める(= 遷移先・遷移文字を集める)
- 子ノードへの遷移情報を確報できる領域を探し(x_check)、書き込む(set_node)
- 各子ノードをルートノードに設定して、1から繰り返す
- もし、子ノードが終端ノードなら、そこで処理を終了する
この方法だと、1の段階で、全ての遷移先(子ノード)が判明しているため、これまでの(common lispによる)実装とは違い、遷移の衝突を扱う必要がなく、高速に挿入が行える。
現時点で、簡単にベンチマークを取ってみたところ*1、挿入速度はgccのstd::tr1::unordered_setの1/2倍程度*2、検索速度はunordered_setの3倍程度、使用メモリはキーの合計サイズとほぼ同じ(2.5M)、となった。
かなり良い結果だと思う*3。unorered_setとの比較では挿入速度で劣るが、std::setとならばDoubleArrayの方が速い。
パフォーマンスに加えて、コードがtrieのアルゴリズムを結構素直に書き記したような感じ*4になっているのも良い(いろいろ制限はあるにせよ)。
さらに
上記のDoubleArray構築方法の、挿入するキーセットが固定ではない場合にも、応用がきく。
前回までに、common lispで実装してきたような、キーの動的追加が可能なDoubleArrayの場合、挿入処理の大部分は、遷移先の衝突の解消に費やされている。
で、衝突が起こった場合に、新たに使える領域を探すのがx_check関数の役目なのだが、通常の場合(?)、x_check関数の実装は、配列の先頭からシラミ潰しに空き領域を探すものとなっている。 ※ その際にリンクリストを用いて、探索を効率的にすることは可能だが、基本的な論点は変わらない
このやり方だと、(結果的に)配列の領域を無駄無く使うことになるので、最終的なサイズや検索効率は良くなるのだが、挿入は遅くなる。 ※ 使用率の高い(= 空きが見つかりにくい)先頭から順に探しているのに加えて、(多分より重要なのは)小さい領域に効率的に(密に)詰め込むため、後続の挿入処理で衝突が起こる可能性自体が高くなってしまうため。 遅いx_check -> 衝突増加 -> 遅いx_check のループ
その解決策(の案)として今試しているのが、x_check関数で先頭からではなくランダムな場所から探索と始めて、かつ、配列は使用領域がある程度増えたら余裕を持ってリサイズする、ということ。これで、挿入処理は(空き領域の確保率が高ければ桁違いに)速くなる。
ただ、これだと配列が疎になり、検索効率も落ちてしまうので、キーの挿入があらかた終了した時点で、今回取り上げた方法で、DoubleArray自体を構築し直す(入力は、ソート済みのキーセットではなく、DoubleArray自身)。
これで、挿入もそこそこ速く、検索も最適化されたDoubleArrayが出来る(はず)。
まあ、これはこれで、メモリの浪費が激しいとか、検索と挿入を交互に行うようなケースでは役に立たないといったような難点はあるのだが、上手く応用すれば便利なのではないかと思い、試している。
