写像の速度

前にも同じようなことを書いたが、

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();

    

    map    m;

    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_map   m;

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;

        }

    }

}

// 配列

pair   m[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;

        }

    }

}