hash (2)
自前でgnuplotをコンパイル
FreeBSDでの出来事さ。portsから簡単に入るんだけど、texとか余計な物が大過ぎて辟易。ならば野良ビルドと思って始めたんだ。そしたら、見事にエラーですよ。
gmake[4]: Entering directory '/tmp/gnuplot-5.4.1/src' c++ -g -O2 -L/usr/local/lib -o gnuplot alloc.o axis.o breaders.o boundary.o color.o command.o contour.o datablock.o datafile.o dynarray.o encoding.o eval.o external.o fit. o gadgets.o getcolor.o graph3d.o graphics.o help.o hidden3d.o history.o internal.o inte rpol.o jitter.o libcerf.o matrix.o misc.o mouse.o multiplot.o parse.o plot.o plot2d.o p lot3d.o pm3d.o readline.o save.o scanner.o set.o show.o specfun.o standard.o stats.o st dfn.o tables.o tabulate.o term.o time.o unset.o util.o util3d.o variable.o version.o vo xelgrid.o vplot.o -lreadline -lncurses -lz -lgd -lm ld: error: undefined symbol: libiconv_open >>> referenced by encoding.c:234 >>> encoding.o:(init_special_chars) :
ports兄貴を参考に、iconvは必要だぞって忠告を受けて、LDFLAGS=-L/usr/local/libは指定しておいたんだけどね。肝心の LIBS=-liconv を忘れていたみたい。
上記のc++の行を適当なファイルにコピーして、最後の部分に -liconv を追加。そのファイルをshellから実行したら、無事にgnuplotが出来上がった。
世の中のMakefileには、肝心な所を隠してしまう奴がいる(そう、最近ではrubyがそうだ)。裏でこそこそやられてしまうと、こういう原始的な事が出来無い。少しは反省して貰いたいな。
hash of mawk
前回見付けてしまったGNUじゃ無いmawkをお取り寄せ。ハッシュがどうなっているか確認。
/*
* FNV-1 hash function
* http://www.isthe.com/chongo/tech/comp/fnv/index.html
*/
unsigned
hash(const char *s)
{
/* FNV-1 */
register unsigned h = 2166136261U;
while (*s) {
h ^= (UChar) (*s++);
h *= 16777619U;
}
return h;
}
こんな案内と共にコードが使われていた。出典が載ってるのは有り難い(上で示したコードは32Bit用なんて事も解るしね)。作者様への礼儀ってもんだろう。色々なソースを見ていると、決して一人ではどうにもなる訳じゃないって事がヒシヒシと感じられるよ。
URLを辿ってみると、色々な所で使われている事が解る。そして、お遊びっぽいお題として、ハッシュ値がZEROになる、入力を求めよなんてのも出てた。これを進化させていくと、ビットコインへ行き着くんですなあ。
sakae@deb:/tmp/mawk-1.3.4-20200120/examples$ mawk -f primes.awk 1950 2000 1951 1973 1979 1987 1993 1997 1999
折角mawkのソースが有るんで、中身の観光をしていたら、例に面白いやつを発見。指定した範囲内の素数を求めるですって。awkでもここまで出来ますって素敵だな。
octave:1> a=primes(1000); octave:2> a(100:110) ans = 541 547 557 563 569 571 577 587 593 599 601
octaveだと、指定した所まで求めておいて、後はスライスしなさい風。
(%i1) primes(8000,8100); (%o1) [8009, 8011, 8017, 8039, 8053, 8059, 8069, 8081, 8087, 8089, 8093]
maximaだと、範囲を指定して求めるのか。
ああ、昔の事を思い出したぞ。LLって言う集会が行われていた。Lightweight Language の自慢大会ね。そこでのお題に、指定されたURLからコンテンツをGETして、内容を検索しろってのが有った。
gawkがそれを実現しててびっくりした。そして強い嫌悪感を抱いた。機能肥大症に罹患してるな。良きUNIXの伝統を忘れているよ。BASHも同じだぞ。って事で、今度はbashしてみる。
hash of bash
sakae@deb:/tmp/bash-5.1.8$ hash hits command 1 /usr/bin/grep 3 /usr/bin/tar 1 /usr/bin/cp 3 /usr/bin/find 2 /usr/bin/gnuplot 1 /usr/bin/man 1 /usr/bin/sync 12 /usr/bin/ls 4 /usr/bin/curl 2 /usr/bin/make 1 /usr/bin/cat 1 /usr/bin/mkdir 5 /usr/bin/emacs 1 /usr/bin/rm
bashは、ユーザーの挙動を監視してるんです。 .bash_history だけかと思ったら、他にもhashなんていう内部コマンドを持ってて、ユーザーの嗜好を把握してましたよ。遣り過ぎ、監視社会は、ここまで来たって、いつかクロ現に取あげられるに違いない。
hashlib.c にコードが置かれていた。その冒頭部分。
/* This is the best 32-bit string hash function I found. It's one of the Fowler-Noll-Vo family (FNV-1). The magic is in the interesting relationship between the special prime 16777619 (2^24 + 403) and 2^32 and 2^8. */ #define FNV_OFFSET 2166136261 #define FNV_PRIME 16777619 /* If you want to use 64 bits, use FNV_OFFSET 14695981039346656037 FNV_PRIME 1099511628211 */
素晴しいハッシュ関数を見付けだぞ。俺って凄いなって、餓鬼だな。御礼の一言ぐらい述べておけよ。あるいは出典のURLを載せておくとかしろよ。
そうそう、bashはawkの真似をしたくて、bashで連想配列を搭載してます。てんこ盛り過ぎると思うのは、オイラーだけかな。
other hash
他にハッシュ関数はないかと手元の本を漁ってみたよ。そしたら今は亡きユニマガの連載からアルゴリズムを取り出してムックにしたものが出て来た。
int as(const char *s, int n){
unsigned h =0, g;
char *p;
for (p = s; *p ; p++) {
h = (h << 4) + (*p);
if (g = h & 0xf0000000) {
h = h ^ (g >> 24);
h = h ^ g;
}
}
return h % n;
}
解説によると、1990年に出版されたコンパイラ II 技法 原理 ツールって本からの抜粋。色々なデータを与えてテストした所、良い結果が得られたとの事。そう言われると自分でも確かめてみたくなる。何せ古い時代のものですからね。現代に通用するか？
test hash
前回は、世界の単語を餌にしてハッシュを取り、衝突数の最小値、最大値あたりを調べた。それって、統計的にどうよ。ばらつきとかをさっぱり検証してない、小学生の研究だな。少し大人になれよ。統計言語Rの登場か。まて、そんな大上段なツールを取り出さなくても済むぞ。そう、かの昔、血圧グラフをやった時、gnuplotの統計機能を使ったんだ。
vbox$ ./a.out | cut -f 2 | gnuplot -e 'stats "-"'
a.outは前回の最後にちょろっと作ったやつ。cutを使って値だけ取出、それをgnuplotに渡してあげる。"-" は、標準入力からのデータ取込になる。オイラーこういうバラック方式のプログラミング大好きよ。結果は、
* FILE: Records: 100 Out of range: 0 Invalid: 0 Header records: 0 Blank: 0 Data Blocks: 1 * COLUMN: Mean: 1027.7400 Std Dev: 817.7511 Sample StdDev: 821.8708 Skewness: 1.1329 Kurtosis: 2.5087 Avg Dev: 695.1900 Sum: 102774.0000 Sum Sq.: 1.72497e+08 Mean Err.: 81.7751 Std Dev Err.: 57.8237 Skewness Err.: 0.2449 Kurtosis Err.: 0.4899 Minimum: 291.0000 [ 14] ; 0% Maximum: 3056.0000 [ 71] ; 100% Quartile: 519.0000 ; 25% Median: 649.0000 ; 50% Quartile: 1498.5000 ; 75%
100個のデータを受取ました(バケット数)。その平均値は、1027.74(衝突の平均)で標準偏差は817.7511でした。データの合計は102774でした。リナの単語悵に登録されてる個数に相当する。
Minimum以下は、株屋さんが大好きなローソクチャート(箱ひげ図)の元データになる。データを昇順に並べた時、それぞれの個数の%における値を表している。Minimum/Maximumの欄にある鍵括弧内の数値は、インデックス番号だ。
データ数の半分は519から1498の範囲に収まっていると読めれば、株に手を出してもOK。保証はしないけど。
これで大分大人っぽくなったけど、株屋さんなら、まだ半人前。Aの銘柄だけに入れ込んでいたら負けるぞ。少なくともB銘柄とも同時比較したい。するべき！
ならば、cutしたデータ一旦ファイルに落とす。もうひとつも別なファイルの落とす。両者を、paste a.txt b.txt >ab.txt とかやって、それを gnuplot -e 'stats "ab.txt"' すれば良い。面倒この上ない。面倒は罪って思うのは(自称)ハッカーの芽生えだ。何とかしたい。
そして、何とかついでに、世界の単語だけじゃなくてもっと現実的なデータも扱いたい。例えば、ソースコードに現れる単語(変数名)とか、マニュアル類とか、格調高くシェークスピアの小説とかね。
これらは、残念ながら一単語/行にはなっていない。まあ、あたりまえだ。１行に複数の単語がスペース区切で並んでいる。この普通の書式の文書を扱かうようにしておきたい。
そんな願いの多く(オーク)は、awkにお任せあれ。これ、寒いオヤジギャクだな。いえ違います。awkをエー・ダブリュー・ケーと読まないでと、作者の方々は言ってます。オークと読んで欲しいと。監督と呼ばないで、ビッグボスって呼んでねって、あの新庄ちゃんが、同じフレーズを使ってたね。
vbox$ cat main.c | awk '{for(i=1; i<=NF; i++) print $i}'
vbox$ man pwd | col -b | awk '{for(i=1; i<=NF; i++) print $i}'
出たな、一行野郎。たったこれだけで、C言語のソース(何でもいいけど)を、全行に渡り、スペース区切で単語に分解してくれます。2番目は、巷に溢れているマニュアルを単語に分解する例です。
何？ 分解した中に記号が含まれててうざい。C言語が許す変数(関数)名だけを取り出したい。それをawkでやりたい。重複を除きたいんで連想配列で何とかなりませんか？ 何もかもawkに押し付けてはいけません。身動きが出来無くなりますから。そんなのはunixの専門家に任せましょう。
egrep '^[A-Za-z]' で名前とおぼしき奴を抜き出す(ちょっと緩い設定なんで注意の事)。重複除きは、sort | uniq の定番組み合わせとかね。
次は、前回のアプリの改変。問題はパイプから入力文書を受け取る方法。セキュリティー的理由により、getsがOpenBSDではサポートされていないんだ。まことに以て潔い。しょうがなしに、fgetsを流用する。巻末にコードを載せたので参考に。
vbox$ cat /usr/share/dict/words | ./a.out | gnuplot -e 'stat "-"' * FILE: Records: 211 Out of range: 0 Invalid: 0 Column headers: 0 Blank: 0 Data Blocks: 1 * COLUMNS: Mean: 1118.3460 1118.3460 Std Dev: 34.3403 34.1761 Sample StdDev: 34.4220 34.2574 Skewness: -0.0452 -0.0427 Kurtosis: 3.1081 2.8379 Avg Dev: 26.5722 27.2762 Sum: 235971.0000 235971.0000 Sum Sq.: 2.64146e+08 2.64144e+08 Mean Err.: 2.3641 2.3528 Std Dev Err.: 1.6717 1.6637 Skewness Err.: 0.1686 0.1686 Kurtosis Err.: 0.3373 0.3373 Minimum: 1032.0000 [113] 1030.0000 [ 73] Maximum: 1204.0000 [ 17] 1222.0000 [160] Quartile: 1099.0000 1095.0000 Median: 1118.0000 1119.0000 Quartile: 1139.0000 1141.0000 Linear Model: y = -0.04976 x + 1174 Slope: -0.04976 +- 0.06875 Intercept: 1174 +- 76.93 Correlation: r = -0.05 Sum xy: 2.639e+08
gnuplotに２列のデータを渡すと、その列をX、Yとみなして、散布図と解釈してくれる。だから、ちょっと解析データが追加されてたりする。Linier Modelで、回歸直線を示してくれたり、Correlationで、相関が出てきたりしてる。AIとかにかぶれていなければ、普段使いの統計解析としては、まあ十分だろう。
で肝心のハッシュの性能だけど、左側は1990年代の技法の結果。右側がmawkで採用してた自慢のやつだ。バケットサイズが211と比較的緩めだ。両者共、優劣をつけがたい。
今度は、バケットサイズを素人っぽく、100に変更(息をするがごとく、再コンパイルね)
Mean: 2359.7100 2359.7100 Std Dev: 888.8830 50.2443 Minimum: 1421.0000 [ 62] 2243.0000 [ 46] Maximum: 3932.0000 [ 73] 2513.0000 [ 53] Quartile: 1703.0000 2326.0000 Median: 2061.0000 2356.5000 Quartile: 3008.0000 2393.5000
1990年式は、バケットサイズに制約がありそう。ならば素数の101にしてみる。
Mean: 2336.3465 2336.3465 Std Dev: 50.5852 42.1930 Minimum: 2220.0000 [ 85] 2244.0000 [ 15] Maximum: 2486.0000 [ 66] 2457.0000 [ 61] Quartile: 2301.0000 2302.0000 Median: 2336.0000 2343.0000 Quartile: 2366.0000 2368.0000
以上は、32Bit環境のOpenBSDだ。64Bit環境では、どうなる？ 1990年式は通用するのか？ 興味ある所だ。結果は一致したよ。
気分転換で、debian(64Bit)で、gccのman を題材に、バケット数は100 って条件。総単語数２万弱の結果。
Mean: 196.9700 196.9700 Std Dev: 57.3635 12.9348 Minimum: 125.0000 [ 19] 167.0000 [ 96] Maximum: 323.0000 [ 50] 227.0000 [ 70] Quartile: 157.5000 189.0000 Median: 173.0000 198.0000 Quartile: 235.0000 206.0000
今度はソースが供給されてるって事で、golangで試してみる。むちゃくちゃ単語が長いので、それなりにバッファーサイズを大きくしておく事。小さいとセグフォするぞ。
Mean: 3556.0300 3556.0300 Std Dev: 1565.5974 61.4606 Sum: 355603.0000 355603.0000 Minimum: 1819.0000 [ 31] 3356.0000 [ 58] Maximum: 6107.0000 [ 8] 3697.0000 [ 67] Quartile: 2213.0000 3515.0000 Median: 3168.5000 3564.5000 Quartile: 4912.0000 3592.5000
測定条件は、下記。って、あの人が好きなパイプ・プログラミングだな。
sakae@pen:/tmp/z$ find /usr/local/go/src/cmd -name '*.go' | xargs cat |\
awk '{for(i=1; i<=NF; i++) print $i}' | sort | uniq |\
./a.out | gnuplot -e 'stat "-"'
ああ、今回は思い出したように、awkを使ってしまったけど、普通は tr ' ' '\n' を使うかな。
Segmentation fault
goのコードの分解実験の時、セグフォが発生したんで注意って、サラリと書いた。良い機会なので、検証してみる。
容易に実験出来るように、main関数内にあるbuf[256]てなってる所を、buf[6]にした。それから、HASHMAXも小くして(5)、観測が容易になるようにした。
sakae@deb:/tmp/z$ echo 123 | ./a.out 1 0 0 1 0 0 0 0 0 0 sakae@deb:/tmp/z$ echo 1234 | ./a.out 0 0 0 1 1 0 0 0 0 0 sakae@deb:/tmp/z$ echo 12345 | ./a.out Segmentation fault
おめでとう、見事に現象再現。リナはまずい事が発生しても、証拠を残さない設定になってるんで、当局の要請で、ゲロるように設定(そう言えば、久し振りの忘年会はゲロの季節でもあります)。
sakae@deb:/tmp/z$ ulimit -c unlimited sakae@deb:/tmp/z$ cc -g ab.c sakae@deb:/tmp/z$ echo 12345 | ./a.out Segmentation fault (core dumped)
sakae@deb:/tmp/z$ gdb -q a.out core
Reading symbols from a.out...
[New LWP 1529]
Core was generated by `./a.out'.
Program terminated with signal SIGSEGV, Segmentation fault.
#0 0x0048536c in main () at ab.c:50
50 *p = '\0';
(gdb) p/x p
$1 = 0x0
(gdb) p/x buf
$2 = {0x31, 0x32, 0x33, 0x34, 0x35, 0x0}
(gdb) p/x &buf
$3 = 0xbff7e432
(gdb) p/x &p
$4 = 0xbff7e438
解決策はどうよ。
#define _GNU_SOURCE /* See feature_test_macros(7) */ #include <string.h> char *strchrnul(const char *s, int c); The strchrnul() function is like strchr() except that if c is not found in s, then it returns a pointer to the null byte at the end of s, rather than NULL.
GNU流の解決方法が出てた。
sakae@deb:/tmp/z$ echo 12345 | ./a.out 2 0 0 1 0 0 0 0 0 1
これで枕を高くして眠れる。もう幾つ寝るとお正月？ ちと、気が早いか。何故結果が２になる？ GNUがお化けを送り込んできたか。それを解決出来無ければ、正月は来ないさ。
code
#include <stdio.h>
#include <string.h>
#define HASHMAX 211
int kr(const char *s, int n){
unsigned hashval;
for (hashval = 0; *s != '\0'; s++)
hashval += *s;
return hashval % n;
}
int nkr(const char *s, int n){
unsigned hashval;
for (hashval = 0; *s != '\0'; s++)
hashval += *s + 31 * hashval;
return hashval % n;
}
unsigned fnv(const char *s, int n) {
register unsigned h = 2166136261U;
while (*s) {
h ^= (unsigned char) (*s++);
h *= 16777619U;
}
return h % n;
}
int as(const char *s, int n){
unsigned h =0, g;
const char *p;
for (p = s; *p ; p++) {
h = (h << 4) + (*p);
if ((g = h & 0xf0000000)) {
h = h ^ (g >> 24);
h = h ^ g;
}
}
return h % n;
}
int main(){
char buf[256], *p;
FILE *fp;
int a[HASHMAX], b[HASHMAX], i;
for (i=0; i<HASHMAX; i++) a[i] = b[i] = 0;
while (fgets(buf, sizeof(buf), stdin) != NULL) {
p = strchr(buf, '\n');
*p = '\0';
a[ as(buf, HASHMAX) ] += 1;
b[ fnv(buf, HASHMAX) ] += 1;
}
for (i=0; i<HASHMAX; i++) printf("%d\t%d\n", a[i], b[i]);
}