Yak!の日記: アルゴリズムクイックリファレンス 単一点最短経路 追試 [C++]
ま た ベ ン チ マ ー ク か !
またベンチマークなのである。O'Reilly 刊のアルゴリズムクイックリファレンス(ISBN978-4-87311-428-6) p.175 に以下のような記述がある。
例 6-5 に示すように、C++ 標準テンプレートライブラリオブジェクトをすべて取り除いて例 6-4 をさらに最適化することができる。サポートするクラスのオーバーヘッドを除くことにより、「6.4.6 比較」で論じるように、性能が大きく改善されることが分かる。
C++er の端くれとしては「ないわー」と言わざるを得まい。ということで追試してみた。なお、出オチでネタばらししておくと例 6-5のデータ型が int** に対して例 6-4では list<pair<int, int> >* である。「密グラフのための」って言ってるのに行列じゃないじゃん。ということで vector<vector<int> > に変更した版で確認した。元ソースは http://oreilly.com/catalog/9780596516246 の Examples から取得可能。変更版はデータ型変えた程度でかつ適当ソースなのでとりあえず省略。環境は g++ 4.3.4 on cygwin、Boost 1.42、CPU Core2Duo T7600(2.33GHz)、RAM 3GB である。10 回実行して最長、最短を除いた 8 回の平均をとっている。N/A はメモリ不足で実行できなかったもの。表中での略記は以下の通り。
- pq
- 優先度付きキューによるダイクストラのアルゴリズム(Examples まま)
- dc
- 密グラフのための最適化されたダイクストラのアルゴリズム(Examples まま)
- D+
- 密グラフのためのダイクストラのアルゴリズム(Examples まま)
- d+
- 密グラフのためのダイクストラのアルゴリズム vector 版
- rate
- 密グラフのための最適化されたダイクストラのアルゴリズム(Examples まま)を 1 としたときの比率
- w/o O
- 最適化なし
- w/ O
- 最適化あり(-O2)
V | E |pq w/o O|dc w/o O|D+ w/o O|d+ w/o O| rate
--------+------------+--------+--------+--------+--------+------
980 | 479,710 | 0.095 | 0.017 | 0.098 | 0.076 | 4.55
1,621 | 1,313,010 | 0.297 | 0.046 | 0.300 | 0.208 | 4.54
6,117 | 18,705,786 | N/A | 0.659 | 5.554 | 2.922 | 4.43
7,663 | 29,356,953 | N/A | 1.039 | N/A | 4.585 | 4.41
9,847 | 48,476,781 | N/A | 1.709 | N/A | 7.536 | 4.41
9,882 | 48,882,021 | N/A | 1.716 | N/A | 7.607 | 4.43
V | E |pq w/ O|dc w/ O|D+ w/ O|d+ w/ O| rate
--------+------------+--------+--------+--------+--------+------
980 | 479,710 | 0.061 | 0.007 | 0.066 | 0.010 | 1.36
1,621 | 1,313,010 | 0.210 | 0.021 | 0.219 | 0.028 | 1.34
6,117 | 18,705,786 | N/A | 0.296 | 4.445 | 0.405 | 1.37
7,663 | 29,356,953 | N/A | 0.471 | N/A | 0.640 | 1.36
9,847 | 48,476,781 | N/A | 0.780 | N/A | 1.051 | 1.35
9,882 | 48,882,021 | N/A | 0.781 | N/A | 1.062 | 1.36
オーバーヘッドが全くない、と言えるところまでではないが速度命でなければ安全性を考慮した上で選択肢になり得るといったところか。書籍中で最悪 20~30 倍だったことからすれば全然余裕である。あと言うまでもないことではあるが STL 使うなら最適化はしっかりかけとけという点も言えるだろう。30% の速度低下については間接参照の増加が原因かと思われる。一度 Boost MultiArray、BGL 辺りと比較をとってみたい。
なお、まだ読んでいる途中ではあるがアルゴリズムクイックリファレンス自体は理論と実践の両極端に偏りがちなアルゴリズム関連書籍の間を取り持とうという良コンセプトの本であり理論中心のアルゴリズム本に挫折した人にも勧められるのではないかと思っている。
アルゴリズムクイックリファレンス 単一点最短経路 追試 [C++] More ログイン