C++ 高速化 - speedkumoのプログラミング日記

研究でC++でソフトウェアの開発を行っていますが
データ量が少ない場合は速度はあまり、気にしなくていいのですが、
データ量が増えてくると、計算量などを意識して、高速化をする必要性を感じてきました。

自分は実装でSTLのmapやmultimapを使っているのですが、mapの検索の計算量がO(log n),multimapの計算量がO(nlogn)なのでここで、時間を食っているのだと考えられます。

そのため、この部分の計算量を減らす方法を検討しました。

まず、STLのmapの計算量がlog(n)なのは、実装に二分木が用いられるためです。そのため、このmapの実装をhashで行ったら高速化されるのではないかと考えました。

そこで、調べていくと、boostで計算量がO(1)のunordered_map,unorderd_multimapのライブラリを見つけたため、これを用いることに決めました。

boostはあまり、つかったことがなかったのですが、便利ですね。

しかし、C++0xでこのライブラリは使えるので、
実装時に、g++ -std=c++0x　という風にして上げればいいので、boostをとってきてディレクトリに置かなくでも大丈夫ですね

あと、実装でlistを用いている部分があるのですが、そこで、遅くなっている可能性を感じました。

一般的にvecotorとlistではvectorのほうがlistより高速なイメージがありますが、挿入、削除が行われる場合、listを使ったほうがお得です。

上記の理由から、listを用いたのですが、使用メモリや処理速度の点でオーバーヘッドが大きいのと、単方向リストで十分と今回の場合、判断したため、forward_listをもちることにしました。
これも、C++0xに含まれています。

以上のライブラリでおそらく、だいぶ高速化されると考えられるので、実装が楽しみですね

特にunordered_mapやunordered_multimapは、計算量がハッシュを用いることで劇的に減るので、かなり期待できますね

C++0xやboostライブラリ、素晴らしいですね