namazu-dev(ring)

[Satoru Takabayashi <satoru-t@xxxxxxxxxxxxxxxxxx>]

Satoru Takabayashi <satoru-t@xxxxxxxxxxxxxxxxxx> wrote:

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

改善しました。新しい実装では nmz_mergesort() を廃止して、ソー
トはすべて qsort(3) を使っています。(その方が速いでしょ?)

nmz_mergesort() で保証していた安定なソート (順序を保つ) を
qsort(3) で実現するために、 set_rank() なる関数を導入しまし
た。実に単純な仕掛けです。

安定なソートを実現する仕組み:

  1. ソートを行なう前に set_rank() 関数を呼び出して、現在の
     順序を記録する。これを ranking と呼ぶ。

  2. 比較部を 2重にする。もし、1回目の比較 (本来の比較)で 2
     つの要素が等価ならば、 ranking で再度、比較を行なう。

比較関数の例:

    int field_scmp(const void *p1, const void *p2)
    {
        hlist_data *v1, *v2;
        int r;
    
        v1 = (hlist_data *) p1;
        v2 = (hlist_data *) p2;
    
        r = strcmp(v2->field, v1->field);
        if (r == 0) {
            /* NOTE: comparison "a - b" is not safe for NEGATIVE numbers */
            r = v2->rank - v1->rank;
        }
        return r;
    }

この関数ではまず、

  r = strcmp(v2->field, v1->field);

でフィールドの情報 (Subject: や From: ) で比較を行ない (降順
のソートが標準なので v2, v1 の順)、それが等価ならば、

  r = v2->rank - v1->rank;

で ranking で再度、比較を行ないます。ranking は必ず、正数な
ので、単純に二つの数値を引き算しています。

これで、安定なソートが保証できます。(馬鹿馬鹿しいほど素朴な
方法ですが)

# いかがなものでしょ? > 古川さん

-- Satoru Takabayashi