a24_aQSort のバックアップ(No.4)

バックアップ一覧
差分を表示
現在との差分を表示
ソースを表示
a24_aQSort へ行く。
- 1 (2024-09-03 (火) 17:53:10)
- 2 (2024-09-03 (火) 20:53:52)
- 3 (2024-09-03 (火) 22:32:27)
- 4 (2024-09-04 (水) 09:32:20)
- 5 (2024-09-04 (水) 23:44:00)

once_aQSort

(by K, 2024.09.03)

(1) ver.1.00 [2024.09.03] (200行)

#define aQSortFast(Mod, Typ, CmpFnc)    ACat3(aQSortFast_, Mod, CmpFnc)
#define aQSort(Mod, Typ)                ACat3(aQSort_, Mod, Typ)

// Mod: 1=a0, a1がある.
// Mod: 2=wがある.
// Mod: 4=関数は非インライン.
// Mod: 8=Typのかわりに一般サイズ.
// Mod:16=N=3の高速化を利用しない.
// Mod:32=double-selection-sortを使わない.

#longdef ALongdef_QSortFast(Mod, Typ, CmpFnc)

#if ((Mod & 6) == 0)
    #define cmp(a, b, w)   CmpFnc(a, b)
#elif ((Mod & 6) == 2)
    #define cmp(a, b, w)   CmpFnc(a, b, w)
#elif ((Mod & 6) == 4)
    #define cmp(a, b, w)   cmp_(a, b)
#elif ((Mod & 6) == 6)
    #define cmp(a, b, w)   cmp_(a, b, w)
#endif

