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.34log₂n + 1.56
配列 : t = 0.0121n + 0.695

境界値は、

n = 305

となった。

注

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