パスワードを忘れた? アカウント作成
462966 journal

cheekcatの日記: 最小hash関数

日記 by cheekcat

ひさしぶりにすごいコードを見た

お題は

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
print
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)
    print

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
typodupeerror

ナニゲにアレゲなのは、ナニゲなアレゲ -- アレゲ研究家

読み込み中...