#if ((Mod & 15) == 0)
AStatic void aQSortFast(Mod, Typ, CmpFnc)(Typ *bas, AInt n)
#elif ((Mod & 15) == 1)
AStatic void aQSortFast(Mod, Typ, CmpFnc)(Typ *bas, AInt n, Typ *a0, Typ *a1)
#elif ((Mod & 15) == 2)
AStatic void aQSortFast(Mod, Typ, CmpFnc)(Typ *bas, AInt n, void *w)
#elif ((Mod & 15) == 3)
AStatic void aQSortFast(Mod, Typ, CmpFnc)(Typ *bas, AInt n, Typ *a0, Typ *a1, void *w)
#elif ((Mod & 15) == 4)
AStatic void aQSort(Mod, Typ)(Typ *bas, AInt n, int (*cmp_)(const void *, const void *))
#elif ((Mod & 15) == 5)
AStatic void aQSort(Mod, Typ)(Typ *bas, AInt n, Typ *a0, Typ *a1, int (*cmp_)(const void *, const void *))
#elif ((Mod & 15) == 6)
AStatic void aQSort(Mod, Typ)(Typ *bas, AInt n, int (*cmp_)(const void *, const void *, void *), void *w)
#elif ((Mod & 15) == 7)
AStatic void aQSort(Mod, Typ)(Typ *bas, AInt n, Typ *a0, Typ *a1, int (*cmp_)(const void *, const void *, void *), void *w)
#elif ((Mod & 15) == 12)
AStatic void aQSort(Mod, Typ)(void *bas_, AInt n, AInt sz, int (*cmp_)(const void *, const void *))
#elif ((Mod & 15) == 13)
AStatic void aQSort(Mod, Typ)(void *bas_, AInt n, AInt sz, void *a0_, void *a1_, int (*cmp_)(const void *, const void *))
#elif ((Mod & 15) == 14)
AStatic void aQSort(Mod, Typ)(void *bas_, AInt n, AInt sz, int (*cmp_)(const void *, const void *, void *), void *w)
#elif ((Mod & 15) == 15)
AStatic void aQSort(Mod, Typ)(void *bas_, AInt n, AInt sz, void *a0_, void *a1_, int (*cmp_)(const void *, const void *, void *), void *w)
#endif
{
    n--;
    if (n <= 0) return; // N=1
    #if ((Mod & 8) != 0)
        char *bas = bas_;
        #if ((Mod & 1) != 0)
            char *a0 = a0_, *a1 = a1_;
        #endif
    #endif
    #if ((Mod & 1) != 0)
        if (a1 <= bas) return;
    #endif
    #if ((Mod & 8) == 0)
        Typ *bi = bas; Typ *bj = bas + n; Typ *bk; Typ c;
        #define Step    1
        #define Swap2(x, y)      c = *x; *x = *y; *y = c;
        #define Swap3(x, y, z)   c = *x; *x = *y; *y = *z; *z = c;
    #else
        char *bi = bas, *bj = bas + n * sz, *bk, c;
        AInt i;
        #define Step sz
        #define Swap2(x,y)        for (i = 0; i < sz; i++) { c = x[i]; x[i] = y[i]; y[i] = c; }
        #define Swap3(x, y, z)    for (i = 0; i < sz; i++) { c = x[i]; x[i] = y[i]; y[i] = z[i]; z[i] = c; }
    #endif
    #if ((Mod & 1) != 0)
        if (bj < a0) return;
    #endif
    if (n == 1) { // N=2
        if (cmp(bas, bj, w) > 0) { Swap2(bas, bj) }
        return;
    }
    #if ((Mod & 16) == 0) // 高速化の必要がなければ、ここは省略してもよい.
        if (n == 2) { // N=3, 比較2回.
n2:         bk = bas + Step;
            if (cmp(bas, bk, w) <= 0) {
                if (cmp(bk, bj, w) <= 0) { return; } // i<k<j
                if (cmp(bj, bas, w) <= 0) { Swap3(bas, bj, bk) return; } // j<i<k
                Swap2(bk, bj) return; // i<j<k
            }
            if (cmp(bj, bk, w) <= 0) { Swap2(bi, bj) return; } // j<k<i
            if (cmp(bas, bj, w) <= 0) { Swap2(bas, bk) return; } // k<i<j
            Swap3(bas, bk, bj) return; //  k<j<i
        }
    #endif
    #if ((Mod & 32) == 0) // 高速化の必要がなければ、ここは省略してもよい.
        if (n <= 10) { // N<=11
            do {
                AInt i;
                bi = bas; bj = bas + Step; bk = bj;
                if (cmp(bi, bj, w) > 0) { bi = bj; bj = bas; }
                for (i = 2; i <= n; i++) {
                    bk += Step;
                    if (cmp(bi, bk, w) > 0) { bi = bk; }
                    if (cmp(bj, bk, w) < 0) { bj = bk; }
                }
                Swap2(bas, bi)
                if (bj == bas) { bj = bi; }
                Swap2(bk, bj)
                bas += Step;
                n -= 2;
            #if ((Mod & 16) == 0)
            } while (n > 2);
            if (n == 2) { bj = bas + Step * 2; goto n2; }
            #else
            } while (n > 1);
            #endif
            if (n == 1) {
                bj = bas + Step; if (cmp(bas, bj, w) > 0) { Swap2(bas, bj) }
            }
            return;
        }
    #endif
    #if ((Mod & 8) == 0)
        Typ p[1];
        bk = bas + (n >> 1);
        if (cmp(bi, bk, w) <= 0) { // bi, bj, bkの中から中央値を見つけてpに代入.
            if (cmp(bk, bj, w) <= 0) { *p = *bk; goto start; } // i<k<j
            if (cmp(bj, bi, w) <= 0) { *p = *bi; goto start; } // j<i<k
                                       *p = *bj; goto start;   // i<j<k
        } // else {
            if (cmp(bj, bk, w) <= 0) { *p = *bk; goto start; } // j<k<i
            if (cmp(bi, bj, w) <= 0) { *p = *bi; goto start; } // k<i<j
                                       *p = *bj; goto start;   // k<j<i
        //}
    #else
        char *p;
        bk = bas + (n >> 1) * sz;
        if (cmp(bi, bk, w) <= 0) { // bi, bj, bkの中から中央値を見つけてpに代入.
            if (cmp(bk, bj, w) <= 0) { p = bk; goto start; } // i<k<j
            if (cmp(bj, bi, w) <= 0) { p = bi; goto start; } // j<i<k
                                       p = bj; goto start;   // i<j<k
        } // else {
            if (cmp(bj, bk, w) <= 0) { p = bk; goto start; } // j<k<i
            if (cmp(bi, bj, w) <= 0) { p = bi; goto start; } // k<i<j
                                       p = bj; goto start;   // k<j<i
        //}
    #endif
    do {
        Swap2(bi, bj)
        #if ((Mod & 8) != 0)
            if (p == bi) { p = bj; } else if (p == bj) { p = bi; }
        #endif
        bi += Step; bj -= Step;
start:
        while (cmp(bi, p, w) < 0) bi += Step;
        while (cmp(p, bj, w) < 0) bj -= Step;
    } while (bi < bj);
    #if ((Mod & 15) == 0)
        aQSortFast(Mod, Typ, CmpFnc)(bas, bi - bas); // basからbiの手前まで.
        aQSortFast(Mod, Typ, CmpFnc)(bj + 1, n + (bas - bj)); // bj + 1からbas + (N-1) まで.
        // bas + n + 1 - (bj + 1) ==> n + (bas - bj)
    #elif ((Mod & 15) == 1)
        aQSortFast(Mod, Typ, CmpFnc)(bas, bi - bas, a0, a1);
        aQSortFast(Mod, Typ, CmpFnc)(bj + 1, n + (bas - bj), a0, a1);
    #elif ((Mod & 15) == 2)
        aQSortFast(Mod, Typ, CmpFnc)(bas, bi - bas, w);
        aQSortFast(Mod, Typ, CmpFnc)(bj + 1, n + (bas - bj), w);
    #elif ((Mod & 15) == 3)
        aQSortFast(Mod, Typ, CmpFnc)(bas, bi - bas, a0, a1, w);
        aQSortFast(Mod, Typ, CmpFnc)(bj + 1, n + (bas - bj), a0, a1, w);
    #elif ((Mod & 15) == 4)
        aQSort(Mod, Typ)(bas, bi - bas, cmp_);
        aQSort(Mod, Typ)(bj + 1, n + (bas - bj), cmp_);
    #elif ((Mod & 15) == 5)
        aQSort(Mod, Typ)(bas, bi - bas, a0, a1, cmp_);
        aQSort(Mod, Typ)(bj + 1, n + (bas - bj), a0, a1, cmp_);
    #elif ((Mod & 15) == 6)
        aQSort(Mod, Typ)(bas, bi - bas, cmp_, w);
        aQSort(Mod, Typ)(bj + 1, n + (bas - bj), cmp_, w);
    #elif ((Mod & 15) == 7)
        aQSort(Mod, Typ)(bas, bi - bas, a0, a1, cmp_, w);
        aQSort(Mod, Typ)(bj + 1, n + (bas - bj), a0, a1, cmp_, w);
    #elif ((Mod & 15) == 12)
        aQSort(Mod, Typ)(bas, (bi - bas) / sz, sz, cmp_);
        aQSort(Mod, Typ)(bj + sz, n - (bj - bas) / sz, sz, cmp_);
    #elif ((Mod & 15) == 13)
        aQSort(Mod, Typ)(bas, (bi - bas) / sz, sz, a0, a1, cmp_);
        aQSort(Mod, Typ)(bj + sz, n - (bj - bas) / sz, sz, a0, a1, cmp_);
    #elif ((Mod & 15) == 14)
        aQSort(Mod, Typ)(bas, (bi - bas) / sz, sz, cmp_, w);
        aQSort(Mod, Typ)(bj + sz, n - (bj - bas) / sz, sz, cmp_, w);
    #elif ((Mod & 15) == 15)
        aQSort(Mod, Typ)(bas, (bi - bas) / sz, sz, a0, a1, cmp_, w);
        aQSort(Mod, Typ)(bj + sz, n - (bj - bas) / sz, sz, a0, a1, cmp_, w);
    #endif
}

