単連結リストの整列 #67 無駄を消す

C

無用な比較は最初のループ以外のループであるので、listsort関数の

listsort.c
...snip
    for (; b == 0 && q != next(list, head(list, listarg), listarg); q = s) {
...snip
        while (p != q) {
...snip
            if (issup(p, s, arg)) {
...snip

の部分、二回目以降のループを司るfor-while二重ループ内のissupの過剰呼び出しでなされていると思われる。
たぶん内側のループの終了条件が設計意図と異なっているのだろう。

というわけで、ざっくりソースを眺めてへろっと変更してみた。

listsort.c
#include "listsort.h"

void listsort(
    void *list,
    void *(*head)(const void *, void *),
    void *(*next)(const void *, const void *, void *),
    int (*isvalid)(const void *, const void *, void *),
    void (*swap)(void *, void *, void *, void *),
    void *listarg,
    int (*issup)(const void *, const void *, void *),
    void *arg
) {
    void *p, *q, *r, *s;
    int b = 1;
    q = head(list, listarg);
    if (! isvalid(list, q, listarg)) return;
    r = next(list, q, listarg);
    if (! isvalid(list, r, listarg)) return;
    for (;;) {
        if (issup(q, r, arg)) {
            swap(list, q, r, listarg);
            s = next(list, q, listarg);
            b = 0;
        } else {
            s = next(list, r, listarg);
            q = r;
        }
        if (! isvalid(list, s, listarg)) break;
        r = s;
    }
    for (; b == 0 && q != next(list, head(list, listarg), listarg); q = p) {
        b = 1;
        p = head(list, listarg);
        for (s = next(list, p, listarg); s != q; s = next(list, p, listarg)) {
            if (issup(p, s, arg)) {
                swap(list, p, s, listarg);
                b = 0;
            } else {
                p = s;
            }
        }
    }
}

何ということはない。無駄を生み出していた原因はあっさり分かった。
内側のループは先頭側の隣接要素pと整列済み要素列の先頭qとが一致するまで回っていた。
したがって末尾側の隣接要素sがqに一致しても処理が続いてしまっていたのだ。

そこで、内側のループの継続条件をp != qからs != qに変更した。
その継続条件を判断する前にsを知る必要があり、
これと、次の要素の組へ進むために必要なsを求める式をループ内の先頭から最後へ移動することから、
内側のループをwhile文からfor文での表現に変えた。sが制御変数となっていることで綺麗にまとまる。
ループ終了時にはその直前に隣接要素の交換があってもなくてもpがそのループにおける最大値を示すので、
外側のループで次のループが始まる前に整列済み要素列の先頭qに設定すべきはpとなる。
また変更前は必要だった隣接要素の非交換時のpとsの参照値の交換*1は、
sが外側のループで不要となったため、sのpへの代入だけで済むようになっている。

変更したlistsortを使って前回の実験コードを動かしてみる。

10 9 8 7 6 5 4 3 2 1
issup: 10, 9
issup: 10, 8
issup: 10, 7
issup: 10, 6
issup: 10, 5
issup: 10, 4
issup: 10, 3
issup: 10, 2
issup: 10, 1
issup: 9, 8
issup: 9, 7
issup: 9, 6
issup: 9, 5
issup: 9, 4
issup: 9, 3
issup: 9, 2
issup: 9, 1
issup: 8, 7
issup: 8, 6
issup: 8, 5
issup: 8, 4
issup: 8, 3
issup: 8, 2
issup: 8, 1
issup: 7, 6
issup: 7, 5
issup: 7, 4
issup: 7, 3
issup: 7, 2
issup: 7, 1
issup: 6, 5
issup: 6, 4
issup: 6, 3
issup: 6, 2
issup: 6, 1
issup: 5, 4
issup: 5, 3
issup: 5, 2
issup: 5, 1
issup: 4, 3
issup: 4, 2
issup: 4, 1
issup: 3, 2
issup: 3, 1
issup: 2, 1
1 2 3 4 5 6 7 8 9 10
#comparisons=45, #swaps=45
issup: 1, 2
issup: 2, 3
issup: 3, 4
issup: 4, 5
issup: 5, 6
issup: 6, 7
issup: 7, 8
issup: 8, 9
issup: 9, 10
1 2 3 4 5 6 7 8 9 10
#comparisons=9, #swaps=0

今度は降順を昇順に整列させる処理で比較回数も交換回数も最悪ケースの理論値45回にきちんとなった。
無用な比較が行われることがなくなったのだ。
昇順を昇順に整列させる処理はもちろん今まで通り9回の比較と0回の交換のままである。

*1:pとsが指し示す先のリスト上での交換でなくpとsの参照値そのものの交換