namazu-dev(ring)

[Satoru Takabayashi <satoru-t@xxxxxxxxxxxxxxxxxx>]

Rei FURUKAWA <furukawa@xxxxxxxxxxxx> wrote:

>satoru-t> >まともな方法が思いついたので、午後にでも改良します。
>satoru-t> 
>satoru-t> 速くなりました。フィールド指定のソートがそこそこの速度で行な
>satoru-t> えます。お試しくださいませ。
>
>自分で作るときの参考にしたいので、「安易な実装」「まともな方法」が、
>どんなものだったか、簡単に教えていただけますでしょうか？

簡単に言うと、

  安易な実装: ソートの比較部の中で NMZ.field.* をアクセスする
  まともな方法: ソートの前に、必要な NMZ.field.* を読み込んでおく

です。「安易な実装」では、ソートの比較回数を n log n とする
と、100件の検索結果をソートするのにおおよそ 460回のディスク
アクセスが生じる計算になります。遅くて当然です。

ところで、「まともな方法」では NMZ.field.* を高速にソートす
るために、qsort(3) を使っています。

元々、Namazu は

  1. 必ず最初に日付でマージソートする
  2. 必要とあればスコアでマージソートする
  3. 必要とあればソート結果を反転する

という手順でソートを行なっており、安定なソートアルゴリズムで
あるマージソートを採用しています。そのため、2のソートが終わっ
た時点で、スコアが同じ要素については 1 でソートされた順序が
保たれます。(スコアが同じときは文書の新しい順に表示される)

フィールド指定によるソートは 2の時点でスコアによるソートの代
わりに行なわれます。そして、マージソートではなく qsort(3) が
用いられるため、 1 でソートされた順序は保たれません。

…と思っていたら、うちの環境 (Linux 2.0.36 + libc5.4.44) の 
qsort(3) はどうも安定なソートアルゴリズムらしく、順序が保た
れているように見えます。man 3 qsort には

|       The comparison function must return an integer less  than,
|       equal  to,  or  greater than zero if the first argument is
|       considered to be respectively  less  than,  equal  to,  or
|       greater than the second.  If two members compare as equal,
|       their order in the sorted array is undefined.

とあり、"If two members compare as equal, their order in the
sorted array is undefined." とのことですが、一般的にはどうな
のでしょうね?

# 現状では qsort(3) で文字列の並びを数値化して 
# nmz_mergesort() でソートし直すという変な操作を行なっていま
# す (手っ取り早く実装しようと思ったらこうなった)。この仕様
# は気持ちが悪いので、のちほど改善するつもりです。


>(a) make clean ができません。(gmake clean はできます) 
(snip)
>(b) Append がうまくいかないようです。

これらは別のメイルにて。(まだ直していない)

-- Satoru Takabayashi