mapはどの程度遅いか

f : A → B という写像を実装する。


集合A, Bは同じ個数の要素を持ち、その個数をnとする。
A,Bの型をそれぞれS,Tとすると、
写像の実装で真っ先に思い浮かぶのは、


map

であろう。
だが、nが小さいとき


pair

の配列のほうが速いのではないだろうか。
mapを使えば、検索にかかる時間はlog nに比例する。
一方、配列を線形探索すればnに比例する。
ただ、mapのほうは比例係数が大きいだろうから、
nが小さいときは配列のほうが速く、
nがある数より大きくなればmap版のほうが速くなることが期待される。
その境界値を求めたい。

実例

ここでは簡単のため、A,Bとも0 〜 n - 1の整数とし、
適当にシャッフルしておく。


int a[n];
for(int i = 0; i < n; i++)
a[i] = i;
random_shuffle(a, a + n);

これをそれぞれ取り込む。


map m;
for(int i = 0; i < n; i++)
m.insert(make_pair(i, a[i]));


pair v[n];
for(int i = 0; i < n; i++)
v[i] = make_pair(i, a[i]);

そして、次のように写像を1000万回繰り返す。


int sum = 0;
for(int i = 0; i < 10000000; i++) {
int r = rand() % n;
sum += m.find(r)->second;
}


int sum = 0;
for(int i = 0; i < 10000000; i++) {
int r = rand() % n;
int j;
for(j = 0; j < n; j++) {
if(v[j].second == r)
break;
}
sum += v[j].first;
}

結果

n map(s) 配列(s)
4 2.22 0.67
8 2.53 0.79
16 2.96 0.92
32 3.31 1.10
64 3.66 1.45
128 3.94 2.28
256 4.24 3.80
512 4.61 6.85

近似式にすると、

map : t = 0.34log2n + 1.56
配列 : t = 0.0121n + 0.695

境界値は、

n = 305

となった。

これはコンパイラ(オプション)によって全然答が違ってくる。
配列のほうが意外と速いかもしれないので、
試したほうがいいということである。