a22_acl2_02 の編集

* acl2ライブラリ #2
-(by [[K]], 2022.11.24)

** (1) crit-bit木について #1
-''[1-1]''
-acl2ライブラリには、ACrit32L0B1などのクラスがあって、これはcrit-bit木を利用するためのクラスです。それでまずはcrit-bit木について説明します。

-''[1-2]''
-何か適当なオブジェクトの集合があって、それらを高速に検索したいとします。ソートした結果をポインタの配列で持っておくことができたら、あとは二分探索で探すだけでよくなるので、とても便利だと思います。これならO(logN)です（もしソートしてなかったら二分探索が使えないので、O(N)になってしまいます）。
-ソートといえばqsort()でしょう。ということで、ひとまず解決です。
-・・・でも待ってください。もし今100万件のデータがソート済みで、そこから一つだけデータを消すとしたらどうでしょうか？まず消すべきデータがどこにあるのかは二分探索ですぐにわかります。そして、そこを一番最後の要素で上書きすれば、これで一つ消したことになります。しかしこれだとソートされた状態が維持できていません。仕方ないのでqsortを呼びます。・・・これはいけません。O(NlogN)の時間がかかります。
-それならmemmove()で消したい場所以降を1つ分だけ前にずらすのはどうでしょうか。これならO(N)で済みます。qsort()よりもいいです。・・・同じ問題は、データを1件だけ追加するときにも生じます。二分探索で挿入すべき場所を探して、memmove()でそこに1つ分の空きを作って入れるやり方のほうがqsort()よりも速いです。・・・結局qsort()は最初にたくさんのデータをソートするには最適なアルゴリズムですが、その後1件ずつ更新するには不向きなアルゴリズムです。

-''[1-3]''
-しかしO(N)というのはお世辞にも速いアルゴリズムだとは言えません。・・・これより速いアルゴリズムがあります。それば二分木やB木などです。これらはソートされた結果をポインタの配列で保持するのをやめて、「木」と呼ばれるデータ構造で管理します。この状態でもデータの検索はO(logN)で行えます。またデータの削除や追加はそれぞれどちらもO(logN)で、先のO(N)よりも格段に速いです。ただし、単純な配列よりもメモリは使います。たいてい単純な配列バージョンの数倍の容量を必要とします。ですから開発者はスピード重視かそれとも省メモリ重視なのかで使い分けることになります。

-''[1-4]''
-とはいえ、人類のアルゴリズムの探求は終わりません。もっと速くできないでしょうか。・・・結局、二分木やB木の処理時間のほとんどは、キーデータの比較です。そう、単純な配列であっても二分探索の際にはO(logN)回のキーの比較をやっていました。だからこの比較処理をやめることができたら、ずっと速くできそうです。・・・そんな夢みたいな方法があるのか・・・あるんです。
-たとえば、キーのデータが、必ず大文字のアルファベット4文字で構成されているとしましょう。これは26^4=45.7万通りしかありません。それなら45.7万の要素を持つポインタの配列を作ればいいじゃないですか。これで、キーの値が"KAWA"のオブジェクトがどこにあるかをO(1)で検索できるようになります。データの1件ずつの追加も削除もすべてO(1)です。これはもはやハッシュ関数を使わないハッシュテーブルです。
-しかしまあ、実際はそんな「キーの値は45.7万通りしかない」みたいなことはまれで、たいていはテーブル配列をメモリ上に構築できません（大きすぎて無理）。でも要点は一つ見つかりました。「ほかのキーとの比較をやめればいい」これです。
-たとえばこうです。"KAWAI"と"OSASK"と"ESSEN"の3つのキーがあるのなら、1文字目だけ見ればそれだけでどこに行けばいいのかわかります。もしここで"OMAKE"も入って合計4つのキーになった場合は、1文字目が"O"の場合に限って2文字目を見て、"S"か"M"かで分岐します。こういう「木」を作ればいいのです。・・・この木をたどる際には、自分のキーだけ見ていればいいのです。他のキーとの比較は発生しません。・・・こういう木を「トライ木」と総称します。

-''[1-5]''
-先の例ではキーの文字に注目しました。文字だと分岐が多くなります。仮に1文字が1バイトだとしても256通りもあります。そんな木は管理が大変なので、キーをビット列に展開し、1ビットずつで見ていくことにして、3ビット目が"0"ならこっち、"1"ならあっち、みたいな木を作ります。これがcrit-bit木です。crit-bitというのは「クリティカル・ビット」の略らしいです。これは私の推測ですが、臨界点（クリティカル・ポイント）という言葉があって、水と氷のさかい目の温度とか、水蒸気と水のさかい目の温度などのことを指しているのですが（というか物質は水に限らないし、温度じゃなくて圧力の場合も臨界点なのですが）、そういう、AかBかのぎりぎりのさかい目ということで、クリティカル・ビットなのかなーと。1ビットで枝分かれするのであれば、分岐はそれぞれ2つしかありません。二分木とにたような木になって理解しやすいです。木をたどるときに他のキーとの比較はないので、crit-bitはトライ木のうちの一つです。

