kbcl0_0004
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
]
開始行:
* kbcl0のページ#4
-(by [[K]],2019.04.30)
** (7) KIndex系
-''[1]'' データがある程度あって、それをソートしたい時があ...
|KIndexS|キーでデータをソートしたインデックスを作ります|
|KIndexHC|ハッシュ関数を使ってデータのインデックスを作り...
|KIndexHO|ハッシュ関数を使ってデータのインデックスを作り...
|KIndexHS|KIndexHCの先がチェインではなく、KIndexSになりま...
-この4つになった理由ですが、最初はKIndexSを作ってなかなか...
-さらにオープンアドレス法のほうがたいていは速いと聞いてKI...
--というか、オープンアドレス法がいいと書いている話はあち...
-じゃあKIndexHCはお払い箱かなーと思ったのですが、もしかし...
-''[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 ...
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のときは、インデ...
-kfnv32というのはFNV-1という軽量で定番のハッシュ関数です...
-t0005t.txtの中身は、数独の問題が81文字で入っています。そ...
-だからこのプログラムがやっていることは、「780個の文字列...
-測定は Celeron J4005 2.00GHz というあまりハイスペックで...
|KIndexS|3.429秒||
|KIndexHC|2.004秒|衝突率=158/780|
|KIndexHO|1.994秒|衝突率=171/780|
|KIndexHS|1.979秒|衝突率=158/780|
-ここの「衝突率」というのは、ハッシュテーブルを引いたとき...
-こうしてみると、ネタで作ったKIndexHSが一番よさそうなこと...
-''[3]'' 先ほどのテストは理想的な場合です。ハッシュ関数が...
-ということで kfnv32(a, 8); にして、ハッシュ関数は先頭8文...
|KIndexHC|33.560秒|衝突率=707/780|
|KIndexHO|18.490秒|衝突率=716/780|
|KIndexHS|RIGHT:3.244秒|衝突率=707/780|
-ねらった通り、KIndexHCとKIndexHOは一気に遅くなりました。...
-この実験からわかる他のこととしては、こういう状況になると...
-''[4]'' ではもっとハッシュ関数をダメにしてみます。そうな...
|KIndexHC|62.730秒|衝突率=758/780|
|KIndexHO|31.305秒|衝突率=760/780|
|KIndexHS|RIGHT:3.669秒|衝突率=758/780|
-KIndexHCとKIndexHOはさらに悪くなっていますが、ここで注目...
-''[5]'' ということで結論です。
--どんなデータが来ても確実に安定している（＝ワーストケー...
--ハッシュ関数をうまく作れるのであれば、ほぼすべてのケー...
--ハッシュ関数があまりうまくない場合でも、ベストはKIndexH...
-kbcl0では、一応4つとも実装しておいたので、状況に応じて使...
* こめんと欄
#comment
終了行:
* kbcl0のページ#4
-(by [[K]],2019.04.30)
** (7) KIndex系
-''[1]'' データがある程度あって、それをソートしたい時があ...
|KIndexS|キーでデータをソートしたインデックスを作ります|
|KIndexHC|ハッシュ関数を使ってデータのインデックスを作り...
|KIndexHO|ハッシュ関数を使ってデータのインデックスを作り...
|KIndexHS|KIndexHCの先がチェインではなく、KIndexSになりま...
-この4つになった理由ですが、最初はKIndexSを作ってなかなか...
-さらにオープンアドレス法のほうがたいていは速いと聞いてKI...
--というか、オープンアドレス法がいいと書いている話はあち...
-じゃあKIndexHCはお払い箱かなーと思ったのですが、もしかし...
-''[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 ...
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のときは、インデ...
-kfnv32というのはFNV-1という軽量で定番のハッシュ関数です...
-t0005t.txtの中身は、数独の問題が81文字で入っています。そ...
-だからこのプログラムがやっていることは、「780個の文字列...
-測定は Celeron J4005 2.00GHz というあまりハイスペックで...
|KIndexS|3.429秒||
|KIndexHC|2.004秒|衝突率=158/780|
|KIndexHO|1.994秒|衝突率=171/780|
|KIndexHS|1.979秒|衝突率=158/780|
-ここの「衝突率」というのは、ハッシュテーブルを引いたとき...
-こうしてみると、ネタで作ったKIndexHSが一番よさそうなこと...
-''[3]'' 先ほどのテストは理想的な場合です。ハッシュ関数が...
-ということで kfnv32(a, 8); にして、ハッシュ関数は先頭8文...
|KIndexHC|33.560秒|衝突率=707/780|
|KIndexHO|18.490秒|衝突率=716/780|
|KIndexHS|RIGHT:3.244秒|衝突率=707/780|
-ねらった通り、KIndexHCとKIndexHOは一気に遅くなりました。...
-この実験からわかる他のこととしては、こういう状況になると...
-''[4]'' ではもっとハッシュ関数をダメにしてみます。そうな...
|KIndexHC|62.730秒|衝突率=758/780|
|KIndexHO|31.305秒|衝突率=760/780|
|KIndexHS|RIGHT:3.669秒|衝突率=758/780|
-KIndexHCとKIndexHOはさらに悪くなっていますが、ここで注目...
-''[5]'' ということで結論です。
--どんなデータが来ても確実に安定している（＝ワーストケー...
--ハッシュ関数をうまく作れるのであれば、ほぼすべてのケー...
--ハッシュ関数があまりうまくない場合でも、ベストはKIndexH...
-kbcl0では、一応4つとも実装しておいたので、状況に応じて使...
* こめんと欄
#comment
ページ名:
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
