hash - 兼雑記

まぁなんかしんどいのでハッシュでも考えるかと思ってたら kinaba さんが素晴らしいことを書いてたというのが現状なのですが、とりあえずどうでもいいとされた速度を測ったのではっておこうかと。

その前に VC の hash_map って少なくとも昔は衝突が起きた時に set みたいに突っ込む仕組みだったので、比較演算が必要だったように思うのでそういう意味でも VC のはひどいのかもしれない。

で、なんかきむらさんとこあたりで引用されてたベンチマークのコードは、数値をインクリメンタルに入れてるのがちょっとハッシュとかのベンチとしてはどうなんかなという感じなので適当にランダムな数値を入れて実験した。

コードは X 軸を n として n 個要素つっこんでから n 個外して空にして…というのを繰り返すような感じ。合計100万回実行してるので、たぶん縦軸は一回あたり何 micro second かかるか、て感じになってるかと思う。

http://shinh.skr.jp/tmp/hash_int_rand.png

あとオリジナルのベンチみたいに 0 から n までの数値を順番につっこんでみるとこんなかんじ。

http://shinh.skr.jp/tmp/hash_int_inc.png

正直 VC わけわからん結果ですが、まぁ wine とかで実験してるので気にしないで下さい。 GCC の方を見ると、 random な数値入れるよりは、 hash との差が少なくなってるので、 VC で逆転減少が起きてたオリジナルのベンチマークはまぁ、ありえん話でもないんじゃないかなみたいな。

あと個人的に連想配列のキーは 90% くらいは string だと思っているので、 string に関しても実験した。 words というのは /usr/share/dict/words で、 1 要素あたり 9.5B くらい。 skk というのは /usr/share/skk/SKK-JISYO.L で、 1 要素あたり 25.5B くらい。

http://shinh.skr.jp/tmp/hash_str.png

なんか VC のハッシュは絶望的な数値になってたのでグラフの上限をつっきっている。あとこっちでは実行回数減らしてるので、 Y 軸は micro second ではないです。

とにかく言いたいのは、少なくとも GCC では hash は常に速い感じなんじゃないかなという。個人的には map とか順番が重要な時以外使わない感じ。

↓コード

整数用

#include <stdio.h>
#include <time.h>
#include <iostream>
#include <map>
#include <vector>
#include <assert.h>

#ifdef _MSC_VER

#include <hash_map>

#else

#include <tr1/unordered_map>

using namespace std::tr1;

#define hash_map unordered_map

#endif

using namespace std;

int main(int argc, char* argv[]) {
    map<int, int> m;
    hash_map<int, int> um;
    vector<int> v;

    static const int TOT = 1000000;
    const int N = atoi(argv[1]);
    for (int i = 0; i < N; i++) {
        v.push_back(rand());
        //v.push_back(i);
        //v.push_back(0);
    }
    {
        clock_t cl = clock();
        for (int t = 0; t < TOT/N; t++) {
            for (int i = 0; i < v.size(); i++) {
                um.insert(make_pair(v[i], i));
            }
            for (int i = 0; i < v.size(); i++) {
                um.erase(v[i]);
            }
        }
        assert(m.empty());
        printf("%.3f\n", ((double)clock() - cl) / CLOCKS_PER_SEC);
    }
    {
        clock_t cl = clock();
        for (int t = 0; t < TOT/N; t++) {
            for (int i = 0; i < v.size(); i++) {
                m.insert(make_pair(v[i], i));
            }
            for (int i = 0; i < v.size(); i++) {
                m.erase(v[i]);
            }
        }
        assert(m.empty());
        printf("%.3f\n", ((double)clock() - cl) / CLOCKS_PER_SEC);
    }
}

文字列用

#include <stdio.h>
#include <time.h>
#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <algorithm>
#include <assert.h>

#ifdef _MSC_VER

#include <hash_map>

#else

#include <tr1/unordered_map>

using namespace std::tr1;

#define hash_map unordered_map

#endif

using namespace std;

int main(int argc, char* argv[]) {
    map<string, int> m;
    hash_map<string, int> um;
    vector<string> v;

    static const int TOT = 160000;
    const int N = atoi(argv[1]);
    FILE* fp = fopen("/usr/share/dict/words", "r");
    //FILE* fp = fopen("/usr/share/skk/SKK-JISYO.L", "r");
    for (int i = 0; i < N; i++) {
        char buf[1024];
        v.push_back(fgets(buf, 1023, fp));
    }
    fclose(fp);
    random_shuffle(v.begin(), v.end());
    {
        clock_t cl = clock();
        for (int t = 0; t < TOT/N; t++) {
            for (int i = 0; i < N; i++) {
                um.insert(make_pair(v[i], i));
            }
            for (int i = 0; i < N; i++) {
                um.erase(v[i]);
            }
        }
        assert(m.empty());
        printf("%.3f\n", ((double)clock() - cl) / CLOCKS_PER_SEC);
    }
    {
        clock_t cl = clock();
        for (int t = 0; t < TOT/N; t++) {
            for (int i = 0; i < N; i++) {
                m.insert(make_pair(v[i], i));
            }
            for (int i = 0; i < N; i++) {
                m.erase(v[i]);
            }
        }
        assert(m.empty());
        printf("%.3f\n", ((double)clock() - cl) / CLOCKS_PER_SEC);
    }
}