先日、Pythonで実装したWard法をC++で再実装し、比較してみた。
まずは、前回のPython版の処理時間を再掲。
件数 処理時間(s) そのうち初期行列作成時間
--------------------------------------------
196 0.677 0.334
392 2.158 1.356
588 4.636 3.073
1176 18.071 12.088
2352 79.09 49.507
これをC++に移植すると、以下の処理時間に短縮される。
件数 処理時間(s) そのうち初期行列作成時間
--------------------------------------------
196 0.216 0.04
392 0.842 0.17
588 1.627 0.39
1176 7.086 1.57
2352 33.432 6.39
今回は、まずは行列作成部分に、できるだけC++で可能なチューニングを施してある。
樹形図作成部分は、あまり最適化していない。
標準のstd::mapとかstd::vectorを使用しており、特別な数値計算用ライブラリなどは一切使っていない。
また、コンパイル時の様々なコンパイルオプションでの最適化もまだ行っていない。
C++(C)のいい所は、メモリの使い方などをダイレクトに想像しながらチューニングが行える所だろう。
今回も、３重ループの効率化を行うだけで、ここまで処理時間が短くなった。
しかし、作っていて気づいたのは、最適化を意識しないでC++を書くと、Pythonとたいして変わらない処理時間だったことだ。
その証拠に、上の表での処理時間の短縮分のほとんどは、今回意識して最適化を図った行列作成部分のものである。
次は、実際の樹形図作成部分がネックになっているので、この部分をより速くしていきたいと思う。
今回のソースはcodereposに置いておきました。
