前にも同じようなことを書いたが、
http://d.hatena.ne.jp/inamori/20060903/p1
もうちょっと詳細に。
f(x) = (x + 1) % n
という写像のスピードを考える。
x = 0から1000万回この写像を繰り返して、その実行時間を調べる。
実装には、
map, hash_map, vector, 配列
を使う。
環境は、Windows2000、Visual C++.net 2003、Pentium4 2.8GHz。
全域にわたって、mapよりhash_mapのほうが速い。
前にどこかでmapのほうが速いような記事を読んだのだが。
これとかか。
http://www.s34.co.jp/cpptechdoc/article/hash/index.html
私の経験では、挿入/削除より参照するほうが圧倒的に重要なのよね、今の仕事も含めて。
vectorはけっこう優秀。
// map
const int n = 4;int _tmain(int argc, _TCHAR* argv[]) {
int t0 = timeGetTime();
mapm;
for(int i = 0; i < n; i++)
m.insert(make_pair(i, (i + 1) % n));
int r = 0;
for(int i = 0; i < 10000000; i++) {
r = m.find(r)->second;
// r = m[r]; // これだと倍くらいかかる
}
cout << r << endl;
cout << (timeGetTime() - t0) << "ms" << endl;
return 0;
}
// hash_map
hash_mapm;
for(int i = 0; i < n; i++)
m.insert(make_pair(i, (i + 1) % n));int r = 0;
for(int i = 0; i < 10000000; i++) {
r = m.find(r)->second;
}
// vector
vector> m;
for(int i = 0; i < n; i++) {
m.push_back(make_pair(i, (i + 1) % n));
}int r = 0;
for(int i = 0; i < 10000000; i++) {
for(int k = 0; k < n; k++) {
if(m[k].first == r) {
r = m[k].second;
break;
}
}
}
// 配列
pairm[n];
for(int i = 0; i < n; i++) {
m[i] = make_pair(i, (i + 1) % n);
}int r = 0;
for(int i = 0; i < 10000000; i++) {
for(int k = 0; k < n; k++) {
if(m[k].first == r) {
r = m[k].second;
break;
}
}
}