再帰呼び出しをループに置き換える
半年に一度くらい、古いコードで使っている再帰呼び出しが原因でスタックオーバーフローになるという不具合が発見され、その都度ループで書き直す修正を入れている。再帰呼び出しをループに展開する方法は、「幅優先探索」や「深さ優先探索」というキーワードで探すと見つけることができる。そのエッセンスだけメモしておく。
再帰呼び出しのうち、トップダウンで処理していくものについては、キューを使うと比較的簡単に展開できる。たとえば
struct Node {
Node* left;
Node* right;
:
};という構造体があって、
void ProcessNode(Node* node)
{
:
: (do something)
:
if (node->left)
ProcessNode(node->left);
if (node->right)
ProcessNode(node->right);
}のような再帰呼び出しがあるとき、ProcessNode関数は以下のように展開できる。
void ProcessNode(Node* node)
{
list<Node*> nodeList;
nodeList.push_back(node);
while (!nodeList.empty())
{
node = nodeList.front();
nodeList.pop_front();
:
: (do something)
:
if (node->left)
nodeList.push_back(node->left);
if (node->right)
nodeList.push_back(node->right);
}
}ボトムアップに処理していくものも基本的な考え方は一緒であるが、
- キューの代わりにスタックを使う
- スタックを積むときと実際に処理をするときの二度、ノードを訪れることになるので、今どっちのタイミングなのか、知るためのフラグが必要
になる点が少し面倒になる。模擬コードは以下のようになるはず（自分で試してね）。
namespace {
struct Data {
Data(Node* n) : node(n), isTraversed(false) {}
Node* node;
bool isTraversed;
};
}
void ProcessNode(Node* node)
{
vector<Data> nodeList;
nodeList.push_back(node);
while (!nodeList.empty())
{
auto& data = nodeList.back();
node = data.node;
if (!data.isTraversed)
{
data.isTraversed = true;
if (node->left)
nodeList.push_back(node->left);
if (node->right)
nodeList.push_back(node->right);
}
else
{
nodeList.pop_back();
:
: (do something)
:
}
}
}再帰呼び出しで書くと、単にコード中の "do something" の位置を if 文の前に持ってくるか後ろに置くかだけの差であり、記述としては簡便なうえに、マシンスタックを利用したほうがヒープよりも高速に動作する。つまりスタックオーバーフローを起こさない限りは再帰のほうが一概に優れているので、もろもろ考慮してどちらの実装方法を選ぶか決めましょう。
Cron の設定メモ
Firefox設定メモ ～MS PゴシックをMeiryo UIに置換～
Google Chromeが頻繁にクラッシュするのと、メモリ使用量が必要以上に多いので、Firefoxに戻ってきた。久々に帰ってきてみたら、UIがGoogle Chromeっぽくなっていて全然違和感がない。HTML5になってから動画の再生にもプラグインが必要なくなったので、プラグインは全てアンイストールないしdeactivateした。
やるべきことは、userContent.cssをいじって「MS Pゴシック」を「Meiryo UI」フォントに置き換えたくらい。Webブラウザの世界の技術も標準化が進み枯れてきたのか、オジサンの想像力が枯れてきたのか。
具体的には以下の2ステップ。
%APPDATA%\Mozilla\Firefox\Profiles\XXXXXXXX.default
以下に chrome というフォルダをつくって、userContent.cssというファイルを作成する。中身はかつてGoogle Chromeでサポートされていたユーザスタイルシートと同じで、たんに
@charset "UTF-8"; @font-face { font-family: "ＭＳ Ｐゴシック"; src: local("Meiryo UI"); } @font-face { font-family: "MS PGothic"; src: local("Meiryo UI"); } @font-face { font-family: "ＭＳ Ｐ明朝"; src: local("Meiryo UI"); } @font-face { font-family: "MS PMincho"; src: local("Meiryo UI"); }
などとしておいた。私は英語版Windowsなのでフォント名は「Meiryo UI」だが、日本語版の場合は「メイリオ」などとする必要があるかもしれない。Google Chromeはご丁寧にユーザスタイルシートファイルの変更のイベントを拾って、動的に既に開いているページに変更を適用してくれたけれども、Firefoxの場合は再起動が必要。設定はたいてい一度限りだし、この方がよい実装だと思う。今のところなんの不満もない。
コンテナ内の検索の速度について(2) ～setの使いどころ～
C++エクササイズその3。前回、前々回の実験で、setの良さが発揮できなかったものの、何となく経験に反する結果だったので、もう一つだけ実験してみた。
具体的には、要素の中身をintからstringに変え、要素数2000から50000のコンテナに対してそれぞれ100万回検索をかけて時間を測定した。
結果
横軸がコンテナの要素数、縦軸が100万回findするのに要した時間（単位：秒）
ソート済みvectorはそれでも大健闘。挿入の速さやメモリ効率を考えると使いどころは多いと思う。string程度の大きさのオブジェクトで、ある程度比較関数も複雑になってくると、メモリ上の構造のシンプルさよりもアルゴリズム的な優位性が利いてきて、setに分がでてくるということなんだろうか。
まとめ
intのような単純なオブジェクトでなければ、やはりsetの方が検索は速いが、ソート済みvectorにも挿入の速さやメモリ効率などのアドバンテージがあるので、状況に応じて両方使いこなすとよい。単に検索目的であればunordered_set一択。
コード
#include <iostream> #include <set> #include <list> #include <vector> #include <deque> #include <unordered_set> #include <random> #include <functional> #include <algorithm> #include <omp.h> #include <string> using namespace std; static void BenchmarkFindString() { default_random_engine generator; uniform_int_distribution<int> distribution; auto dice = bind(distribution, generator); uniform_int_distribution<int> distChar(65, 90); auto diceChar = bind(distChar, generator); uniform_int_distribution<size_t> distStrLen(16, 128); auto diceStrLen = bind(distStrLen, generator); vector<size_t> DATA_LENGTH_ARRAY(25); size_t next = 2000; for (auto& len : DATA_LENGTH_ARRAY) { len = next; next += 2000; } vector<string> QUERY_DATA(1000000); for (auto& dat : QUERY_DATA) { auto len = diceStrLen(); dat.reserve(len + 1); for (size_t i = 0; i < len; ++i) dat += (char)diceChar(); } cout << "size,vector,set,unordered_set" << endl; for (auto DATA_LENGTH : DATA_LENGTH_ARRAY) { vector<string> vals(DATA_LENGTH); for (auto& val : vals) { auto len = diceStrLen(); val.reserve(len + 1); for (size_t i = 0; i < len; ++i) val += (char)diceChar(); } cout << DATA_LENGTH; { vector<string> 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<string> 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<string> 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[]) { BenchmarkFindString(); return 0; }
コンテナ内の検索の速度について
追記：この記事には続きがあります。
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; }
