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

[Shun-ichi GOTO ( 後藤 俊一 )]

後藤＠太陽計測です

# hashとか、基本はクリアしているつもりですが、決して詳しくはないです。

>>>>> at Tue, 20 Jul 1999 00:01:47 +0900
>>>>> shigeya <shigeya at example.com> said,
>>>>> "kazu" == 山本和彦  <Kazu> writes:

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

...かどうかはなんともいえませんが、hash関数に凝るのは、key集合が固定で、
それ用の perfect関数をつくるときだけだろうとは思います。


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

obarrayのようなものは、どんなkey文字列が与えられるか分かりませんから、そ
ういう割りきりは重要で、そこに凝っても効果は上がらないのは容易に想像でき
ますし、実際ハッシュとしての効果はEmacsのあの関数で十分有ると思います。


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

そうですかねぇ、、、そんなことないと思うのですが、、、(^^;
でも分散を調べてみるのは一度やってみたいですね。

ただ、Emacs内で検索しようとすると、どうしてもelispコードでループする部分
が出てきてしまうので、そういう場合とに比べれば格段に差が出ると思います。
ただ、internするということは、symbolを作る/保持するということなので、そ
の分のメモリコストなどを加味して考えるとどんなもんでしょうかねぇ。。。

件のMUEというコードに関していえば、message-id以外にも、一意の文字列とし
たいものはみんなシンボルにしてハッシュに突っ込んじゃってます。それは、重
複した文字列を持たなくて済ませる目的と、一致検出の容易性(eqによる比較)の
ためです。

依然個人的興味で 1500通程度のメッセージのフォルダで、MUEによるシンボル
obarray構造と、Wanderlustのデータ構造とで比較してみて、見た目のメモリ消
費量はほとんど違わないという(かなり適当だけど)結果を得たので、実装の一例
としては、結構いけるかな、とは思ってます。汎用性と抽象性はかなり負けてま
すが、スレッド構築、サマリ描画のスピードは結構勝っていたように記憶してま
す。あと、scanスピードも負けてた。bodyのdigest作成はやはりコスト高。


--- Regards,
 Shun-ichi Goto  <gotoh at example.com>
   R&D Group, TAIYO Corp., Tokyo, JAPAN