車輪の再発明は避けるべき,を実感
ここ最近,Percy Liang の Brown クラスタリングの実装を使って単語クラスタリングしていたのだけど,感覚的に実行速度が遅いと感じたので,これぐらい簡単なアルゴリズムなら再実装しても良いかと思って,以下の原著を見ながら C++ で実装してみた.
- Class-based n-gram models of natural language (Computational Linguistics, 1992)
単純なだけに300行ぐらいで実装できたが,相互情報量の損失の計算をサボるところが少し面倒で,既存実装と結果が一致するまでに丸一日かかった*1.
自分の実装と既存実装の処理速度を比べたところ 5-10 倍ぐらい速くなっており(大規模データを扱う場合には実行速度が 2 倍違うだけでも致命的なので)再実装して良かったと一瞬ぬか喜びしたのだけど,同じ C++ で同じアルゴリズムを実装していてこんなに速度差があるのは怪しいと思って少し調べたら,既存実装の Makefile 中でコンパイル時の g++ の最適化オプションが -g になっているのに気がついた orz. 同じ最適化オプションで再コンパイルして実行してみたら,1.25倍ぐらいしか速くなかったよ.これは微妙過ぎる.
今回の失敗は,既存実装が C++ で書かれていて,大規模データを処理することを想定したアルゴリズムということから,コンパイラの最適化オプションが -O2 以上になっていると勝手に思い込んでしまっていたこと*2.後置インクリメントを使っていたりと(処理速度をあまり意識していないと思われる)フラグはあったし,再実装する前に気づくべきだった.仕方ない,処理に一週間ぐらいかかる実験をして(Intel Xeon 3.2Ghz CPU, k=1024, V=3M (words) ぐらい),元を取っておくか.