日曜日だが, 坪坂君の実験 で 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 を使うことにしましたが, ちなみにスプレー木は自己組織化二分木 なので, 計算が進むほど, 各ノードの持つ二分木の構造が最適化されて, どんどん計算 が速くなるという素敵仕様があったりします。

---