動的ダブル配列を使って Wikipedia のテキスト処理を高速化
Wikipediaによるテキストマイニング入門など，Wikipedia 中の単語頻度を測るのが流行っているようだ．例えば，Hadoop を使ったり（Hadoop で Wikipedia のテキスト処理を900倍高速化 - 武蔵野日記），ハッシュを使ったり（Hadoopを使わずにWikipediaのテキスト処理を400倍高速化 - tsubosakaの日記Hadoopを使わずにWikipediaのテキスト処理を400倍高速化 - tsubosakaの日記）とか．情報系の人間なら普通はハッシュで十分と思うところ，折角なので動的ダブル配列を使って測ってみた．動的ダブル配列から保存された文字列を効率的に取り出すには，ノードリンクを実装して traverse () を再帰的に呼び出せば良い．今回は MSD radix sort 用に sibling のリンクを昇順にしたバージョン（僅かに追加速度が低下）を利用．Hadoopを使わずにWikipediaのテキスト処理を400倍高速化 - tsubosakaの日記のハッシュ (unordered_map) を利用したカウンタと比較してみる (gcc 4.6; -O2 -march=core2 -m64)．
データは Wikipedia-ja の2010-03-06 版 (テキストで 10M x 128)．ハッシュを利用したカウンタ (遅い順にhash_counter1, hash_counter2, hash_counter3) と，動的ダブル配列を使ったカウンタ (dda_counter) の実行結果 (on a server with Intel Xeon E5462 (3.2 Ghz)) は以下．
> ls -l unigram_raw.txt -rw-r--r-- 1 xxxxx xxxxx 1645539124 2010-06-12 12:50 unigram_raw.txt > time cat unigram_raw.txt | hash_counter1 > tmp.hash1 cat unigram_raw.txt 0.09s user 2.04s system 2% cpu 1:35.57 total hash_counter1 > tmp.hash1 96.76s user 3.41s system 99% cpu 1:40.62 total > time hash_counter2 > tmp.hash2 hash_counter2 > tmp.hash2 61.90s user 5.12s system 99% cpu 1:07.06 total > time hash_counter3 > tmp.hash3 hash_counter3 > tmp.hash3 33.98s user 5.41s system 99% cpu 39.432 total > time dda_counter unigram_raw.txt > tmp.dda dda_counter unigram_raw.txt > tmp.dda 27.35s user 2.04s system 99% cpu 29.426 total
dda_counter では std::map と同様に，キーは辞書順で出力される．処理時間，消費メモリは hash_counter1 (101s, 177MB), hash_counter2 (67s, 1717MB), hash_coutner3 (39s, 1633MB), dda_counter (29s, 161MB)．
というわけで，Hadoop やハッシュを使わなくても，動的ダブル配列を実装すれば，単語頻度のカウントは1750倍高速化される上，キーをソートして出力できます！動的ダブル配列ハヤーイと言いたいところだが，ランダム追加・検索だとハッシュとダブル配列は大差ないような気がしたので，ダブル配列のところをハッシュに変えた版を自作．
#include <cstdio> #include <cstdlib> #include <cstring> #include <tr1/unordered_map> struct equal_charp { bool operator () (const char* a, const char* b) const { int i = 0; for (; a[i] && b[i]; ++i) if (a[i] != b[i]) return false; // reject immediately return a[i] == b[i]; } }; struct hashfun_charp { // FNV-1a unsigned int operator () (const char* const &p) const { unsigned int h = 0x811c9dc5; for (char const *q = p; *q != '\0'; ++q) { h ^= *q; h *= 0x01000193; } return h; } }; int main (int argc, char** argv) { typedef std::tr1::unordered_map <char*, int, hashfun_charp, equal_charp> hash; if (argc < 2) { std::fprintf (stderr, "Usage: %s file\n", argv[0]); std::exit (1); } FILE * reader = std::fopen (argv[1], "r"); if (! reader) { std::fprintf (stderr, "no such file: %s\n", argv[1]); std::exit (1); } // push hash keys; char * line = 0; #ifdef __APPLE__ size_t read = 0; while ((line = fgetln (reader, &read)) != NULL) { #else ssize_t read = 0; size_t size = 0; while ((read = getline (&line, &size, reader)) != -1) { #endif * (line + read - 1) = '\0'; hash::iterator it = keys.find (line); if (it == keys.end ()) { char * copy = new char[read]; std::strcpy (copy, line); it = keys.insert (hash::value_type (copy, 0)).first; } ++it->second; } std::fclose (reader); // print for (hash::iterator it = keys.begin (); it != keys.end (); ++it) { std::fprintf (stdout, "%s %d\n", it->first, it->second); delete [] it->first; } return 0; }
実行してみる．
> time hash_counter4 unigram_raw.txt > tmp.hash4 hash_counter4 unigram_raw.txt > tmp.hash4 28.21s user 1.91s system 99% cpu 30.170 total
処理時間，消費メモリは，30s, 106M．動的ダブル配列を使ったカウンタとほとんど同じ速度（で，メモリ的には当然有利）．釣りっぽいタイトルでしたが，char * をキーにしたハッシュと比較する限り，キーを整列する必要がなければダブル配列を持ち出すメリットは無いということでした．
また，ちゃんとメモリを適宜確保すれば，ファイル全体をメモリに載せる必要は無いです（頻度が2回以上の単語について無駄にメモリを割り当てる分遅い）．コンテナの要素にはコピーコストの大きい要素を入れずに（コンテナのサイズを拡大する度に全要素をコピーし直す），ポインタを入れましょう．
先日の日記に書いたことにも関係するけど，Hadoop みたいな技術は，「処理にかかる時間を1/1000に短縮する」ための技術と認識している人と，「処理するデータを1000倍に増やす」ための技術と認識している人とで，実際に扱うデータのサイズに大きな差が出ると思う．
