日曜日だが,
坪坂君の実験
で Google sparsehash はやはり結構速かったことが
わかったのに影響されて(?), 自製のHPYLMのコードを
Google sparsehash
で書き直してみることに。
というのは, もうすぐ公開する予定のプログラムで確率の計算がボトルネックに
なっているらしいことが分かったからですが..。
*1
実際のプログラムはうまく抽象化して書いてあったことが幸いして,
少し直すだけで対応完了。
- ngramの各ノードから子供へのポインタを探す部分
- 予測するngramのノードから, 予測したい語(CRPオブジェクト)へのポインタを探す 部分
の両方を sparse_hash/dense_hash にしてみました。
例えば, p(cake|mary eats a)の確率を予測したい場合, 木の根から
a→eats→mary の順にノードをたどり, たどり着いた 'mary eats a' のノードで
cake が何回出てきているか&そのテーブルの数は何個か, を知る必要がありますが,
どの検索もスパースなので, 何らかの形で効率的なデータ構造が必要になります。
というのが前置きで, 以下がその結果。
Algorithm | Time | Memory |
---|
dense_hash_map | 33.48min | 209M |
sparse_hash_map | 55.28min | 111M |
splay tree | 57.13min | 76M |
上はかなり小さいデータ(京大コーパスから5000文)のもので, 毎日新聞2000年度全文
(約150万文)を突っ込んだメモリ使用量は, dense_hash_map で7.5G, splay tree で
4.0Gでした。ちなみに, ナイーブに ext/hash_map を使うと20G超えのようです。
ということで,
- メモリ効率ではスプレー木はやはり優秀 *2
- sparse_hash_map の速度はスプレー木と同程度
- dense_hash_map はスプレー木に比べてメモリを2倍弱使うが, 速度が2倍弱になる
というのがひとまずの結論のようです。
スプレー木は二分木なので O(logn) ですが, 意外と速かったなというか..。
今回は densehash を使うことにしましたが, ちなみにスプレー木は自己組織化二分木
なので, 計算が進むほど, 各ノードの持つ二分木の構造が最適化されて, どんどん計算
が速くなるという素敵仕様があったりします。
*1: ちなみに, この実装ではノードの検索は int のハッシュなので, ハッシュ関数の影響
はありません。
*2: これは, ngramの各ノードでそれぞれハッシュを持つという構造のせいで,
巨大なハッシュを一つだけ持つという場合は, Google sparsehashのメモリ効率は非常に
良いのだと思います。