a22_acl2_02
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
]
開始行:
* acl2ライブラリ #2
-(by [[K]], 2022.11.24)
** (1) crit-bit木について #1
-''[1-1]''
-acl2ライブラリには、ACrit32L0B1などのクラスがあって、こ...
-''[1-2]''
-何か適当なオブジェクトの集合があって、それらを高速に検索...
-ソートといえばqsort()でしょう。ということで、ひとまず解...
-・・・でも待ってください。もし今100万件のデータがソート...
-それならmemmove()で消したい場所以降を1つ分だけ前にずらす...
-''[1-3]''
-しかしO(N)というのはお世辞にも速いアルゴリズムだとは言え...
-''[1-4]''
-とはいえ、人類のアルゴリズムの探求は終わりません。もっと...
-たとえば、キーのデータが、必ず大文字のアルファベット4文...
-しかしまあ、実際はそんな「キーの値は45.7万通りしかない」...
-たとえばこうです。"KAWAI"と"OSASK"と"ESSEN"の3つのキーが...
-''[1-5]''
-先の例ではキーの文字に注目しました。文字だと分岐が多くな...
-''[1-6]''
-crit-bit木に関するリンク集です。
--https://dankogai.livedoor.blog/archives/51853853.html
--https://cr.yp.to/critbit.html
--https://qiita.com/Pseudonym/items/c2ef9a3a574b9e047287
** (2) crit-bit木について #2
-''[2-1]''
-ここで、ベンチマーク結果を示したいと思います。・・・0か...
int qscmp(const void *a, const void *b)
{
return strcmp(*(char **) a, *(char **) b);
}
-としてみました。すると当方の環境（Kano PC, Celeron N4000...
0
1
10
100
1000
10000
100000
100001
100002
100003
100004
100005
100006
100007
100008
100009
10001
100010
100011
100012
-いい感じに混ざり合っているのがよくわかります。次に、比較...
int qscmp(const void *a, const void *b)
{
const unsigned char *ca = *(const unsigned char **) ...
if (ca[0] != cb[0]) return ca[0] - cb[0];
if (ca[1] != cb[1]) return ca[1] - cb[1];
if (ca[2] != cb[2]) return ca[2] - cb[2];
if (ca[3] != cb[3]) return ca[3] - cb[3];
if (ca[4] != cb[4]) return ca[4] - cb[4];
if (ca[5] != cb[5]) return ca[5] - cb[5];
return ca[6] - cb[6];
}
-こうすると、286ミリ秒になりました。もちろん結果は同じで...
int qscmp(const void *a, const void *b)
{
const unsigned int *ca = *(const unsigned int **) a,...
if (ca[0] != cb[0]) return ca[0] - cb[0];
return ca[1] - cb[1];
}
-この比較を成功させるためには、文字列を加工する必要があり...
-''[2-2]''
-では同じことをACrit32L0B1でやってみました。100万件の文字...
-''[2-3]''
-話はこれで終わりではありません。実はACrit32L0B2とACrit32...
|qsrot #1|RIGHT:340ms|
|qsort #2|RIGHT:286ms|
|qsort #3|RIGHT:278ms|
|ACrit32L0B1|RIGHT:186+20=206ms|
|ACrit32L0B2|RIGHT:145+17=162ms|
|ACrit32L0B4|RIGHT:127+15=142ms|
-このようにこの例ではqsort()よりも高速になりましたが、他...
-''[2-4]''
-上記の例では文字列は最長でも6バイトでした。もっと長い文...
-qsortの比較関数はこうしました。
int qscmp(const void *a, const void *b)
{
const unsigned int *ca = *(const unsigned int **) a,...
if (ca[0] != cb[0]) return ca[0] - cb[0];
if (ca[1] != cb[1]) return ca[1] - cb[1];
if (ca[2] != cb[2]) return ca[2] - cb[2];
if (ca[3] != cb[3]) return ca[3] - cb[3];
if (ca[4] != cb[4]) return ca[4] - cb[4];
return ca[5] - cb[5];
}
-結果は以下の通りです。
|qsort|RIGHT:328ms|
|ACrit32L0B1|RIGHT:203+21=224ms|
|ACrit32L0B2|RIGHT:175+18=193ms|
|ACrit32L0B4|RIGHT:160+16=176ms|
//-qsortでは328/278=1.18倍になりましたが、ACrit32L0B4では...
-''[2-5]''
-ではキーをもっと短くしたらどうでしょうか。今回は最長でも...
-qsortの比較関数はこうしました。
int qscmp(const void *a, const void *b)
{
const unsigned int *ca = *(const unsigned int **) a,...
return ca[0] - cb[0];
}
-一方でACrit32のほうも、キーの長さが32bitの固定長なら、よ...
|qsort|RIGHT:179ms||
|ACrit32L0B1|RIGHT:176+22=198ms|可変長モード|
|ACrit32L1B1|RIGHT:153+22=175ms|固定長32bitキー専用クラス|
|ACrit32L0B2|RIGHT:137+15=152ms|可変長モード|
|ACrit32L1B2|RIGHT:120+15=135ms|固定長32bitキー専用クラス|
|ACrit32L0B4|RIGHT:112+11=123ms|可変長モード|
|ACrit32L1B4|RIGHT:102+11=113ms|固定長32bitキー専用クラス|
-ちなみにACrit32L0Bxには固定長モードもありますが、結果は...
** (3) crit-bit木について #3
-''[3-1]''
-acl2ライブラリが提供するACrit32LxBxクラスは以下の機能を...
|init|初期化|
|deinit|後始末|
|ins|データの追加|
|srch0|検索（キーを指定）：データを返す|
|srch1|検索（ソート順でn番目）：データを返す|
|srch2|検索（キーを指定）：nを返す（註1）|
|srch3|検索（キーを指定）：nを返す（註1）|
|srch4|srch0の連続指定（註2）|
|srch5|srch1の連続指定（註2）|
|del0|削除（キーを指定）：データを返す|
|del1|削除（ソート順でn番目）：データを返す|
|annl|キーの加工（アニーリング）（註3）|
--[註1] srch2とsrch3の違いを説明します。srch2が木の中にあ...
--[註2] 指定されたキーから連続で複数のデータポインタを得...
--[註3] キーを検索しやすい形に加工します。主にビットを並...
-''[3-2]''
-世間で一般的に知られているcrit-bit木は、srch1～5, del1の...
||B1|B2|B4|
|pos:ビット位置|1|1|RIGHT:1|
|ptr:ポインタ|2|4|16|
|num:そのポインタの先にいくつデータがあるか|2|4|16|
--numは実はアルゴリズムを工夫すれば、1,3,15にできることが...
--num==1の時、対応するポインタはデータを指しています。num...
** (4) crit-bit木について #4
-''[4-1]''
-これだけいろいろできれば、例えばこんなことができます。
-malloc/free処理を考えます。・・・mallocするときに、要求...
-それでは性能を比べてみたいと思います。まずこんなプログラ...
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main()
{
int i, sz = 16 * 1024, n = 10;
void **p = malloc(1024 * 1024 * sizeof (void *)), *q;
free(malloc(1026 * 1024 * 1024)); // 1GBくらいを確保...
for (i = 0; i < n; i++)
p[i] = malloc(sz);
q = malloc(sz * 2);
for (i = 1; i < n; i += 2)
free(p[i]);
clock_t t0 = clock();
for (i = 0; i < 1000000; i++) {
free(q);
free(p[0]);
p[0] = malloc(sz);
q = malloc(sz * 2);
}
clock_t t1 = clock();
printf("%f[sec]\n", (double) (t1 - t0) / CLOCKS_PER_...
return 0;
}
-最初に16KBのメモリ領域をn個確保します。次に32KBのメモリ...
-ここで free(q); free(p[0]); p[0] = malloc(16KB); q = mal...
-ただし、それでも1回やったくらいでは大して時間はかからな...
-次にACrit32版のほうについてです。以下のようなクラスを作...
AClass(MemMan) {
ACrit32L0B1 idxSiz; // 空きメモリブロック情報オブジ...
};
-mallocではidxSizを使って最適な空きメモリブロックをO(logN...
||n=10|n=65536|
|オリジナル（msvcrt.dllのmalloc/freeを使用)|RIGHT:599ms|R...
|ACrit32L0B1を使ったmalloc/free|RIGHT:279ms|RIGHT:533ms|
|ACrit32L0B2を使ったmalloc/free|RIGHT:293ms|RIGHT:427ms|
|ACrit32L0B4を使ったmalloc/free|RIGHT:399ms|RIGHT:493ms|
-これを見ると、「ACrit32L0B1を使ったmalloc/free」がシンプ...
-高性能なmallocとしてはdlmallocが知られていますが、このMe...
-なお、言うまでもないですが、メモリ消費量の観点では、crit...
** (5) crit-bit木について #5
-''[5-1]''
-ACrit32L0B1などでは、データオブジェクトの中にアニール済...
-そのためオプションとして、若干の速度低下はあるものの、cr...
-そもそもcrit-bit木では、キーデータが必要になるのは、デー...
-''[5-2]''
-結局、crit-bit木の使いどころはどこなのかと考えました。
--[1]ハッシュテーブルの代わりに使う： ハッシュテーブルは...
--[2]平衡木の代わりに使う： 性能を比較してないので断言で...
--[3]全文検索に使う： 数万字、数百万字、なんならそれ以上...
-''[5-3]''
-ハッシュテーブルとcrit-bit木での性能比較をやってみました。
-テストに使ったのは、適当なHLX向けのサンプルプログラムを...
-ACrit32L0Bxでは、すべてのキーは16バイトの固定長であると...
|ACrit32L0B1|RIGHT:1425ms||
|ACrit32L0B2|RIGHT:999ms||
|ACrit32L0B4|RIGHT:746ms|ACrit32ではこれが最速|
|hash 582|RIGHT:879ms||
|hash 512|RIGHT:839ms||
|hash 1024|RIGHT:812ms|ハッシュ関数をカスタマイズしないの...
-うーんハッシュテーブルのパワーとはこんなものだったでしょ...
|ACrit32L0B1|RIGHT:1425ms||
|ACrit32L0B2|RIGHT:999ms||
|ACrit32L0B4|RIGHT:746ms|ACrit32ではこれが最速|
|hash 582|RIGHT:879ms||
|hash 512|RIGHT:839ms||
|hash 1024|RIGHT:812ms|ハッシュ関数をカスタマイズしないの...
|hash2 582|RIGHT:493ms||
|hash2 512|RIGHT:453ms||
|hash2 1024|RIGHT:413ms|ハッシュ関数をカスタマイズすれば...
-ハッシュテーブルに関しては、テーブルの大きさを4096や6553...
** (6) crit-bit木について #6
-[考察]Crit32L0B1とCrit32L0B4で何が違うか？
--[1]最大で4倍速く枝をたどれる（2つしか入っていないときは...
--[2]16分岐すべてが埋まっていれば・・・B1だと5*sizeof(int...
-[考察]ハッシュテーブルに対する優位性は？
--たとえば、Alfa, Bravo, Charlie, Delta, Echoみたいなキー...
終了行:
* acl2ライブラリ #2
-(by [[K]], 2022.11.24)
** (1) crit-bit木について #1
-''[1-1]''
-acl2ライブラリには、ACrit32L0B1などのクラスがあって、こ...
-''[1-2]''
-何か適当なオブジェクトの集合があって、それらを高速に検索...
-ソートといえばqsort()でしょう。ということで、ひとまず解...
-・・・でも待ってください。もし今100万件のデータがソート...
-それならmemmove()で消したい場所以降を1つ分だけ前にずらす...
-''[1-3]''
-しかしO(N)というのはお世辞にも速いアルゴリズムだとは言え...
-''[1-4]''
-とはいえ、人類のアルゴリズムの探求は終わりません。もっと...
-たとえば、キーのデータが、必ず大文字のアルファベット4文...
-しかしまあ、実際はそんな「キーの値は45.7万通りしかない」...
-たとえばこうです。"KAWAI"と"OSASK"と"ESSEN"の3つのキーが...
-''[1-5]''
-先の例ではキーの文字に注目しました。文字だと分岐が多くな...
-''[1-6]''
-crit-bit木に関するリンク集です。
--https://dankogai.livedoor.blog/archives/51853853.html
--https://cr.yp.to/critbit.html
--https://qiita.com/Pseudonym/items/c2ef9a3a574b9e047287
** (2) crit-bit木について #2
-''[2-1]''
-ここで、ベンチマーク結果を示したいと思います。・・・0か...
int qscmp(const void *a, const void *b)
{
return strcmp(*(char **) a, *(char **) b);
}
-としてみました。すると当方の環境（Kano PC, Celeron N4000...
0
1
10
100
1000
10000
100000
100001
100002
100003
100004
100005
100006
100007
100008
100009
10001
100010
100011
100012
-いい感じに混ざり合っているのがよくわかります。次に、比較...
int qscmp(const void *a, const void *b)
{
const unsigned char *ca = *(const unsigned char **) ...
if (ca[0] != cb[0]) return ca[0] - cb[0];
if (ca[1] != cb[1]) return ca[1] - cb[1];
if (ca[2] != cb[2]) return ca[2] - cb[2];
if (ca[3] != cb[3]) return ca[3] - cb[3];
if (ca[4] != cb[4]) return ca[4] - cb[4];
if (ca[5] != cb[5]) return ca[5] - cb[5];
return ca[6] - cb[6];
}
-こうすると、286ミリ秒になりました。もちろん結果は同じで...
int qscmp(const void *a, const void *b)
{
const unsigned int *ca = *(const unsigned int **) a,...
if (ca[0] != cb[0]) return ca[0] - cb[0];
return ca[1] - cb[1];
}
-この比較を成功させるためには、文字列を加工する必要があり...
-''[2-2]''
-では同じことをACrit32L0B1でやってみました。100万件の文字...
-''[2-3]''
-話はこれで終わりではありません。実はACrit32L0B2とACrit32...
|qsrot #1|RIGHT:340ms|
|qsort #2|RIGHT:286ms|
|qsort #3|RIGHT:278ms|
|ACrit32L0B1|RIGHT:186+20=206ms|
|ACrit32L0B2|RIGHT:145+17=162ms|
|ACrit32L0B4|RIGHT:127+15=142ms|
-このようにこの例ではqsort()よりも高速になりましたが、他...
-''[2-4]''
-上記の例では文字列は最長でも6バイトでした。もっと長い文...
-qsortの比較関数はこうしました。
int qscmp(const void *a, const void *b)
{
const unsigned int *ca = *(const unsigned int **) a,...
if (ca[0] != cb[0]) return ca[0] - cb[0];
if (ca[1] != cb[1]) return ca[1] - cb[1];
if (ca[2] != cb[2]) return ca[2] - cb[2];
if (ca[3] != cb[3]) return ca[3] - cb[3];
if (ca[4] != cb[4]) return ca[4] - cb[4];
return ca[5] - cb[5];
}
-結果は以下の通りです。
|qsort|RIGHT:328ms|
|ACrit32L0B1|RIGHT:203+21=224ms|
|ACrit32L0B2|RIGHT:175+18=193ms|
|ACrit32L0B4|RIGHT:160+16=176ms|
//-qsortでは328/278=1.18倍になりましたが、ACrit32L0B4では...
-''[2-5]''
-ではキーをもっと短くしたらどうでしょうか。今回は最長でも...
-qsortの比較関数はこうしました。
int qscmp(const void *a, const void *b)
{
const unsigned int *ca = *(const unsigned int **) a,...
return ca[0] - cb[0];
}
-一方でACrit32のほうも、キーの長さが32bitの固定長なら、よ...
|qsort|RIGHT:179ms||
|ACrit32L0B1|RIGHT:176+22=198ms|可変長モード|
|ACrit32L1B1|RIGHT:153+22=175ms|固定長32bitキー専用クラス|
|ACrit32L0B2|RIGHT:137+15=152ms|可変長モード|
|ACrit32L1B2|RIGHT:120+15=135ms|固定長32bitキー専用クラス|
|ACrit32L0B4|RIGHT:112+11=123ms|可変長モード|
|ACrit32L1B4|RIGHT:102+11=113ms|固定長32bitキー専用クラス|
-ちなみにACrit32L0Bxには固定長モードもありますが、結果は...
** (3) crit-bit木について #3
-''[3-1]''
-acl2ライブラリが提供するACrit32LxBxクラスは以下の機能を...
|init|初期化|
|deinit|後始末|
|ins|データの追加|
|srch0|検索（キーを指定）：データを返す|
|srch1|検索（ソート順でn番目）：データを返す|
|srch2|検索（キーを指定）：nを返す（註1）|
|srch3|検索（キーを指定）：nを返す（註1）|
|srch4|srch0の連続指定（註2）|
|srch5|srch1の連続指定（註2）|
|del0|削除（キーを指定）：データを返す|
|del1|削除（ソート順でn番目）：データを返す|
|annl|キーの加工（アニーリング）（註3）|
--[註1] srch2とsrch3の違いを説明します。srch2が木の中にあ...
--[註2] 指定されたキーから連続で複数のデータポインタを得...
--[註3] キーを検索しやすい形に加工します。主にビットを並...
-''[3-2]''
-世間で一般的に知られているcrit-bit木は、srch1～5, del1の...
||B1|B2|B4|
|pos:ビット位置|1|1|RIGHT:1|
|ptr:ポインタ|2|4|16|
|num:そのポインタの先にいくつデータがあるか|2|4|16|
--numは実はアルゴリズムを工夫すれば、1,3,15にできることが...
--num==1の時、対応するポインタはデータを指しています。num...
** (4) crit-bit木について #4
-''[4-1]''
-これだけいろいろできれば、例えばこんなことができます。
-malloc/free処理を考えます。・・・mallocするときに、要求...
-それでは性能を比べてみたいと思います。まずこんなプログラ...
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main()
{
int i, sz = 16 * 1024, n = 10;
void **p = malloc(1024 * 1024 * sizeof (void *)), *q;
free(malloc(1026 * 1024 * 1024)); // 1GBくらいを確保...
for (i = 0; i < n; i++)
p[i] = malloc(sz);
q = malloc(sz * 2);
for (i = 1; i < n; i += 2)
free(p[i]);
clock_t t0 = clock();
for (i = 0; i < 1000000; i++) {
free(q);
free(p[0]);
p[0] = malloc(sz);
q = malloc(sz * 2);
}
clock_t t1 = clock();
printf("%f[sec]\n", (double) (t1 - t0) / CLOCKS_PER_...
return 0;
}
-最初に16KBのメモリ領域をn個確保します。次に32KBのメモリ...
-ここで free(q); free(p[0]); p[0] = malloc(16KB); q = mal...
-ただし、それでも1回やったくらいでは大して時間はかからな...
-次にACrit32版のほうについてです。以下のようなクラスを作...
AClass(MemMan) {
ACrit32L0B1 idxSiz; // 空きメモリブロック情報オブジ...
};
-mallocではidxSizを使って最適な空きメモリブロックをO(logN...
||n=10|n=65536|
|オリジナル（msvcrt.dllのmalloc/freeを使用)|RIGHT:599ms|R...
|ACrit32L0B1を使ったmalloc/free|RIGHT:279ms|RIGHT:533ms|
|ACrit32L0B2を使ったmalloc/free|RIGHT:293ms|RIGHT:427ms|
|ACrit32L0B4を使ったmalloc/free|RIGHT:399ms|RIGHT:493ms|
-これを見ると、「ACrit32L0B1を使ったmalloc/free」がシンプ...
-高性能なmallocとしてはdlmallocが知られていますが、このMe...
-なお、言うまでもないですが、メモリ消費量の観点では、crit...
** (5) crit-bit木について #5
-''[5-1]''
-ACrit32L0B1などでは、データオブジェクトの中にアニール済...
-そのためオプションとして、若干の速度低下はあるものの、cr...
-そもそもcrit-bit木では、キーデータが必要になるのは、デー...
-''[5-2]''
-結局、crit-bit木の使いどころはどこなのかと考えました。
--[1]ハッシュテーブルの代わりに使う： ハッシュテーブルは...
--[2]平衡木の代わりに使う： 性能を比較してないので断言で...
--[3]全文検索に使う： 数万字、数百万字、なんならそれ以上...
-''[5-3]''
-ハッシュテーブルとcrit-bit木での性能比較をやってみました。
-テストに使ったのは、適当なHLX向けのサンプルプログラムを...
-ACrit32L0Bxでは、すべてのキーは16バイトの固定長であると...
|ACrit32L0B1|RIGHT:1425ms||
|ACrit32L0B2|RIGHT:999ms||
|ACrit32L0B4|RIGHT:746ms|ACrit32ではこれが最速|
|hash 582|RIGHT:879ms||
|hash 512|RIGHT:839ms||
|hash 1024|RIGHT:812ms|ハッシュ関数をカスタマイズしないの...
-うーんハッシュテーブルのパワーとはこんなものだったでしょ...
|ACrit32L0B1|RIGHT:1425ms||
|ACrit32L0B2|RIGHT:999ms||
|ACrit32L0B4|RIGHT:746ms|ACrit32ではこれが最速|
|hash 582|RIGHT:879ms||
|hash 512|RIGHT:839ms||
|hash 1024|RIGHT:812ms|ハッシュ関数をカスタマイズしないの...
|hash2 582|RIGHT:493ms||
|hash2 512|RIGHT:453ms||
|hash2 1024|RIGHT:413ms|ハッシュ関数をカスタマイズすれば...
-ハッシュテーブルに関しては、テーブルの大きさを4096や6553...
** (6) crit-bit木について #6
-[考察]Crit32L0B1とCrit32L0B4で何が違うか？
--[1]最大で4倍速く枝をたどれる（2つしか入っていないときは...
--[2]16分岐すべてが埋まっていれば・・・B1だと5*sizeof(int...
-[考察]ハッシュテーブルに対する優位性は？
--たとえば、Alfa, Bravo, Charlie, Delta, Echoみたいなキー...
ページ名:
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
