コンテナ内の検索の速度について
追記：この記事には続きがあります。
C++エクササイズその2。前回の実験で、要素の追加についてはvectorの性能が際立っていたので、今度は要素の検索について実験してみた。
vectorに対して要素の検索をする場合、誰もが思いつくのは
というわけで、今回はソート済みvectorに対するstd::lower_bound()、set
- コンテナに対して100万回検索をかける
- コンテナサイズは20000から500000まで、20000刻み。各コンテナは同じ乱数を使って初期化（中身は一緒）
結果
さすがにunordered_setは速い。しかしソート済みvectorに対する二分岐探索は、setよりも速い。あれ、set、いいとこ無いじゃん。vectorに比べて挿入は400倍遅くて、検索も2倍から3倍遅いとは。
まとめ
- 検索に関してはunordered_set最強。これは技術書どおりでホッとした
- ソート済みの要素に対して検索をかけられるならば、vectorのほうがsetよりも速い
- 前回の結果と組み合わせると、ソート済みvectorは挿入も検索もsetを凌ぐパフォーマンスを示している。これはハードウェア的な問題なのか、単にsetの実装がマズいのか...。
コード
実験に使ったコードは以下の通り。開発環境はVisual Studio 2013 (msvc12)で、コンパイラオプションも特にいじらず素のリリースモジュールで実験しました。
#include <iostream> #include <set> #include <vector> #include <unordered_set> #include <random> #include <functional> #include <algorithm> #include <omp.h> using namespace std; static void BenchmarkFind() { default_random_engine generator; uniform_int_distribution<int> distribution; auto dice = bind(distribution, generator); vector<size_t> DATA_LENGTH_ARRAY(25); size_t next = 20000; for (auto& len : DATA_LENGTH_ARRAY) { len = next; next += 20000; } vector<int> QUERY_DATA(1000000); for (auto& dat : QUERY_DATA) dat = dice(); cout << "size,vector,set,unordered_set" << endl; for (auto DATA_LENGTH : DATA_LENGTH_ARRAY) { vector<int> vals(DATA_LENGTH); for (auto& val : vals) val = dice(); cout << DATA_LENGTH; { vector<int> cont(begin(vals), end(vals)); sort(begin(cont), end(cont)); cont.erase(unique(begin(cont), end(cont)), end(cont)); double dStart = omp_get_wtime(); for (auto val : QUERY_DATA) lower_bound(begin(cont), end(cont), val); cout << ',' << (omp_get_wtime() - dStart); } { set<int> cont(begin(vals), end(vals)); double dStart = omp_get_wtime(); for (auto val : QUERY_DATA) cont.find(val); cout << ',' << (omp_get_wtime() - dStart); } { unordered_set<int> cont(begin(vals), end(vals)); double dStart = omp_get_wtime(); for (auto val : QUERY_DATA) cont.find(val); cout << ',' << (omp_get_wtime() - dStart); } cout << endl; } } int main(int argc, char* argv[]) { BenchmarkFind(); return 0; }
コンテナへの挿入の速度について
C++エクササイズ。今回は挿入の速度に的を絞って計測してみた。
やったこと
- ランダムな整数値を50000個生成
- 整数値をコンテナに挿入する
- 2の操作を各コンテナにつき10回繰り返す
vectorについてはさらに3つの異なる条件でも実験してみた。
- (R) ... あらかじめ領域をreserveする
- (RS) ... setは挿入時に値をソートし、ユニークかどうかのチェックもするので、vectorで同等の後処理をする（vector + sort + unique）
- (RSS) ... 後処理ではなく、挿入時にユニークかどうかを二分岐探索でチェックする（よりsetに近い挙動）
結果
（単位：秒）
vector<int> 0.0305866 vector<int>(R) 0.00266554 vector<int>(RS) 0.0445996 vector<int>(RSS) 1.97772 set<int> 17.7869 unordered_set<int> 36.134 list<int> 76.8214 deque<int> 15.5323
発生する乱数のレンジを小さくして、衝突が起こりやすくすれば、setの速度はもう少し上がる。しかし、極端な例としてレンジを [0, 10] にしても、vector + sort + unique の速度にはダブルスコアで負けてしまった。vector強し。
1秒あたりの挿入数をグラフにプロットしてみた（対数グラフ）
まとめ
この結果、実はCPUのキャッシュがどれくらい有効に使われているかとかのほうが利いているのかもしれない（それもまた良い発見）。STLportなどの異なるSTLの実装、異なるハードウェアでも、また違った傾向が観察できるはず。
とりあえず覚えておくと良いのは
- 連続領域が安全に確保できるならvectorを使っておけば間違いない
- reserveしたvector最強。なるべくreserveを呼んでおく
- 検索を必要とせず、単にソート済みのユニークな要素のリストがほしければsetではなくvector + sort + unique の組み合わせを使う（場合によっては1万倍以上の差が出る）
- 実は検索が必要な場合も、二分岐探索で挿入、検索するほうがパフォーマンスが出るかもしれない（これはあとで検証する）
- list/setへの挿入のコストはvectorのpush_backとは次元が違う
- dequeとvectorもこれだけ差が出る（似て非なる）
といったところ。雑感としては、unordered_set、dequeの結果は想像したoptimalな挙動とかけ離れていると感じる。本当にパフォーマンスが必要とされるところではSTLを信用せず、必要があれば自作するという選択肢もアリだと思った。
たまにこうやって手を動かして、速度を体感しておくのは大切ですね。
コード
使ったコードは以下の通り。開発環境はVisual Studio 2013 (msvc12)を使った。
#include <iostream> #include <set> #include <list> #include <vector> #include <deque> #include <unordered_set> #include <random> #include <functional> #include <algorithm> #include <omp.h> using namespace std; int main(int argc, char* argv[]) { default_random_engine generator; uniform_int_distribution<int> distribution; const int LOOP_COUNT = 10; const size_t DATA_LENGTH = 50000; vector<int> vals(DATA_LENGTH); auto dice = bind(distribution, generator); for (auto& val : vals) val = dice(); double dStart = omp_get_wtime(); //----------------------------------------------------------------- for (int i = 0; i < LOOP_COUNT; ++i) { vector<int> cont; for (auto val : vals) cont.push_back(val); } cout << "vector<int>\t" << (omp_get_wtime() - dStart) << endl; //----------------------------------------------------------------- dStart = omp_get_wtime(); for (int i = 0; i < LOOP_COUNT; ++i) { vector<int> cont; cont.reserve(DATA_LENGTH); for (auto val : vals) cont.push_back(val); } cout << "vector<int>(R)\t" << (omp_get_wtime() - dStart) << endl; //----------------------------------------------------------------- dStart = omp_get_wtime(); for (int i = 0; i < LOOP_COUNT; ++i) { vector<int> cont; cont.reserve(DATA_LENGTH); for (auto val : vals) cont.push_back(val); sort(begin(cont), end(cont)); cont.erase(unique(begin(cont), end(cont)), end(cont)); } cout << "vector<int>(RS)\t" << (omp_get_wtime() - dStart) << endl; //----------------------------------------------------------------- dStart = omp_get_wtime(); for (int i = 0; i < LOOP_COUNT; ++i) { vector<int> cont; cont.reserve(DATA_LENGTH); for (auto val : vals) { auto lb = lower_bound(begin(cont), end(cont), val); if (lb != end(cont) && *lb == val) continue; cont.insert(upper_bound(begin(cont), end(cont), val), val); } } cout << "vector<int>(RSS)\t" << (omp_get_wtime() - dStart) << endl; //----------------------------------------------------------------- dStart = omp_get_wtime(); for (int i = 0; i < LOOP_COUNT; ++i) { set<int> cont; for (auto val : vals) cont.insert(val); } cout << "set<int>\t" << (omp_get_wtime() - dStart) << endl; //----------------------------------------------------------------- dStart = omp_get_wtime(); for (int i = 0; i < LOOP_COUNT; ++i) { unordered_set<int> cont; for (auto val : vals) cont.insert(val); } cout << "unordered_set<int>\t" << (omp_get_wtime() - dStart) << endl; //----------------------------------------------------------------- dStart = omp_get_wtime(); for (int i = 0; i < LOOP_COUNT; ++i) { list<int> cont; for (auto val : vals) cont.push_back(val); } cout << "list<int>\t" << (omp_get_wtime() - dStart) << endl; //----------------------------------------------------------------- dStart = omp_get_wtime(); for (int i = 0; i < LOOP_COUNT; ++i) { deque<int> cont; for (auto val : vals) cont.push_back(val); } cout << "deque<int>\t" << (omp_get_wtime() - dStart) << endl; return 0; }
水曜日：C++関数の多重定義
かれこれC++で飯を食べさせていただいて10年くらいになるけれど、久々に血の気が弾いたあと鼻血がでるくらい酷いバグ入れてしまった。
幸い正式リリースモジュールを送信する数時間前に気付いて事無きを得たのだけど、本当に危なかった。
#include <iostream> #include <string> using namespace std; void writeOption(const string& value) { cout << "text: " << value << endl; } void writeOption(bool value) { cout << "bool: " << (value ? "true" : "false") << endl; } int main() { string s = "std::string de gonsu."; bool b = true; writeOption(s); writeOption(b); writeOption("text de gonsu"); return 0; }
最後の呼び出しがバグで、"test de gonsu" が出力されると思われがちだが、実際の結果は
text: std::string de gonsu. bool: true bool: true
となる。
とりあえずconst char*版を追加することで最小限の変更で修正をした。
同様の問題には ostream に対して wchar_t* の文字列を流し込んでポインタ値が出力されるバグなどがある。今のところ、この手の問題を未然に防ぐエレガントな方法が見つかっていない。
火曜日
昼はお好み焼き。夕飯はカレーと名前の知らない野菜と豚肉の炒め物。Chromecastが届いた。
夕方、普段果物を食べないK氏が苺を食べたと奥さんから連絡。めでたい。普通に考えれば大したことないことかもしれないけれども、我が家にとっては一大事であった。
M氏は高度なことをして親を驚かせるのに対して、K氏は真央ちゃん効果でいつも驚かしてくれる。
月曜日
帰宅時、ガレージを空けると子供のおもちゃが転がっていた。いつもは私が自分で片付けていたが、今日は初めて出迎えにきて気付いたK氏がどかしてくれた。
本日はM氏が疲れ切って早寝、帰ったらK氏が一人っ子状態で、込み上げてくる喜びが押さえきれず、ずーっとニヤニヤしていた。面白いくらいに分かり易い。
「お父さん、一緒に寝よう」
といつも言ってくるけれど、それはM氏のために遠慮していて、本当はお母さんと寝たいのを知っていたので
「今日はお母さんと寝ていいんだよ」
と言ったら、少し嬉しそうにして、寝かしつけてもらっていた。
火曜日
そろそろ暖かくなってきたので、ボタンが陥没してスイッチが入らなくなっていた扇風機を修理した。SEARSで買ったロータリー式の安物だけど、機構がシンプルでかつ静かで風力も強く、リモコン操作にも対応している。
唯一つの難点は、組み付けにセキュリティボルトを使用しており、通常の工具では容易に分解できないところである。その難点を克服すべくセキュリティボルトを取り外すための工具を自作した。
電動ドリルに、マンドレル（mandrel）を装着してディスクカッター（cut-off disc）を取り付け、中心を外さないように慎重に削りだす。思ったよりうまくいった。
日曜日
前日K氏と一緒に9時就寝、午前3時に目が覚めてしまう。午後5時まで布団でぐずぐずして6時に起きて波乗り。今年は水温もそこそこ暖かく、波にも恵まれている。
昼は蕎麦屋、食料買出し。帰りにケーキを買って帰る。平穏で楽しい週末であった。
