DoubleArray動的追加版計時(Mersenne Twister利用)
前に少しDoubleArrayの動的追加時(のx-check関数で空き領域を探す際)に乱数を使えば処理速度を大幅に改善できるのでは、というようなことを書いた。
この方法だとメモリ使用量は結構増える(まだ正確には把握していない)が、確かに処理速度は大きく向上する。
また、乱数生成器として、C++に標準で備わっているものではなく、速いと評判の(?)Mersenne Twister(Mersenne Twister Home Page)というライブラリを使ってみたところ、stlのset(gcc-4.2.4)に劣らぬほどの速度がでるようになったので、簡単に比較した結果を載せておく。
比較結果: ソート済みのデータ挿入時間
| doar静的版*1 *2 | doar動的版(rand関数) | doar動的版(MersenneTwister) | std::set | std::tr1::unordered_set |
|---|---|---|---|---|
| 0.267s | 0.596s | 0.208s | 0.369s | 0.140s |
比較結果: 未ソートデータ挿入時間 ※doar静的版は未ソートのデータには使えないので除外
| doar動的版(rand関数) | doar動的版(MersenneTwister) | std::set | std::tr1::unordered_set |
|---|---|---|---|
| 1.084s | 0.442s | 0.311s | 0.138s |
(DoubleArrayにしては)意外なほど速い。
これくらいの速度が出るなら、DoubleArrayの静的版は不要かもしれない。
ただ、乱数を利用した動的追加版には、以下のようなデメリットや注意しなければならない(と思われる)点がある。
- trie構築時のメモリ使用量が多い ※ 静的版より多いのはほぼ確実(現状4〜6倍程度)。もしかしたらstd::setなどと同程度くらいにはできるかもしれない。
- 乱数を使っているので、性能が安定しないかもしれない。
- データ(挿入するキーセット、及び順序)とその時の乱数によって速い時もあれば遅い時もあるかもしれない。メモリ使用量も同様。 ※ ただ、乱数の性質上、(キーセットなどによらず)逆に安定する可能性もあるように思う。
- 少なくとも現時点では、安定した性能が出ることは確認していない。
- BASE、CHECK、TAIL配列は、ファイルに保存する前に、コンパクトに圧縮することを想定しているが、それも含めると、結局は静的版の方が時間が短くて済む(おそらく)。
もし、メモリ使用量の点が解決できるなら、doarでは動的追加版の実装のみを採用しても良いと思うのだが...(というかそうしたいのだが...多分無理っぽい)。
追記(2009/10/17)
念のために補足。
乱数を使わなくても、同程度速度で挿入が可能で、かつメモリ使用量が(もともとのものよりは)少なくて済む方法が分かったので、現在は乱数を使ってない。
その方法を簡単に云えば次のような感じとなる。
- 前提: BASE・CHECK配列の空き領域は、リンクリスト*3で管理する
- x-check関数で要素を調べる際には、リンクリストの先頭の次の要素から調べる ※ for(cur=front->next;; cur=cur->next) ...;
- 空き領域を見つけるまでに、一定数以上の要素を辿った(ループした)場合は、先頭部分の使用が密になっていると判断し、リンクリストの先頭を一つ進める ※ if(loop_count > XXX) front=front->next
- ただし、例外としてx-check関数に渡される遷移文字のリストの要素が一つの場合は、常に先頭から探索を行う。
また別の方法に変わる可能性もなくはないが、少なくともしばらくはこの方法を使っていくと思う。