#undef cmp
#undef Step
#undef Swap2
#undef Swap3

#endlongdef

ひとつのコードで12通りの引数タイプ、さらにそれぞれ高速化とコード量のバランスを制御するための組み合わせが4通りあるので、コードが複雑になっています。

Mod=0  void aQSortFast(Mod, Typ, CmpFnc)(Typ *bas, AInt n)
Mod=1  void aQSortFast(Mod, Typ, CmpFnc)(Typ *bas, AInt n, Typ *a0, Typ *a1)
Mod=2  void aQSortFast(Mod, Typ, CmpFnc)(Typ *bas, AInt n, void *w)
Mod=3  void aQSortFast(Mod, Typ, CmpFnc)(Typ *bas, AInt n, Typ *a0, Typ *a1, void *w)
Mod=4  void aQSort(Mod, Typ)(Typ *bas, AInt n, int (*cmp)(const void *, const void *))
Mod=5  void aQSort(Mod, Typ)(Typ *bas, AInt n, Typ *a0, Typ *a1, int (*cmp)(const void *, const void *))
Mod=6  void aQSort(Mod, Typ)(Typ *bas, AInt n, int (*cmp)(const void *, const void *, void *), void *w)
Mod=7  void aQSort(Mod, Typ)(Typ *bas, AInt n, Typ *a0, Typ *a1, int (*cmp)(const void *, const void *, void *), void *w)
Mod=12 void aQSort(Mod, Typ)(void *bas, AInt n, AInt sz, int (*cmp)(const void *, const void *))
Mod=13 void aQSort(Mod, Typ)(void *bas, AInt n, AInt sz, void *a0, void *a1, int (*cmp)(const void *, const void *))
Mod=14 void aQSort(Mod, Typ)(void *bas, AInt n, AInt sz, int (*cmp)(const void *, const void *, void *), void *w)
Mod=15 void aQSort(Mod, Typ)(void *bas, AInt n, AInt sz, void *a0, void *a1, int (*cmp)(const void *, const void *, void *), void *w)

