* 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(char *a, char *b) { return strncmp(a, b, 81); }
 unsigned int hsh(char *a) { 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.429秒||
|KIndexHC|2.004秒|衝突率=158/780|
|KIndexHO|1.994秒|衝突率=171/780|
|KIndexHS|1.979秒|衝突率=158/780|
-ここの「衝突率」というのは、ハッシュテーブルを引いたときに目的のデータが一番最初に来ないものの個数です。ハッシュ関数がどのくらいばらまいてくれているかの目安になります。
-こうしてみると、ネタで作ったKIndexHSが一番よさそうなことがわかります。そしてチェイン法とオープンアドレス法を比べるとオープンアドレス法がよいことがわかります（まあ小さな差ではありますが）。なるほど、だからみんなこれを使っていたのかー。

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

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

-''[5]'' ということで結論です。
--どんなデータが来ても確実に安定している（＝ワーストケースで最も成績が良い）のはKIndexSです。
--ハッシュ関数をうまく作れるのであれば、ほぼすべてのケースで最適なのはKIndexHSです。
--ハッシュ関数があまりうまくない場合でも、ベストはKIndexHSです。
-kbcl0では、一応4つとも実装しておいたので、状況に応じて使い分けようと思います。




* こめんと欄
#comment
トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS