LOUDS++(7): trie - 比較
七回目。多分最後。
これまで作ってきたものを他のtrie実装と比較する。
比較対象
比較内容
以下の二つの項目の比較を行う。
- trie用のバイナリデータのサイズ
- キー検索速度
データ
比較に用いるtrieのキーセットとしては、Wikipediaのタイトルを利用することにする。
以下、取得/作成手順。
# /tmp/に移動 $ cd /tmp # Wikipediaのタイトルリストをダウンロード $ wget http://download.wikimedia.org/jawiki/20100607/jawiki-20100607-all-titles-in-ns0.gz $ wget http://download.wikimedia.org/euwiki/20100612/euwiki-20100612-all-titles-in-ns0.gz $ wget http://download.wikimedia.org/zhwiki/20100612/zhwiki-20100612-all-titles-in-ns0.gz $ wget http://download.wikimedia.org/fiwiki/20100620/fiwiki-20100620-all-titles-in-ns0.gz $ wget http://download.wikimedia.org/frwiki/20100614/frwiki-20100614-all-titles-in-ns0.gz $ wget http://download.wikimedia.org/svwiki/20100620/svwiki-20100620-all-titles-in-ns0.gz $ wget http://download.wikimedia.org/trwiki/20100620/trwiki-20100620-all-titles-in-ns0.gz $ wget http://download.wikimedia.org/hewiki/20100620/hewiki-20100620-all-titles-in-ns0.gz $ wget http://download.wikimedia.org/nowiki/20100619/nowiki-20100619-all-titles-in-ns0.gz $ wget http://download.wikimedia.org/cawiki/20100619/cawiki-20100619-all-titles-in-ns0.gz $ gzip -d *-ns0.gz # ソート & ユニーク $ cat *-ns0 | LC_ALL=C sort | LC_ALL=C uniq > wiki.title # wiki.titleという名前でキーセットを保存 # 行数 $ wc -l wiki.title 5340378 wiki.title # 約500万行 # サイズ $ ls -lh wiki.title -rw-r--r-- 1 user user 103M 2010-06-20 21:22 wiki.title
検索用データには、'wiki.title'をランダムに並び替えたものを用いる。※ このため検索は常に成功となる
# ファイル名: shuffle.rb # # 引数で指定されたファイルの各行をランダムに並び替えて出力する titles = open(ARGV[0]).read.split("\n") def swap(ary, x, y) tmp = ary[x]; ary[x] = ary[y]; ary[y] = tmp end titles.size.times {|i| swap(titles, i, rand(titles.size)) } puts titles.join("\n")
# wiki.titleをランダムに並び替える $ ruby shuffle.rb wiki.title > wiki.title.rand
構築/検索方法
各trieのデータの作成/検索方法。
検索用のコマンドに関しては、末尾の「比較用検索プログラム」を参照のこと。
$ echo $PWD /tmp # louds-trie $ mklouds-trie wiki.title louds-trie.idx # 作成 $ cklouds-trie louds-trie.idx wiki.title.rand # 検索 # louds-trie-tail $ mklouds-trie-tail wiki.title louds-trie-tail.idx # 作成 $ cklouds-trie-tail louds-trie-tail.idx wiki.title.rand # 検索 # doar $ mkdoar --conc-static doar.idx wiki.title # 作成 $ ckdoar doar.idx wiki.title.rand # 検索 # tx $ txbuild wiki.title tx.idx # 作成 $ cktx tx.idx wiki.title.rand # 検索 # darts $ mkdarts wiki.title darts.idx # 作成 $ ckdarts darts.idx wiki.title.rand # 検索
結果
| データサイズ | 検索所要時間(秒) | |
| louds-trie | 74MB | 32.1372s |
| louds-trie-tail | 52MB | 17.0782s |
| doar | 94MB*1 | 3.19229s |
| tx | 67MB | 51.556s |
| darts | 416MB | 3.35106s |
※ ただし、条件を厳密に合わせている訳ではないので、あまり正確なことは云えない
LOUDSを利用したtrie実装は、やはりDoubleArrayのそれよりも検索が低速だった(漠然と予想していた程ではなかったけど)。
ただlouds-trie-tail(及びlouds-trie)の検索メソッド周りはまだ改良の余地があると思うので、もし今後の改良*2によって、DoubleArray版の三倍程度(の遅さ)にまで差を縮めることができたら、LOUDS(LOUDS++)によるtrie実装の、サイズと検索速度のトレードオフは結構リーズナブルなものになるのではないか、と思う。
比較用検索プログラム
キー検索用の各プログラム。
ckdoarに関しては、doarビルド時に作成されるコマンドを用いた。※ 他のコマンドの命名規則は、これに合わせた
参照: read_line.h, gettime関数
cklouds-trie:
/*** * ファイル名: cklouds-trie.cc * コンパイル: g++ -O3 -o cklouds-trie cklouds-trie.cc */ #include <iostream> #include "louds_trie.h" #include "read_line.h" #include "gettime.h" int main(int argc, char** argv) { LoudsTrie lt(fopen(argv[1],"rb")); ReadLine rl(argv[2]); double beg_t = gettime(); unsigned err = 0; unsigned cnt = 0; const char* line; while((line=rl.read())) { cnt++; if(lt.find(line) == lt.NOT_FOUND) err++; } std::cerr << "Not Found: " << err << "/" << cnt << std::endl; std::cerr << "Elapsed: " << gettime()-beg_t << " sec" << std::endl << std::endl; std::cerr << "DONE" << std::endl; return 0; }
cklouds-trie-tail:
/*** * ファイル名: cklouds-trie-tail.cc * コンパイル: g++ -O3 -o cklouds-trie-tail cklouds-trie-tail.cc */ #include <iostream> #include "louds_trie_tail.h" #include "read_line.h" #include "gettime.h" int main(int argc, char** argv) { LoudsTrieTail lt(fopen(argv[1],"rb")); ReadLine rl(argv[2]); double beg_t = gettime(); unsigned err = 0; unsigned cnt = 0; const char* line; while((line=rl.read())) { cnt++; if(lt.find(line) == lt.NOT_FOUND) err++; } std::cerr << "Not Found: " << err << "/" << cnt << std::endl; std::cerr << "Elapsed: " << gettime()-beg_t << " sec" << std::endl << std::endl; std::cerr << "DONE" << std::endl; return 0; }
cktx:
/*** * ファイル名: cktx.cc * コンパイル: libtool --mode=link g++ -O3 -o cktx cktx.cc libtx.la * ※ あらかじめtxのソースをダウンロードし、ビルドしておくこと */ #include <iostream> #include "tx.hpp" #include "read_line.h" #include "gettime.h" int main(int argc, char** argv) { tx_tool::tx t; t.read(argv[1]); ReadLine rl(argv[2]); double beg_t = gettime(); unsigned err = 0; unsigned cnt = 0; const char* line; while((line=rl.read())) { cnt++; unsigned retlen; if(t.prefixSearch(line,strlen(line),retlen) == t.NOTFOUND) err++; } std::cerr << "Not Found: " << err << "/" << cnt << std::endl; std::cerr << "Elapsed: " << gettime()-beg_t << " sec" << std::endl << std::endl; std::cerr << "DONE" << std::endl; return 0; }
ckdarts:
/*** * ファイル名: ckdarts.cc * コンパイル: g++ -O3 -o ckdarts ckdarts.cc * ※ あらかじめdartsのソースをダウンロードし、解凍しておくこと */ #include <iostream> #include "darts.h" #include "read_line.h" #include "gettime.h" int main(int argc, char** argv) { Darts::DoubleArray da; da.open(argv[1]); ReadLine rl(argv[2]); double beg_t = gettime(); unsigned err = 0; unsigned cnt = 0; const char* line; while((line=rl.read())) { cnt++; if(da.exactMatchSearch<int>(line) == -1) err++; } std::cerr << "Not Found: " << err << "/" << cnt << std::endl; std::cerr << "Elapsed: " << gettime()-beg_t << " sec" << std::endl << std::endl; std::cerr << "DONE" << std::endl; return 0; }