Mod=12の形式がqsort()互換です。

本当は #longdef @ALongdef_QSortFast(@Mod, @Typ, @CmpFnc) とすべきだし、Modも(@Mod)として式を書かれても平気なようにするべきなのですが、面倒なのでまだやっていません・・・。

↑

(2) サンプルコード#1

intの配列を100万用意して、ソートします。コンパイラの最適化能力が優秀なら、標準関数のqsortよりもかなり高速になります（比較関数がインライン展開されるためです）。

#include "acl1Tiny.c"
#include_once "once_aQSort.c"

uint32_t aXorShift32_i = 2463534242U;

AStatic uint32_t aXorShift32()
{
    uint32_t i = aXorShift32_i;
    i = i ^ (i << 13);
    i = i ^ (i >> 17);
    i = i ^ (i <<  5);
    aXorShift32_i = i;
    return i;
}

AInlineStatic int cmpInt(const void *a, const void *b) { return *(int *)a - *(int *)b; }

#longuse ALongdef_QSortFast(0, int, cmpInt)

int main()
{
    int i, n = 1000000, *a = malloc(n * sizeof (int));
    for (i = 0; i < n; i++)
        a[i] = aXorShift32() % 100000; // 10万.
    aQSortFast(0, int, cmpInt)(a, n); // とりあえず全部ソート.
    for (i = 0; i < 100; i++)
        printf("%d ", a[i]);
    return 0;
}

別バージョン。この書き方でも同じ結果になります。速度は格段に速くなります。
最初の100件だけをソートしてるわけではなく、ちゃんと100万件の中から、最初の100件を探してきています。残りは不揃いになっています。

