a24_aqsort の変更点

https://essen.osask.jp/?a24_aqsort

[ トップ ]   [ 編集 | 差分 | バックアップ | 添付 | リロード ]   [ 新規 | 一覧 | 単語検索 | 最終更新 | ヘルプ ]

• 追加された行はこの色です。
• 削除された行はこの色です。
• a24_aqsort は削除されています。
• a24_aqsort の差分を削除

---

* 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;
 }

       

Site admin: K

PukiWiki 1.4.7 Copyright © 2001-2006 PukiWiki Developers Team. License is GPL.
Based on "PukiWiki" 1.3 by yu-ji. Powered by PHP 5.6.40. HTML convert time: 0.009 sec.