素数ゼミ
なんか面白い記事見つけた。
去年の2学期の実験で日本語形態素解析プログラムの作成をした時に
線形探索→二分探索→ハッシュテーブル→(ダブルアレイ)
といった感じで高速化をしていたのだけれど、ふとその時のハッシュ関数の実装(というか素数周りどうなってるのか)が気になったので当時のコードを引っ張り出してきて、ついでに素数について少し調べてたらさっきのサイトにたどり着いた。
ハッシュテーブルを用意して、データを格納する際になるべく衝突が少なくなるように素数を使って...というプロセスと、自然界における様々な周期のセミとの競合を防ぐために素数周期で地上に出てくるセミ...衝突・競合というある種の同じ問題に同じ解決法が用いられているって面白い。
ちなみに僕が実装で使ってたハッシュ関数を晒してみる。
いろいろ突っ込みどころあるけど、いろんな素数を使って衝突回数を数えてチューニングしたのは面白かった。
long hash(char *s) { int i,h = 1; int L = strlen(s); for (i = 0; i < L; i++) h = h * 137 + s[i]; return labs(h) % 4999991; }
そういえば完全ハッシュ関数あたりを調べたいなーと思っていたのに調べてなかったから今月中に調べてみるか(｀・ω・´)
