■

カゼひいたぽいので一回休み。

hash

http://www.jmuk.org/diary/2008/04/09/0

http://www.kt.rim.or.jp/~kbk/zakkicho/08/zakkicho0804a.html#D20080408-2

http://www.kmonos.net/wlog/84.html#_1049080409

まぁなんかしんどいのでハッシュでも考えるかと思ってたら 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 とか順番が重要な時以外使わない感じ。

↓コード

↑

なんか間違って全然違うコードはっててわらった。しんどい時はちゃんと寝ましょう。

個人的に list と set っていうデータ構造はこう、全然信用してないというか、あまりこう登場頻度が高くないとされている物体で、

• 今のアーキテクチャでは、何要素くらいから探索が vector より set の方が良くなるのか
• 今のアーキテクチャでは、何要素くらい移動する必要が発生すると挿入が vector より list の方が良くなるのか
• URL の群れがあったとして、何要素くらいから線型探索よりハッシュが速くなるのか
• メソッドテーブルを作るとして、何要素くらいから線型探索よりハッシュが速くなるのか
• vector と list の末尾挿入ってどのくらい差が出るのか

とかそのへんが気になっている。

最後のやってみた。

vector が 0.210 秒で list が 0.850 秒とかで、 vector の方が速かった。まぁそらそうだ。当たり前だと思う人で、償却定数時間とかの単語を知らない人は、このへん見てみるといいかも:

http://chasen.org/~taku/blog/archives/2007/02/_o1.html

#include <stdio.h>
#include <time.h>
#include <vector>
#include <list>

using namespace std;

int main() {
    vector<int> v;
    list<int> l;
    {
        clock_t cl = clock();
        for (int i = 0; i < 10000000; i++) {
            v.push_back(i);
        }
        printf("%.3f\n", ((double)clock() - cl) / CLOCKS_PER_SEC);
    }
    {
        clock_t cl = clock();
        for (int i = 0; i < 10000000; i++) {
            l.push_back(i);
        }
        printf("%.3f\n", ((double)clock() - cl) / CLOCKS_PER_SEC);
    }
}

push_front

push_front だけくらいなら実験できるので、 vector に insert(v.begin(), i) とかするのと list に push_front する速度を比較してみた。

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

答え: int 40要素くらいなら vector もいいセン行く。