[Mew-dist 09776] Re: hash on Emacs (toward threading)

[Shigeya Suzuki]

>>>>> "kazu" == 山本和彦  <Kazu> writes:

kazu> Emacs の変数や関数の値の検索にはこの obarray が利用されています。実際
kazu> に obarray という大域変数があるので、評価してみるといいでしょう。この 
kazu> obarray の大きさは 1511 に決め打ちされています。

1511 って prime で、恣意的に選んだ値だと思います。

% /usr/games/factor 1511
1511: 1511


kazu> ここで湧く疑問は、Emacs がたくさん .el を読み込むと、衝突が頻繁に起こ
kazu> り、線形検索の部分が遅くなるのではないかということです。ソースを見た限
kazu> り、ハッシュを動的に大きくするなどの作業はしていないようです。この理解
kazu> は正しいでしょうか？

kazu> ここから本題ですが、obarray を使うと簡易 DB が作成できるので、thread 
kazu> を実装する際に役に立ちます。(Message-ID: に対し、In-Reply-To: を登録す
kazu> るなど。)しかし、メッセージの数が大きくなると効率が落ちるんじゃないで
kazu> しょうか？ 真剣に探しましたが、ハッシュを大きくする方法はないようです。

...

kazu> あと、ハッシュに関して深い知識のある方は、ハッシュはどういうときに大き
kazu> くすべきか教えてもらえると嬉しいです。

深い知識というわけではないけど、そもそも、hash 関数にあった bucket
size ってのがあると思うので、この配列の大きさかえても、関数自体が変わ
らないと意味ないかも。

結局、hash のキーに当たる値から、キーにhash関数を適用したときに、適当
に値が分散するようなhash関数が良いわけで、むやみにbucket sizeを多くし
ても、hash関数自体が対応するものでなければ意味無いでしょう。適度にばら
けていて、かつ、範囲がコンパクトな方が良いでしょう。

あのへんみてるなら、とうぜん見てると思いますが、Emacsのhash関数は、こ
んなんです。これを1511で割ってる。

static int
hash_string (ptr, len)
     unsigned char *ptr;
     int len;
{
  register unsigned char *p = ptr;
  register unsigned char *end = p + len;
  register unsigned char c;
  register int hash = 0;

  while (p != end)
    {
      c = *p++;
      if (c >= 0140) c -= 40;
      hash = ((hash<<3) + (hash>>28) + c);
    }
  return hash & 07777777777;
}

まあ、キーになる値のパターンが変わると、適正な関数とかも変わると思うけ
れど、Message-ID ぐらいの値のふれかただと、最後が com/gov/orgとか jp 
とかあるから、最後の数回のループの値の適用パターンが同じになるから、少
しふれかたが固まるかもしれない。(hash>>28)が、どれだけきくかにかかって
いるかもしれないが、日付とかもエンコードされているのが裏目にでるかもし
れないし。。実際にデータくわせてみないとわからないかも。

あと、Emacs とは関係ないけれど、ヘタにhash関数使うより、昨今のアーキテ
クチャに、そこそこ賢いコンパイラの組み合わせだと、単純なリニアサーチの
方が早かったりします。(ばかっぱやだから) なので、ヘタに凝ったhash関数
作ると失敗します。

結局、どういう文字列を、どのぐらいの長さで、かつ、最終的なレコード数が
何レコードぐらいになるのかのバランス考えないと、良いとか悪いとかは言え
ない。で、間を取ると↑ぐらいになるってことなのではないかと。

僕がこの手の関数作る場合は、ターゲットのキーになる値を実際の関数にかけ
て、振れ具合いみて決めてます。漢字とか混ざっている場合、漢字コードによっ
ても振れ具合いは変わるし(笑) もっとサボっても平気そうなら、手を抜きま
す。

私見としては、Message-ID に対するハッシュ関数というのは、工夫の余地が
比較的低い（かなり傾向があるし、時間的な分散具合いもイヤ）ので、普通の
関数つかう以外に方法ないんじゃないかという気がします。

shigeya