cheekcatの日記: 最小hash関数
ひさしぶりにすごいコードを見た
お題は
2^a (1≦a≦9)を渡されたときaを求める方法で何かいい物はありませんか?
なるべくループやlogを使わない物がいいです
これの解答にこんなが来た。
"_\1\6\2\011\7\3__\5\010_\4"[n*0xCA030FF>>28];
もしくは
"\1\2\3\010\6\4\011__\7\5"[n*0x5300000>>28];
これは
#include <stdio.h>
#include <math.h>
int main()
{
int i;
for (i=1; i<10; i++){
int n = pow(2,i);
printf("%d %2d %2d\n",i,(unsigned int)n*0x5300000>>28,(unsigned int)n*0xCA030FF>>28);
}
return 0;
}
こういうコードを実行すれば原理がつかめる。
1 0 1
2 1 3
3 2 6
4 5 12
5 10 9
6 4 2
7 9 5
8 3 10
9 6 4
入力に対して出力が完全にばらけるようになっている。
0x53 = 01010011 (2)
これを bit shift した時、 int の幅 32bit で切り詰められることを考慮すると
1 0 => 0000 = 0
2 01 => 0001 = 1
3 010 => 0010 = 2
4 0101 => 0101 = 5
5 01010 => 1010 = 10
6 010100 => 0100 = 4
7 0101001 => 1001 = 9
8 01010011 => 0011 = 3
9 010100110 => 0110 = 6
となる。 そして、文字列を lookup すると答が出るわけですね。
さて、この完全 hash 関数の作りかた。適当なものでいいならともかく最小を探す
ならプログラムにたよるのがよいだろう。Python ならこんな感じか。
# でも、なんとなく法則がありそうな感じもする
generator って初めて使ったけど楽しい。
総当りしてるからこのプログラムは遅い。 ほんとは gen_bit あたりで適当に
木を切っていかなきゃいけないのだろうね。
#!/usr/bin/python
import sys
from itertools import count
import re
def bitstr(string, bits):
return "0"*(bits-len(string))+string[-bits:]
def gen_bit_len(seed,length):
if len(seed) == length:
yield seed
else:
gen = gen_bit_len(seed+"0",length)
for x in gen:
yield x
gen = gen_bit_len(seed+"1",length)
for x in gen:
yield x
def gen_bit(n):
g = count(n)
for x in g:
gen = gen_bit_len("",x)
for y in gen:
yield y
def two2ten(two):
res=0
for x in range(1,len(two)+1):
res+=int(two[-x])*(2**(x-1))
return res
def gen_hash(n, bits):
gen = gen_bit(n)
for curbit in gen:
bitmap = {}
ok = True
for x in range(1,n+1):
tmp = bitstr(curbit[:x],bits)
if bitmap.has_key(tmp):
ok = False
break
bitmap[tmp] = 1
if ok:
yield curbit
if not len(sys.argv) in (2,3):
print "Usage: %s <number> [<bit>]" % sys.argv[0]
sys.exit(1)
n = int(sys.argv[1])
mbits = 1
while True:
if n <= 2**mbits:
break
mbits+=1
if len(sys.argv) == 3:
bits = int(sys.argv[2])
else:
bits = mbits
if bits < mbits:
print "bits too small, should be larger than %d" % mbits-1
sys.exit(1)
min_len = -1
hash_list = []
min_hash = -1
print "Start %d bit search" % bits
for curbit in gen_hash(n, bits):
if min_len <> -1 and min_len < len(curbit):
break
min_len = len(curbit)
m = -1
for x in range(1,n+1):
ten = two2ten(bitstr(curbit[:x],bits))
if m < ten:
m = ten
if min_hash <> -1 and min_hash < m:
continue
elif m < min_hash:
hash_list = []
min_hash = m
hash_list.append(curbit)
for curbit in hash_list:
bitmap = ["_"] * (2**bits)
for x in range(1,n+1):
tmp_str = bitstr(curbit[:x],bits)
ten = two2ten(tmp_str)
if m < ten:
m = ten
bitmap[ten] = r"\0%o" % x
print "%5d => %5d (%s)" % (x, ten, tmp_str)
print curbit
s = ''.join(bitmap[:m+1])
print "\"%s\"(0x%X<<i)>>%d" % (s, two2ten(curbit+"0"*(32-len(curbit))), 32-bits)
最小hash関数 More ログイン