-''[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から999999まで、数を数えて文字列にします。これで"0", "1", "2", "3", ... という100万件の文字列データができます。これをqsortでソートします。その際に比較関数を
 int qscmp(const void *a, const void *b)
 {
     return strcmp(*(char **) a, *(char **) b);
 }
-としてみました。すると当方の環境（Kano PC, Celeron N4000）では、初期の並びを配列に書き込んでqsort()が終わるまでに340ミリ秒かかりました。ソート結果を出力するとこうなっていました。
 0
 1
 10
 100
 1000
 10000
 100000
 100001
 100002
 100003
 100004
 100005
 100006
 100007
 100008
 100009
 10001
 100010
 100011
 100012
-いい感じに混ざり合っているのがよくわかります。次に、比較関数を改良しました。strcmp()は遅いので、使わない形に書きました。
 int qscmp(const void *a, const void *b)
 {
     const unsigned char *ca = *(const unsigned char **) a, *cb = *(const unsigned char **) b;
     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ミリ秒になりました。もちろん結果は同じです。ではもっと改良します。32bitのintを使って、4文字ずつ比較します。
 int qscmp(const void *a, const void *b)
 {
     const unsigned int *ca = *(const unsigned int **) a, *cb = *(const unsigned int **) b;
     if (ca[0] != cb[0]) return ca[0] - cb[0];
     return ca[1] - cb[1];
 }
-この比較を成功させるためには、文字列を加工する必要があります。x86はリトルエンディアンなので、char *s;のs[0]が上位に来てくれないのです。それでエンディアンを入れ替える処理を追加しました。するとソートに要する時間は278ミリ秒になりました（このキーの加工にかかる時間はこの278ミリ秒には含まれません）。32ビット環境ではこれくらいがqsort()での限界かなと思います。

-''[2-2]''
-では同じことをACrit32L0B1でやってみました。100万件の文字列を作って、やはりキーを都合のいい形式に加工しておきます（ビットを入れ替える）。また空っぽの木も準備しておきます。ここから処理時間を計測開始です。ACrit32L0B1_ins()でデータを1つずつ追加していきます。合計100万件です。そしてその後、qsort()と結果が同じ形式になるように配列にポインタを出力させます。この時間を計りました。100万回のinsに186ミリ秒かかって、配列への出力に20ミリ秒かかりました。合計で206秒です。qsort()での最速の278ミリ秒よりも明らかに速いです！

-''[2-4]''
-上記の例では文字列は最長でも6バイトでした。もっと長い文字列でやったら当然遅くなると思いますが、さてどの程度遅くなるでしょうか。実験してみました。文字列はUTF8で全角文字にしました。これで1文字当たり3バイトになるので、最長18バイトになります。
-qsortの比較関数はこうしました。
 int qscmp(const void *a, const void *b)
 {
     const unsigned int *ca = *(const unsigned int **) a, *cb = *(const unsigned int **) b;
     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では176/142=1.24倍になりました。

-''[2-5]''
-ではキーをもっと短くしたらどうでしょうか。今回は最長でも数字が6ケタなので、これをBCD（2進化10進数）という方法で表現すれば32bitに収まりそうです。BCDは簡単に言うと、数字1ケタを4ビット（＝0～15）で表現する方法です。だだし今回は必要な文字として0～9のほかにスペースもあるので、スペースを0として、0～9を1～10に対応させて変換しています。
-qsortの比較関数はこうしました。
 int qscmp(const void *a, const void *b)
 {
     const unsigned int *ca = *(const unsigned int **) a, *cb = *(const unsigned int **) b;
     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-2]''
-世間で一般的に知られているcrit-bit木は、srch1～5, del1のようなことができません。それはそれぞれのデータがソート順で何番目なのかをO(logN)で計算するための情報を持っていないせいです。でもACrit32はそれらの情報を持っているので、これらの問い合わせに応えることができます。その代わり、各ノードのサイズは 3 * sizeof (int) ではなく、 5 * sizeof (int) になっています（ACrin32LxB1の場合）。
||B1|B2|B4|
|pos:ビット位置|1|1|RIGHT:1|
|ptr:ポインタ|2|4|16|
|num:そのポインタの先にいくつデータがあるか|2|4|16|
--numは実はアルゴリズムを工夫すれば、1,3,15にできることが分かっているのですが、処理を単純化して高速にするために、ポインタと同じ数だけ持たせています。
--num==1の時、対応するポインタはデータを指しています。num>=2のとき、対応するポインタはノードを指しています。

** (4) crit-bit木について #4
-''[4-1]''
-これだけいろいろできれば、例えばこんなことができます。
-malloc/free処理を考えます。・・・mallocするときに、要求サイズにできるだけ近い空きブロックを高速に見つけたいです。それはACrit32を使えば簡単にできそうです。

-それでは性能を比べてみたいと思います。まずこんなプログラムを作りました。
 #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_SEC);
     return 0;
 }
-最初に16KBのメモリ領域をn個確保します。次に32KBのメモリ領域を1個確保します。そしてn/2個の16KBのメモリ領域を解放します。このときにメモリの空きがとびとびになるようにします。これで準備完了です。
-ここで free(q); free(p[0]); p[0] = malloc(16KB); q = malloc(32KB); を実行します。これは解放してから確保し直すという、かなり無意味なことをやっています。でもこの処理をK&R型のmalloc()はかなり苦手としています。一番時間がかかるのは q = malloc(32KB); のところです。n/2個の16KBしかない空き領域を読み飛ばして、やっと32KB以上の空きメモリを見つけることができるのです。ここでは n=10 なので大したことはないのですが、nが大きくなると結構な負担になります。
-ただし、それでも1回やったくらいでは大して時間はかからないので、100万回繰り返して、かかった時間を計ります。

-次にACrit32版のほうについてです。以下のようなクラスを作り、initして、本家のmalloc()で1GBくらいを取ってきて、MemManの管理下に組み入れます。あとはすべてMemManに対するmalloc/freeに書き換えるだけです（条件を同じにしないと比較にならないので）。
 AClass(MemMan) {
     ACrit32L0B1 idxSiz; // 空きメモリブロック情報オブジェクトの、sizメンバをキーとするインデックス.
 };
-mallocではidxSizを使って最適な空きメモリブロックをO(logN)で見つけてきます。見つけて必要なメモリを切り取った後に余りが出れば、それはidxSizに登録します。・・・freeでは、前後の領域とマージできるときはマージして、それからidxSizに登録します。
||n=10|n=65536|
|オリジナル（msvcrt.dllのmalloc/freeを使用)|RIGHT:599ms|RIGHT:4178ms|
|ACrit32L0B1を使ったmalloc/free|RIGHT:279ms|RIGHT:533ms|
|ACrit32L0B2を使ったmalloc/free|RIGHT:293ms|RIGHT:427ms|
|ACrit32L0B4を使ったmalloc/free|RIGHT:399ms|RIGHT:493ms|
-これを見ると、「ACrit32L0B1を使ったmalloc/free」がシンプルで一番よさそうに思います。n=10の時点で、すでに標準のmalloc/freeの2倍の速度が出ています。これで、ACrit32L0B1の基本的なオーバヘッド（Nによらないオーバーヘッド）は十分に小さいことが分かります。n=65536では性能の差は圧倒的になっています。
-高性能なmallocとしてはdlmallocが知られていますが、このMemMan-mallocはサイズごとに処理を分けるようなこともなく、ごく単純にK&R型のmallocを速くしたような感じになっています。
-なお、言うまでもないですが、メモリ消費量の観点では、crit-bit木の分も必要になるため、K&R型と比べれば劣っています。

** (5) crit-bit木について #5
-''[5-1]''
-ACrit32L0B1などでは、データオブジェクトの中にアニール済みのキーデータを保持する必要があります。しかしcrit-bit木に登録するために、符号付き整数の符号ビットを反転させたり、浮動小数点形式も加工することになるので、アニールを解いてそれから元に戻すことも容易ではありますが、不便です。そうなるとキーのためのデータと元のデータの両方を保持することになり、メモリ消費量の観点からは好ましくありません。
-そのためオプションとして、若干の速度低下はあるものの、crit-bit木のためのキーデータを一切保持しないで済むモードを付けました。このモードでは必要に応じて無加工のデータからcrit-bit木のためのキーデータを生成します（そういう関数を用意してください、クラスから必要に応じて呼び出します）。
-そもそもcrit-bit木では、キーデータが必要になるのは、データ追加1回につき、2回だけです（追加するデータのキーで1回、登録済みデータのうち、crit-bit木のアルゴリズムで選ばれたデータのキーで1回）。検索1回についてもその程度ですし、削除1回についでもその程度です。ですからqsortの比較関数と比べると、呼ばれる頻度はずっと少ないです。

-''[5-2]''
-結局、crit-bit木の使いどころはどこなのかと考えました。
--[1]ハッシュテーブルの代わりに使う： ハッシュテーブルはうまくいっているときは確かにO(1)（というか厳密にはO(m)ですが）なんですが、衝突が起きてしまうと性能は急激に悪くなってしまいます。つまりワーストケースの性能はかなり悪いわけです。一方でcrit-bit木はベストでもワーストでもO(m)なので、とても安定しています。ただまあポインタをたどる処理は処理的には少し重いので、衝突がほとんどないときのハッシュテーブルの速度は出ないだろうとは思います。でもcrit-bit木にすれば、ハッシュ関数をどうしたらいいかとか、テーブルサイズを動的に拡大縮小するかどうかなどを悩む必要は一切ありません。ハッシュテーブルのオープンアドレス法では、データを消すのは削除マークを入れるしかないですが（ハッシュテーブルを作り直すこともできますが）、crit-bit木ではちゃんと消せて性能が上がります。
--[2]平衡木の代わりに使う： 性能を比較してないので断言できないのですが、よほどキーの長さが長くない限りは、crit-bit木が性能で大きく負けることはなさそうな気がします。メモリ消費量の点からも他の平衡木に比べて何ら見劣りすることはありません（ACrit32は、srch1やsrch3を可能にするために冗長になっていますが）。ディスク上の木構造に有利と言われているB木に勝てるかどうかはわかりません。でもなんか工夫したら、いけそうな感じはします。
--[3]全文検索に使う： 数万字、数百万字、なんならそれ以上のテキストがあったとして、それを先頭から1文字ずつ削りながら、すべてcrit-bit木に登録したとします。ここで探索したい文字列で検索すれば、O(logN)くらいで見つけられると思います。この用途のためにはsuffix-arrayやLCP-arrayが有名ですし、そのほうが消費メモリは少なくて済みますが、しかしこれらは後から検索対象テキストを少量ずつ追加するのには向いていません。一方で、crit-bit木や平衡木なら、少量ずつの追加に十分に対応できます。

-''[5-3]''
-ハッシュテーブルとcrit-bit木での性能比較をやってみました。
-テストに使ったのは、適当なHLX向けのサンプルプログラムをつないで一つのテキストファイルし、それをlexerでトークンに分けて、さらにトークンが1文字以下のものは捨てて2文字以上のものだけにして、トークン文字列をトークン番号に変換する処理を、10万回繰り返す処理です。1文字のトークンを避けたのは、「1文字の場合はサイズが256の配列を作ってそれで一発で求める」という処理を書くと思うので、それ以外の長さのトークンをいかに速く処理できるかを見たかったためです。なお、文字列リテラルには極端に長いものもあって処理が面倒になってきたので、それはすべて"str"と書いてあるとみなして処理しています。結果的にトークンはすべて2～16文字になりました。
-ACrit32L0Bxでは、すべてのキーは16バイトの固定長であるとしました。そうするほうが簡単だったので。ハッシュテーブルのほうは、ハッシュ関数にFNVの32ビット版を使っています。Hash 582 はハッシュテーブルの大きさが582ということです。582は1bitのcrit-bit木を限界まで削ったときと同じ消費メモリの大きさのハッシュテーブルです。
|ACrit32L0B1|RIGHT:1425ms||
|ACrit32L0B2|RIGHT:999ms||
|ACrit32L0B4|RIGHT:746ms|ACrit32ではこれが最速|
|hash 582|RIGHT:879ms||
|hash 512|RIGHT:839ms||
|hash 1024|RIGHT:812ms|ハッシュ関数をカスタマイズしないのならここが限界|
-うーんハッシュテーブルのパワーとはこんなものだったでしょうか？そんなことはないはず！と思って改良しました。ハッシュ関数の計算を16バイト固定にはしないで、長さが短いときは適当に打ち切ることにしました。これでも今回の用途に限れば問題ないはずです。
|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や65536なども試しましたが、そもそも1024の段階でほとんど衝突していないようで、性能向上は見られませんでした。むしろキャッシュヒット率が下がってきて、性能低下するくらいです。

** (6) crit-bit木について #6
-[考察]Crit32L0B1とCrit32L0B4で何が違うか？
--[1]最大で4倍速く枝をたどれる（2つしか入っていないときは1倍）
--[2]16分岐すべてが埋まっていれば・・・B1だと5*sizeof(int)*15, B4だと33*sizeof(int)。だから0.44倍くらい省メモリになる。
-[考察]ハッシュテーブルに対する優位性は？
--たとえば、Alfa, Bravo, Charlie, Delta, Echoみたいなキーだった場合、crit-bitは最初の1文字だけでこれらを区別できることを発見して、そのような木を作る（2文字目以降で分岐することはない）。ハッシュテーブルはそういうことはせずに全部混ぜ込んで（＝そのために時間まで浪費して）テーブルを引く。

タイムスタンプを変更しない

* acl2ライブラリ #2
-(by [[K]], 2022.11.24)

テキスト整形のルールを表示する