kbcl0_0004 のバックアップ(No.3)

バックアップ一覧
差分を表示
現在との差分を表示
ソースを表示
kbcl0_0004 へ行く。
- 1 (2019-04-30 (火) 09:06:43)
- 2 (2019-04-30 (火) 11:14:17)
- 3 (2019-04-30 (火) 11:14:17)

kbcl0のページ#4

(by K,2019.04.30)

(7) KIndex系

[1] データがある程度あって、それをソートしたい時があります。もしくは別にソートまではしなくてもいいのだけど、キーが一致するものを高速に検索したい時があります。そんなときのために、以下の4つのクラスを作りました。

KIndexS	キーでデータをソートしたインデックスを作ります
KIndexHC	ハッシュ関数を使ってデータのインデックスを作ります（チェイン法）
KIndexHO	ハッシュ関数を使ってデータのインデックスを作ります（オープンアドレス法）
KIndexHS	KIndexHCの先がチェインではなく、KIndexSになります

この4つになった理由ですが、最初はKIndexSを作ってなかなか良い性能が出たものの、やっぱりハッシュを使ったらもっと速くなるんだろうなと思って適当にKIndexHCを作ったらやっぱり速くてさすがだと思いました。

さらにオープンアドレス法のほうがたいていは速いと聞いてKIndexHOを作ってみたら確かに速くて、ああだから世間のたいていのハッシュテーブルはオープンアドレス法を実装しているんだなーと納得できました（やはり両方作ってみないとよくわからない）。
- というか、オープンアドレス法がいいと書いている話はあちこちにあるけど、何がどのくらいのいいのかを比較したものはなかなか見つけられなかったので、単純には信用できないと思ったのです。
じゃあKIndexHCはお払い箱かなーと思ったのですが、もしかしてチェインの部分をKIndexSにしたら最強なんじゃないかと急に思いついて、ネタで作ったのがKIndexHSです（笑）。

[2] ベンチマークテストをしてみます。

#include "kbcl0.h"
#include <stdio.h>
#include <time.h>
#include <string.h>

int cmp(void *opt, char *a, char *b) { (void) opt; return strncmp(a, b, 81); }
unsigned int hsh(void *opt, char *a) { (void) opt; return kfnv32(a, 81); }

int main()
{
    // ファイルから読み込んで行単位で記憶する.
    char *f = (char *) kreadFileA("t0005t.txt", "rb", 1 + 2);
    KSizPtr sp;
    while (*f != 0)
        sp.addPtr(kcutCrLfM(ksgetsA(&f)));

    // インデックスを作って登録する.
    int i, i1 = sp.s / sizeof (void *), j, cr;
    char **p = (char **) sp.p;
    KIndexS idx((void *) cmp, 0);
    for (i = 0; i < i1; i++)
        idx.ins(p[i]);

    // 検索速度の測定.
    clock_t t0 = 0, t1;
    for (j = -10; j < 10000; j++) {
        if (j == 0) t0 = clock();
        for (i = 0; i < i1; i++)
            idx.search(p[i], &cr);
    }
    t1 = clock();
    printf("%d\n", (int) (t1 - t0));
    return 0;
}

これはKIndexSの例ですが、KIndexHC/HO/HSのときは、インデックスのクラス名を変えて、コンストラクタにハッシュ関数も渡して、searchのときに&crを渡さないだけです。だから2行しか変わりません。
kfnv32というのはFNV-1という軽量で定番のハッシュ関数です（これもkbcl0に入れてあります）。たいていはこれで結構いけます。
t0005t.txtの中身は、数独の問題が81文字で入っています。それが780行あるだけのものです。手元に他の適当な「重複のない」＆「まあまあの規模がある」データがなかったのでこれにしました。
だからこのプログラムがやっていることは、「780個の文字列データを用意して、それを何も考えずにインデックスにガンガン登録して、「すべてのデータを1回ずつsearchしてみる検索」を1万セット繰り返すのに要した時間を計る」です。
測定は Celeron J4005 2.00GHz というあまりハイスペックではない環境でやりました。全体的に結果は微妙かもしれませんが、相対的な比較はできると思います。
KIndexS 3.533秒
KIndexHC 2.161秒衝突率=158/780
KIndexHO 2.135秒衝突率=171/780
KIndexHS 2.145秒衝突率=158/780
ここの「衝突率」というのは、ハッシュテーブルを引いたときに目的のデータが一番最初に来ないものの個数です。ハッシュ関数がどのくらいばらまいてくれているかの目安になります。
こうしてみると、オープンアドレス法が一番よさそうなことがわかります（まあ小さな差ではありますが）。なるほど、だからみんなこれを使っていたのかー。

[3] 先ほどのテストは理想的な場合です。ハッシュ関数がちゃんとデータをばらまいているうちは、KIndexHSが有利になることはありません。だからここではハッシュ関数がうまく作れなくて衝突しまくっている状況で実験してみようと思います。
ということで kfnv32(a, 8); にして、ハッシュ関数は先頭8文字しか見ていないというひどい仕様にしました。するとこうなります。
KIndexHC 34.365秒衝突率=707/780
KIndexHO 18.609秒衝突率=716/780
KIndexHS 3.349秒衝突率=707/780
ねらった通り、KIndexHCとKIndexHOは一気に遅くなりました。そして見事にKIndexHSは耐えています。しかも少しだけのハッシュ関数による分類も効果があって、KIndexSよりもわずかに速くなっています。
この実験からわかる他のこととしては、こういう状況になると、チェイン法に対するオープンアドレス法の優位がよりはっきりと見えてくるということです。

[4] ではもっとハッシュ関数をダメにしてみます。そうなるとどうなるかを確認したいのです。 kfnv32(a, 4); にしました。
KIndexHC 64.229秒衝突率=758/780
KIndexHO 31.014秒衝突率=760/780
KIndexHS 3.854秒衝突率=758/780
KIndexHCとKIndexHOはさらに悪くなっていますが、ここで注目すべきはKIndexHSです。つまり本当にハッシュ関数がどうしようもなくダメだと、単純な二分探索よりも悪くなることがあるのです。おそらくこれはハッシュ関数の計算コストの分だと思います。

[5] ということで結論です。
- どんなデータが来ても確実に安定している（＝ワーストケースで最も成績が良い）のはKIndexSです。
- ハッシュ関数をうまく作れるのであれば、ほぼすべてのケースで最適なのはKIndexHOです。
- ハッシュ関数をうまく作ったつもりだけど、でもワーストケースでの性能もある程度保証しておきたいなら、最適なのはKIndexHSです。
- 残念ながらKIndexHCが役に立つケースは思いつけませんでした。
kbcl0では、一応4つとも実装しておいたので、状況に応じて使い分けようと思います。

↑

こめんと欄

コメント	お名前	NameLink

KIndexS	3.533秒
KIndexHC	2.161秒	衝突率=158/780
KIndexHO	2.135秒	衝突率=171/780
KIndexHS	2.145秒	衝突率=158/780

KIndexHC	34.365秒	衝突率=707/780
KIndexHO	18.609秒	衝突率=716/780
KIndexHS	3.349秒	衝突率=707/780

KIndexHC	64.229秒	衝突率=758/780
KIndexHO	31.014秒	衝突率=760/780
KIndexHS	3.854秒	衝突率=758/780