Minimal Perfect Hashing
gcc -m64 でコンパイルするとうまくいかない。gcc -m32 だと動く。生成されたtab[]がでかい。
生成された phash.c も -m32 じゃないとうまく動かなかったりする。
$ head allmoves.txt 00110012 00120012 00110013 00120013 （中略） $ ./perfect -hm <allmoves.txt Read in 8970 keys found distinct (A,B) on attempt 798 fail to map group of size 11 for tab size 1024 found distinct (A,B) on attempt 2179 fail to map group of size 12 for tab size 1024 （中略） fail to map group of size 3 for tab size 2048 found distinct (A,B) on attempt 4843 fail to map group of size 7 for tab size 2048 found distinct (A,B) on attempt 4860 built perfect hash table of size 2048 Wrote phash.h Wrote phash.c Cleaned up
こんな関数ができた。チェックしたけど、ちゃんと最小完全ハッシュになってる。素晴らしいなー。
tabの大きさが2048もあるんだけど、小さくできたりするんだろうか。
/* small adjustments to _a_ to make values distinct */
ub2 tab[] = {
7360,1412,3608,1548,5637,5373,3838,249,
0,15642,1768,0,788,2534,3228,3071,
(中略)
1987,15527,5375,1984,7293,2590,7259,6522,
};
/* The hash function */
ub4 phash(val)
ub4 val;
{
ub4 a, b, rsl;
val += 0xa52ad41c;
val ^= (val >> 16);
val += (val << 8);
val ^= (val >> 4);
b = (val >> 8) & 0x7ff;
a = val >> 19;
rsl = (a^tab[b]);
return rsl;
}できた関数は-m64でコンパイルすると動かない。1996年のプログラムだから32bit CPU前提なんだな。そのころの64bit環境ってalphaぐらい? なので、long intが32bitだと思ってる。standard.hの中のub4の定義を変えれば一応動く。
standard.h全部は不要だから、ub2とub4の定義だけもってくるか、phash.cを書き換えた方が早いかも。bonanzaは書き換えているようだ。
diff -u standard.h.orig standard.h --- standard.h.orig 2012-04-10 09:29:56.253191724 +0900 +++ standard.h 2012-04-10 09:29:37.220192384 +0900 @@ -1,3 +1,7 @@ +#include <stdlib.h> +#include <memory.h> +#include <string.h> +#include <bits/types.h> /* ------------------------------------------------------------------------------ Standard definitions and types, Bob Jenkins @@ -18,7 +22,7 @@ #define UB8BITS 64 typedef signed long long sb8; #define SB8MAXVAL 0x7fffffffffffffffLL -typedef unsigned long int ub4; /* unsigned 4-byte quantities */ +typedef __uint32_t ub4; #define UB4MAXVAL 0xffffffff typedef signed long int sb4; #define UB4BITS 32
メモ：
