犬も猫も空想も扱っておりません。(旧・エト記)この広告は、90日以上更新していないブログに表示しています。2014-08-14コンテナへの挿入の速度についてC++C++エクササイズ。今回は挿入の速度に的を絞って計測してみた。整数値をコンテナに挿入する2の操作を各コンテナにつき10回繰り返すvectorについてはさらに3つの異なる条件でも実験してみた。15.5323発生する乱数のレンジを小さくして、衝突が起こりやすくすれば、setの速度はもう少し上がる。速度にはダブルスコアで負けてしまった。1秒あたりの挿入数をグラフにプロットしてみた(対数グラフ)まとめこの結果、実はCPUのキャッシュがどれくらい有効に使われているかとかのほうが利いているのかもしれない(それもまた良い発見)。STLportなどの異なるSTLの実装、異なるハードウェアでも、また違った傾向が観察できるはず。覚えておくと良いのは連続領域が安全に確保できるならvectorを使っておけば間違いないreserveしたvector最強。組み合わせを使う(場合によっては1万倍以上の差が出る)実は検索が必要な場合も、二分岐探索で挿入、検索するほうがパフォーマンスが出るかもしれない(これはあとで検証する)list/setへの挿入のコストはvectorのpush_backとは次元が違うdequeとvectorもこれだけ差が出る(似て非なる)といったところ。雑感としては、unordered_set、dequeの結果は想像したoptimalな挙動とかけ離れていると感じる。本当にパフォーマンスが必要とされるところではSTLを信用せず、必要があれば自作するという選択肢もアリだと思った。やって手を動かして、速度を体感しておくのは大切ですね。コード使ったコードは以下の通り。(msvc12)を使った。10:57コンテナへの挿入の速度についてTweet広告を非表示にするもっと読むコメントを書く2014-08-14コンテナ内の検索の速度についてC++追記:この記事には続きがあります。C++エクササイズその2。前回の実験で、要素の追加についてはvectorの性能が際立っていたので、今度は要素の検索について実験してみた。vectorに対して要素の検索をする場合、誰もが思いつくのはに定義されているstd::findだろうと思うが、setに対して公正な比較対象になるのはstd::lower_bound()(二分岐探索)だろう。いうわけで、今回はソート済みvectorに対するstd::lower_bound()、set::find()、unordered_set::find()の比較を行ってみた。コンテナに対して100万回検索をかけるコンテナサイズは20000から500000まで、20000刻み。各コンテナは同じ乱数を使って初期化(中身は一緒)結果さすがにunordered_setは速い。ソート済みvectorに対する二分岐探索は、setよりも速い。あれ、set、いいとこ無いじゃん。vectorに比べて挿入は400倍遅くて、検索も2倍から3倍遅いとは。まとめ検索に関してはunordered_set最強。これは技術書どおりでホッとしたソート済みの要素に対して検索をかけられるならば、vectorのほうがsetよりも速い前回の結果と組み合わせると、ソート済みvectorは挿入も検索もsetを凌ぐパフォーマンスを示している。これはハードウェア的な問題なのか、単にsetの実装がマズいのか...。コード実験に使ったコードは以下の通り。(msvc12)で、コンパイラオプションも特にいじらず素のリリースモジュールで実験しました。~setの使いどころ~C++C++エクササイズその3。前回、前々回の実験で、setの良さが発揮できなかったものの、何となく経験に反する結果だったので、もう一つだけ実験してみた。具体的には、要素の中身をintからstringに変え、要素数2000から50000のコンテナに対してそれぞれ100万回検索をかけて時間を測定した。横軸がコンテナの要素数、縦軸が100万回findするのに要した時間(単位:秒)ソート済みvectorはそれでも大健闘。挿入の速さやメモリ効率を考えると使いどころは多いと思う。string程度の大きさのオブジェクトで、ある程度比較関数も複雑になってくると、メモリ上の構造のシンプルさよりもアルゴリズム的な優位性が利いてきて、setに分がでてくるということなんだろうか。まとめintのような単純なオブジェクトでなければ、やはりsetの方が検索は速いが、ソート済みvectorにも挿入の速さやメモリ効率などのアドバンテージがあるので、状況に応じて両方使いこなすとよい。検索目的であればunordered_set一択。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。