最初のN件だけではなく、真ん中の一つだけ（メジアン）みたいな指定もできます。

（前略）
#longuse ALongdef_QSortFast(1, int, cmpInt)
（中略）
    aQSortFast(1, int, cmpInt)(a, n, &a[0], &a[100]); // a[0～99]だけを正確にソート.
（後略）

↑

(3) サンプルコード#2

もうちょっと複雑な例を用意してみます。

（前略）
AClass(Data) { int key[4]; };

AInlineStatic int cmpKey20(const void *a, const void *b)
{
    if ((*(Data **)a)->key[2] > (*(Data **)b)->key[2]) return +1;
    if ((*(Data **)a)->key[2] < (*(Data **)b)->key[2]) return -1;
    if ((*(Data **)a)->key[0] > (*(Data **)b)->key[0]) return +1;
    if ((*(Data **)a)->key[0] < (*(Data **)b)->key[0]) return -1;
    return 0;
}

#longuse ALongdef_QSortFast(0, Data *, cmpKey20)

int main()
{
    int i, j, n = 1000000;
    Data *a = malloc(n * sizeof (Data)), **p = malloc(n * sizeof (Data *));
    for (i = 0; i < n; i++) {
        for (j = 0; j < 4; j++)
            a[i].key[j] = aXorShift32() % 1000; // 1千.
        p[i] = &a[i];
    }
    aQSortFast(0, Data *, cmpKey20)(p, n); // とりあえず全部ソート.
    for (i = 0; i < 10; i++)
        printf("(%d,%d,%d,%d)\n", p[i]->key[0], p[i]->key[1], p[i]->key[2], p[i]->key[3]);
    return 0;
}

これは、4つのデータをもつ構造体をソートしています。ソート速度を上げるために、a[]をそのままソートするのではなく、ポインタの配列p[]をソートしています（非常に一般的な手法です）。
このプログラムでは、ソートにあたって、まず第一キーとしてkey[2]を使い、第二キーとしてkey[0]を使っています。第一キーが等しいとき、第二キーで大小を判定します。
これはこれでいいのですが、第一キーと第二キーって、変数で指定したいと思いませんか？変数で指定できないと、すべての組み合わせを可能にするには、4x3=12の関数を作らなければいけなくなってしまいます。

それをやるには、比較関数に追加の引数を渡す必要が出てきます。そのためにMod=2,3,6,7,14,15があります。

（前略）
AInlineStatic int cmpKeyExtPrm(const void *a, const void *b, void *w)
// 追加の引数は1つしかないので（w）、配列もしくは構造体のポインタを渡す.
{
    int *extParam = (int *) w, i = extParam[0], j = extParam[1]; 
    if ((*(Data **)a)->key[i] > (*(Data **)b)->key[i]) return +1;
    if ((*(Data **)a)->key[i] < (*(Data **)b)->key[i]) return -1;
    if ((*(Data **)a)->key[j] > (*(Data **)b)->key[j]) return +1;
    if ((*(Data **)a)->key[j] < (*(Data **)b)->key[j]) return -1;
    return 0;
}

#longuse ALongdef_QSortFast(2, Data *, cmpKeyExtPrm)

int main()
{
    int i, j, n = 1000000;
    Data *a = malloc(n * sizeof (Data)), **p = malloc(n * sizeof (Data *));
    for (i = 0; i < n; i++) {
        for (j = 0; j < 4; j++)
            a[i].key[j] = aXorShift32() % 1000; // 1千.
        p[i] = &a[i];
    }
    static int extParam[] = { 2, 0 }; // 今回の追加の引数.
    aQSortFast(2, Data *, cmpKeyExtPrm)(p, n, extParam); // とりあえず全部ソート.
    for (i = 0; i < 10; i++)
        printf("(%d,%d,%d,%d)\n", p[i]->key[0], p[i]->key[1], p[i]->key[2], p[i]->key[3]);
    return 0;
}