a24_aQSort
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
]
開始行:
* once_aQSort
-(by [[K]], 2024.09.03)
** (1) ver.1.10 [2024.09.04] (244行)
#define aQSortFast(Mod, Typ, CmpFnc) ACat3(aQSortFast...
#define aQSort(Mod, Typ) ACat3(aQSort_, M...
// 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, ...
#elif ((@Mod & 15) == 1)
AStatic void aQSortFast(@Mod, @Typ, @CmpFnc)(@Typ *bas, ...
#elif ((@Mod & 15) == 2)
AStatic void aQSortFast(@Mod, @Typ, @CmpFnc)(@Typ *bas, ...
#elif ((@Mod & 15) == 3)
AStatic void aQSortFast(@Mod, @Typ, @CmpFnc)(@Typ *bas, ...
#elif ((@Mod & 15) == 4)
AStatic void aQSort(@Mod, @Typ)(@Typ *bas, AInt n, int (...
#elif ((@Mod & 15) == 5)
AStatic void aQSort(@Mod, @Typ)(@Typ *bas, AInt n, @Typ ...
#elif ((@Mod & 15) == 6)
AStatic void aQSort(@Mod, @Typ)(@Typ *bas, AInt n, int (...
#elif ((@Mod & 15) == 7)
AStatic void aQSort(@Mod, @Typ)(@Typ *bas, AInt n, @Typ ...
#elif ((@Mod & 15) == 12)
AStatic void aQSort(@Mod, @Typ)(void *bas_, AInt n, AInt...
#elif ((@Mod & 15) == 13)
AStatic void aQSort(@Mod, @Typ)(void *bas_, AInt n, AInt...
#elif ((@Mod & 15) == 14)
AStatic void aQSort(@Mod, @Typ)(void *bas_, AInt n, AInt...
#elif ((@Mod & 15) == 15)
AStatic void aQSort(@Mod, @Typ)(void *bas_, AInt n, AInt...
#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; @T...
#define @Step 1
#define @Swap2(x, y) c = *x; *x = *y; *y = c;
#define @Swap3(x, y, z) c = *x; *x = *y; *y = ...
#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...
#define @Swap3(x, y, z) for (i = 0; i < sz; i...
#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; } //...
if (@cmp(bj, bas, w) <= 0) { @Swap3(bas,...
@Swap2(bk, bj) return; // i<j<k
}
if (@cmp(bj, bk, w) <= 0) { @Swap2(bi, bj) r...
if (@cmp(bas, bj, w) <= 0) { @Swap2(bas, bk)...
@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 =...
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) >...
}
return;
}
#endif
#if ((@Mod & 8) == 0)
@Typ p[1];
bk = bas + (n >> 1);
if (@cmp(bi, bk, w) <= 0) { // bi, bj, bkの中か...
if (@cmp(bk, bj, w) <= 0) { *p = *bk; goto s...
if (@cmp(bj, bi, w) <= 0) { *p = *bi; goto s...
*p = *bj; goto s...
} // else {
if (@cmp(bj, bk, w) <= 0) { *p = *bk; goto s...
if (@cmp(bi, bj, w) <= 0) { *p = *bi; goto s...
*p = *bj; goto s...
//}
#else
char *p;
bk = bas + (n >> 1) * sz;
if (@cmp(bi, bk, w) <= 0) { // bi, bj, bkの中か...
if (@cmp(bk, bj, w) <= 0) { p = bk; goto sta...
if (@cmp(bj, bi, w) <= 0) { p = bi; goto sta...
p = bj; goto sta...
} // else {
if (@cmp(bj, bk, w) <= 0) { p = bk; goto sta...
if (@cmp(bi, bj, w) <= 0) { p = bi; goto sta...
p = bj; goto sta...
//}
#endif
do {
@Swap2(bi, bj)
#if ((@Mod & 8) != 0)
if (p == bi) { p = bj; } else if (p == bj) {...
#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); ...
aQSortFast(@Mod, @Typ, @CmpFnc)(bj + 1, n + (bas...
// bas + n + 1 - (bj + 1) ==> n + (bas - bj)
#elif ((@Mod & 15) == 1)
aQSortFast(@Mod, @Typ, @CmpFnc)(bas, bi - bas, a...
aQSortFast(@Mod, @Typ, @CmpFnc)(bj + 1, n + (bas...
#elif ((@Mod & 15) == 2)
aQSortFast(@Mod, @Typ, @CmpFnc)(bas, bi - bas, w);
aQSortFast(@Mod, @Typ, @CmpFnc)(bj + 1, n + (bas...
#elif ((@Mod & 15) == 3)
aQSortFast(@Mod, @Typ, @CmpFnc)(bas, bi - bas, a...
aQSortFast(@Mod, @Typ, @CmpFnc)(bj + 1, n + (bas...
#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, a...
#elif ((@Mod & 15) == 6)
aQSort(@Mod, @Typ)(bas, bi - bas, cmp_, w);
aQSort(@Mod, @Typ)(bj + 1, n + (bas - bj), cmp_,...
#elif ((@Mod & 15) == 7)
aQSort(@Mod, @Typ)(bas, bi - bas, a0, a1, cmp_, ...
aQSort(@Mod, @Typ)(bj + 1, n + (bas - bj), a0, a...
#elif ((@Mod & 15) == 12)
aQSort(@Mod, @Typ)(bas, (bi - bas) / sz, sz, cmp...
aQSort(@Mod, @Typ)(bj + sz, n - (bj - bas) / sz,...
#elif ((@Mod & 15) == 13)
aQSort(@Mod, @Typ)(bas, (bi - bas) / sz, sz, a0,...
aQSort(@Mod, @Typ)(bj + sz, n - (bj - bas) / sz,...
#elif ((@Mod & 15) == 14)
aQSort(@Mod, @Typ)(bas, (bi - bas) / sz, sz, cmp...
aQSort(@Mod, @Typ)(bj + sz, n - (bj - bas) / sz,...
#elif ((@Mod & 15) == 15)
aQSort(@Mod, @Typ)(bas, (bi - bas) / sz, sz, a0,...
aQSort(@Mod, @Typ)(bj + sz, n - (bj - bas) / sz,...
#endif
}
#undef @cmp
#undef @Step
#undef @Swap2
#undef @Swap3
#endlongdef
typedef int32_t aQSort_i32;
typedef int64_t aQSort_i64;
#longuse ALongdef_QSortFast(4, aQSort_i32, _)
#longuse ALongdef_QSortFast(5, aQSort_i32, _)
#longuse ALongdef_QSortFast(6, aQSort_i32, _)
#longuse ALongdef_QSortFast(7, aQSort_i32, _)
#longuse ALongdef_QSortFast(4, aQSort_i64, _)
#longuse ALongdef_QSortFast(5, aQSort_i64, _)
#longuse ALongdef_QSortFast(6, aQSort_i64, _)
#longuse ALongdef_QSortFast(7, aQSort_i64, _)
#longuse ALongdef_QSortFast(12, aQSort_sub, _)
#longuse ALongdef_QSortFast(13, aQSort_sub, _)
#longuse ALongdef_QSortFast(14, aQSort_sub, _)
#longuse ALongdef_QSortFast(15, aQSort_sub, _)
AStatic void aQSort12(void *bas, AInt n, AInt sz, int (*...
// これが<stdlib.h>のqsort()相当.
{
if (sz == sizeof (aQSort_i64)) { aQSort(4, aQSo...
else if (sz == sizeof (aQSort_i32)) { aQSort(4, aQSo...
else { aQSort(12, aQS...
}
AStatic void aQSort13(void *bas, AInt n, AInt sz, void *...
{
if (sz == sizeof (aQSort_i64)) { aQSort(5, aQSo...
else if (sz == sizeof (aQSort_i32)) { aQSort(5, aQSo...
else { aQSort(13, aQS...
}
AStatic void aQSort14(void *bas, AInt n, AInt sz, int (*...
{
if (sz == sizeof (aQSort_i64)) { aQSort(6, aQSo...
else if (sz == sizeof (aQSort_i32)) { aQSort(6, aQSo...
else { aQSort(14, aQS...
}
AStatic void aQSort15(void *bas, AInt n, AInt sz, void *...
{
if (sz == sizeof (aQSort_i64)) { aQSort(7, aQSo...
else if (sz == sizeof (aQSort_i32)) { aQSort(7, aQSo...
else { aQSort(15, aQS...
}
-ひとつのコードで12通りの引数タイプ、さらにそれぞれ高速化...
Mod=0 void aQSortFast(Mod, Typ, CmpFnc)(Typ *bas, AInt n)
Mod=1 void aQSortFast(Mod, Typ, CmpFnc)(Typ *bas, AInt ...
Mod=2 void aQSortFast(Mod, Typ, CmpFnc)(Typ *bas, AInt ...
Mod=3 void aQSortFast(Mod, Typ, CmpFnc)(Typ *bas, AInt ...
Mod=4 void aQSort(Mod, Typ)(Typ *bas, AInt n, int (*cmp...
Mod=5 void aQSort(Mod, Typ)(Typ *bas, AInt n, Typ *a0, ...
Mod=6 void aQSort(Mod, Typ)(Typ *bas, AInt n, int (*cmp...
Mod=7 void aQSort(Mod, Typ)(Typ *bas, AInt n, Typ *a0, ...
Mod=12 void aQSort(Mod, Typ)(void *bas, AInt n, AInt sz,...
Mod=13 void aQSort(Mod, Typ)(void *bas, AInt n, AInt sz,...
Mod=14 void aQSort(Mod, Typ)(void *bas, AInt n, AInt sz,...
Mod=15 void aQSort(Mod, Typ)(void *bas, AInt n, AInt sz,...
--Mod=12の形式がqsort()互換です。
//-本当は #longdef @ALongdef_QSortFast(@Mod, @Typ, @CmpFn...
** (2) サンプルコード#1
-intの配列を100万用意して、ソートします。コンパイラの最適...
#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) {...
#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件だけをソートしてるわけではなく...
-最初のN件だけではなく、真ん中の一つだけ（メジアン）みた...
（前略）
#longuse ALongdef_QSortFast(1, int, cmpInt)
（中略）
aQSortFast(1, int, cmpInt)(a, n, &a[0], &a[100]); //...
（後略）
** (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]) r...
if ((*(Data **)a)->key[2] < (*(Data **)b)->key[2]) r...
if ((*(Data **)a)->key[0] > (*(Data **)b)->key[0]) r...
if ((*(Data **)a)->key[0] < (*(Data **)b)->key[0]) r...
return 0;
}
#longuse ALongdef_QSortFast(0, Data *, cmpKey20)
int main()
{
int i, j, n = 1000000;
Data *a = malloc(n * sizeof (Data)), **p = malloc(n ...
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]->ke...
return 0;
}
-これは、4つのデータをもつ構造体をソートしています。ソー...
-このプログラムでは、ソートにあたって、まず第一キーとして...
-これはこれでいいのですが、第一キーと第二キーって、変数で...
~
-それをやるには、比較関数に追加の引数を渡す必要が出てきま...
（前略）
AInlineStatic int cmpKeyExtPrm(const void *a, const void...
// 追加の引数は1つしかないので（w）、配列もしくは構造体...
{
int *extParam = (int *) w, i = extParam[0], j = extP...
if ((*(Data **)a)->key[i] > (*(Data **)b)->key[i]) r...
if ((*(Data **)a)->key[i] < (*(Data **)b)->key[i]) r...
if ((*(Data **)a)->key[j] > (*(Data **)b)->key[j]) r...
if ((*(Data **)a)->key[j] < (*(Data **)b)->key[j]) r...
return 0;
}
#longuse ALongdef_QSortFast(2, Data *, cmpKeyExtPrm)
int main()
{
int i, j, n = 1000000;
Data *a = malloc(n * sizeof (Data)), **p = malloc(n ...
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]->ke...
return 0;
}
** (4) ベンチマーク
-(4-1) 前提：
// 乱数で初期配列を準備(a).
aXorShift32_seed(0); // seedをデフォルトに固定.
for (i = 0; i < n; i++)
a[i] = aXorShift32() % 1000;
// 逆順になるように初期配列を用意(b).
for (i = 0; i < n; i++)
a[i] = n - i;
-(4-2) (a)で初期化してソートする場合（n=100万）
|#0|qsort(a, n, sizeof (int), cmpInt);|0.112秒|（比較の基...
|#1|aQSortFast(0, int, cmpInt)(a, n);|0.057秒|#0の1.96倍速|
|#2|aQSortFast(1, int, cmpInt)(a, n, &a[n / 2 - 1], &a[n ...
|#3|aQSort12(a, n, sizeof (int), cmpInt);|0.112秒|qsort互...
-(4-3) (b)で初期化してソートする場合（n=100万）
|#4|qsort(a, n, sizeof (int), cmpInt);|0.124秒|qsortは逆...
|#5|aQSortFast(0, int, cmpInt)(a, n);|0.023秒|aQSortなら...
|#6|aQSort12(a, n, sizeof (int), cmpInt);|0.071秒|qsort互...
~
-(4-4) 次の前提：
typedef struct Data_ { int key[4]; } Data;
inline static int cmpKey20(const void *a, const void *b)...
{
if ((*(Data **)a)->key[2] > (*(Data **)b)->key[2]) r...
if ((*(Data **)a)->key[2] < (*(Data **)b)->key[2]) r...
if ((*(Data **)a)->key[0] > (*(Data **)b)->key[0]) r...
if ((*(Data **)a)->key[0] < (*(Data **)b)->key[0]) r...
return 0;
}
// 乱数で初期配列を準備(c)
aXorShift32_seed(0); // seedをデフォルトに固定.
for (i = 0; i < n; i++) {
for (j = 0; j < 4; j++)
d[i].key[j] = aXorShift32() % 1000;
a[i] = &d[i];
}
-(4-5) (c)で初期化してソートする場合（n=100万）
|#7|qsort(a, n, sizeof (Data *), cmpKey20);|0.586秒||
|#8|aQSortFast(0, n, cmpKey20)(a, n);|0.332秒|#7の1.76倍速|
-(4-6) 比較関数に追加のパラメータを渡したい（ソートの軸の...
inline static int cmpKeyIj(const void *a, const void *b,...
{
int i = ((int *) extParam)[0], j = ((int *) extParam...
if ((*(Data **)a)->key[i] > (*(Data **)b)->key[i]) r...
if ((*(Data **)a)->key[i] < (*(Data **)b)->key[i]) r...
if ((*(Data **)a)->key[j] > (*(Data **)b)->key[j]) r...
if ((*(Data **)a)->key[j] < (*(Data **)b)->key[j]) r...
return 0;
}
-(4-7) (c)で初期化してソートする場合（n=100万）
|#9|static int extParam[] = { 2, 0 }; aQSortFast(2, n, cm...
-(4-8) まとめ
|#0|qsort(a, n, sizeof (int), cmpInt);|0.112秒|（比較の基...
|#1|aQSortFast(0, int, cmpInt)(a, n);|0.057秒|#0の1.96倍速|
|#2|aQSortFast(1, int, cmpInt)(a, n, &a[n / 2 - 1], &a[n ...
|#3|aQSort12(a, n, sizeof (int), cmpInt);|0.112秒|qsort互...
|#4|qsort(a, n, sizeof (int), cmpInt);|0.124秒|qsortは逆...
|#5|aQSortFast(0, int, cmpInt)(a, n);|0.023秒|aQSortなら...
|#6|aQSort12(a, n, sizeof (int), cmpInt);|0.071秒|qsort互...
|#7|qsort(a, n, sizeof (Data *), cmpKey20);|0.586秒||
|#8|aQSortFast(0, n, cmpKey20)(a, n);|0.332秒|#7の1.76倍速|
|#9|static int extParam[] = { 2, 0 }; aQSortFast(2, n, cm...
終了行:
* once_aQSort
-(by [[K]], 2024.09.03)
** (1) ver.1.10 [2024.09.04] (244行)
#define aQSortFast(Mod, Typ, CmpFnc) ACat3(aQSortFast...
#define aQSort(Mod, Typ) ACat3(aQSort_, M...
// 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, ...
#elif ((@Mod & 15) == 1)
AStatic void aQSortFast(@Mod, @Typ, @CmpFnc)(@Typ *bas, ...
#elif ((@Mod & 15) == 2)
AStatic void aQSortFast(@Mod, @Typ, @CmpFnc)(@Typ *bas, ...
#elif ((@Mod & 15) == 3)
AStatic void aQSortFast(@Mod, @Typ, @CmpFnc)(@Typ *bas, ...
#elif ((@Mod & 15) == 4)
AStatic void aQSort(@Mod, @Typ)(@Typ *bas, AInt n, int (...
#elif ((@Mod & 15) == 5)
AStatic void aQSort(@Mod, @Typ)(@Typ *bas, AInt n, @Typ ...
#elif ((@Mod & 15) == 6)
AStatic void aQSort(@Mod, @Typ)(@Typ *bas, AInt n, int (...
#elif ((@Mod & 15) == 7)
AStatic void aQSort(@Mod, @Typ)(@Typ *bas, AInt n, @Typ ...
#elif ((@Mod & 15) == 12)
AStatic void aQSort(@Mod, @Typ)(void *bas_, AInt n, AInt...
#elif ((@Mod & 15) == 13)
AStatic void aQSort(@Mod, @Typ)(void *bas_, AInt n, AInt...
#elif ((@Mod & 15) == 14)
AStatic void aQSort(@Mod, @Typ)(void *bas_, AInt n, AInt...
#elif ((@Mod & 15) == 15)
AStatic void aQSort(@Mod, @Typ)(void *bas_, AInt n, AInt...
#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; @T...
#define @Step 1
#define @Swap2(x, y) c = *x; *x = *y; *y = c;
#define @Swap3(x, y, z) c = *x; *x = *y; *y = ...
#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...
#define @Swap3(x, y, z) for (i = 0; i < sz; i...
#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; } //...
if (@cmp(bj, bas, w) <= 0) { @Swap3(bas,...
@Swap2(bk, bj) return; // i<j<k
}
if (@cmp(bj, bk, w) <= 0) { @Swap2(bi, bj) r...
if (@cmp(bas, bj, w) <= 0) { @Swap2(bas, bk)...
@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 =...
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) >...
}
return;
}
#endif
#if ((@Mod & 8) == 0)
@Typ p[1];
bk = bas + (n >> 1);
if (@cmp(bi, bk, w) <= 0) { // bi, bj, bkの中か...
if (@cmp(bk, bj, w) <= 0) { *p = *bk; goto s...
if (@cmp(bj, bi, w) <= 0) { *p = *bi; goto s...
*p = *bj; goto s...
} // else {
if (@cmp(bj, bk, w) <= 0) { *p = *bk; goto s...
if (@cmp(bi, bj, w) <= 0) { *p = *bi; goto s...
*p = *bj; goto s...
//}
#else
char *p;
bk = bas + (n >> 1) * sz;
if (@cmp(bi, bk, w) <= 0) { // bi, bj, bkの中か...
if (@cmp(bk, bj, w) <= 0) { p = bk; goto sta...
if (@cmp(bj, bi, w) <= 0) { p = bi; goto sta...
p = bj; goto sta...
} // else {
if (@cmp(bj, bk, w) <= 0) { p = bk; goto sta...
if (@cmp(bi, bj, w) <= 0) { p = bi; goto sta...
p = bj; goto sta...
//}
#endif
do {
@Swap2(bi, bj)
#if ((@Mod & 8) != 0)
if (p == bi) { p = bj; } else if (p == bj) {...
#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); ...
aQSortFast(@Mod, @Typ, @CmpFnc)(bj + 1, n + (bas...
// bas + n + 1 - (bj + 1) ==> n + (bas - bj)
#elif ((@Mod & 15) == 1)
aQSortFast(@Mod, @Typ, @CmpFnc)(bas, bi - bas, a...
aQSortFast(@Mod, @Typ, @CmpFnc)(bj + 1, n + (bas...
#elif ((@Mod & 15) == 2)
aQSortFast(@Mod, @Typ, @CmpFnc)(bas, bi - bas, w);
aQSortFast(@Mod, @Typ, @CmpFnc)(bj + 1, n + (bas...
#elif ((@Mod & 15) == 3)
aQSortFast(@Mod, @Typ, @CmpFnc)(bas, bi - bas, a...
aQSortFast(@Mod, @Typ, @CmpFnc)(bj + 1, n + (bas...
#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, a...
#elif ((@Mod & 15) == 6)
aQSort(@Mod, @Typ)(bas, bi - bas, cmp_, w);
aQSort(@Mod, @Typ)(bj + 1, n + (bas - bj), cmp_,...
#elif ((@Mod & 15) == 7)
aQSort(@Mod, @Typ)(bas, bi - bas, a0, a1, cmp_, ...
aQSort(@Mod, @Typ)(bj + 1, n + (bas - bj), a0, a...
#elif ((@Mod & 15) == 12)
aQSort(@Mod, @Typ)(bas, (bi - bas) / sz, sz, cmp...
aQSort(@Mod, @Typ)(bj + sz, n - (bj - bas) / sz,...
#elif ((@Mod & 15) == 13)
aQSort(@Mod, @Typ)(bas, (bi - bas) / sz, sz, a0,...
aQSort(@Mod, @Typ)(bj + sz, n - (bj - bas) / sz,...
#elif ((@Mod & 15) == 14)
aQSort(@Mod, @Typ)(bas, (bi - bas) / sz, sz, cmp...
aQSort(@Mod, @Typ)(bj + sz, n - (bj - bas) / sz,...
#elif ((@Mod & 15) == 15)
aQSort(@Mod, @Typ)(bas, (bi - bas) / sz, sz, a0,...
aQSort(@Mod, @Typ)(bj + sz, n - (bj - bas) / sz,...
#endif
}
#undef @cmp
#undef @Step
#undef @Swap2
#undef @Swap3
#endlongdef
typedef int32_t aQSort_i32;
typedef int64_t aQSort_i64;
#longuse ALongdef_QSortFast(4, aQSort_i32, _)
#longuse ALongdef_QSortFast(5, aQSort_i32, _)
#longuse ALongdef_QSortFast(6, aQSort_i32, _)
#longuse ALongdef_QSortFast(7, aQSort_i32, _)
#longuse ALongdef_QSortFast(4, aQSort_i64, _)
#longuse ALongdef_QSortFast(5, aQSort_i64, _)
#longuse ALongdef_QSortFast(6, aQSort_i64, _)
#longuse ALongdef_QSortFast(7, aQSort_i64, _)
#longuse ALongdef_QSortFast(12, aQSort_sub, _)
#longuse ALongdef_QSortFast(13, aQSort_sub, _)
#longuse ALongdef_QSortFast(14, aQSort_sub, _)
#longuse ALongdef_QSortFast(15, aQSort_sub, _)
AStatic void aQSort12(void *bas, AInt n, AInt sz, int (*...
// これが<stdlib.h>のqsort()相当.
{
if (sz == sizeof (aQSort_i64)) { aQSort(4, aQSo...
else if (sz == sizeof (aQSort_i32)) { aQSort(4, aQSo...
else { aQSort(12, aQS...
}
AStatic void aQSort13(void *bas, AInt n, AInt sz, void *...
{
if (sz == sizeof (aQSort_i64)) { aQSort(5, aQSo...
else if (sz == sizeof (aQSort_i32)) { aQSort(5, aQSo...
else { aQSort(13, aQS...
}
AStatic void aQSort14(void *bas, AInt n, AInt sz, int (*...
{
if (sz == sizeof (aQSort_i64)) { aQSort(6, aQSo...
else if (sz == sizeof (aQSort_i32)) { aQSort(6, aQSo...
else { aQSort(14, aQS...
}
AStatic void aQSort15(void *bas, AInt n, AInt sz, void *...
{
if (sz == sizeof (aQSort_i64)) { aQSort(7, aQSo...
else if (sz == sizeof (aQSort_i32)) { aQSort(7, aQSo...
else { aQSort(15, aQS...
}
-ひとつのコードで12通りの引数タイプ、さらにそれぞれ高速化...
Mod=0 void aQSortFast(Mod, Typ, CmpFnc)(Typ *bas, AInt n)
Mod=1 void aQSortFast(Mod, Typ, CmpFnc)(Typ *bas, AInt ...
Mod=2 void aQSortFast(Mod, Typ, CmpFnc)(Typ *bas, AInt ...
Mod=3 void aQSortFast(Mod, Typ, CmpFnc)(Typ *bas, AInt ...
Mod=4 void aQSort(Mod, Typ)(Typ *bas, AInt n, int (*cmp...
Mod=5 void aQSort(Mod, Typ)(Typ *bas, AInt n, Typ *a0, ...
Mod=6 void aQSort(Mod, Typ)(Typ *bas, AInt n, int (*cmp...
Mod=7 void aQSort(Mod, Typ)(Typ *bas, AInt n, Typ *a0, ...
Mod=12 void aQSort(Mod, Typ)(void *bas, AInt n, AInt sz,...
Mod=13 void aQSort(Mod, Typ)(void *bas, AInt n, AInt sz,...
Mod=14 void aQSort(Mod, Typ)(void *bas, AInt n, AInt sz,...
Mod=15 void aQSort(Mod, Typ)(void *bas, AInt n, AInt sz,...
--Mod=12の形式がqsort()互換です。
//-本当は #longdef @ALongdef_QSortFast(@Mod, @Typ, @CmpFn...
** (2) サンプルコード#1
-intの配列を100万用意して、ソートします。コンパイラの最適...
#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) {...
#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件だけをソートしてるわけではなく...
-最初のN件だけではなく、真ん中の一つだけ（メジアン）みた...
（前略）
#longuse ALongdef_QSortFast(1, int, cmpInt)
（中略）
aQSortFast(1, int, cmpInt)(a, n, &a[0], &a[100]); //...
（後略）
** (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]) r...
if ((*(Data **)a)->key[2] < (*(Data **)b)->key[2]) r...
if ((*(Data **)a)->key[0] > (*(Data **)b)->key[0]) r...
if ((*(Data **)a)->key[0] < (*(Data **)b)->key[0]) r...
return 0;
}
#longuse ALongdef_QSortFast(0, Data *, cmpKey20)
int main()
{
int i, j, n = 1000000;
Data *a = malloc(n * sizeof (Data)), **p = malloc(n ...
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]->ke...
return 0;
}
-これは、4つのデータをもつ構造体をソートしています。ソー...
-このプログラムでは、ソートにあたって、まず第一キーとして...
-これはこれでいいのですが、第一キーと第二キーって、変数で...
~
-それをやるには、比較関数に追加の引数を渡す必要が出てきま...
（前略）
AInlineStatic int cmpKeyExtPrm(const void *a, const void...
// 追加の引数は1つしかないので（w）、配列もしくは構造体...
{
int *extParam = (int *) w, i = extParam[0], j = extP...
if ((*(Data **)a)->key[i] > (*(Data **)b)->key[i]) r...
if ((*(Data **)a)->key[i] < (*(Data **)b)->key[i]) r...
if ((*(Data **)a)->key[j] > (*(Data **)b)->key[j]) r...
if ((*(Data **)a)->key[j] < (*(Data **)b)->key[j]) r...
return 0;
}
#longuse ALongdef_QSortFast(2, Data *, cmpKeyExtPrm)
int main()
{
int i, j, n = 1000000;
Data *a = malloc(n * sizeof (Data)), **p = malloc(n ...
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]->ke...
return 0;
}
** (4) ベンチマーク
-(4-1) 前提：
// 乱数で初期配列を準備(a).
aXorShift32_seed(0); // seedをデフォルトに固定.
for (i = 0; i < n; i++)
a[i] = aXorShift32() % 1000;
// 逆順になるように初期配列を用意(b).
for (i = 0; i < n; i++)
a[i] = n - i;
-(4-2) (a)で初期化してソートする場合（n=100万）
|#0|qsort(a, n, sizeof (int), cmpInt);|0.112秒|（比較の基...
|#1|aQSortFast(0, int, cmpInt)(a, n);|0.057秒|#0の1.96倍速|
|#2|aQSortFast(1, int, cmpInt)(a, n, &a[n / 2 - 1], &a[n ...
|#3|aQSort12(a, n, sizeof (int), cmpInt);|0.112秒|qsort互...
-(4-3) (b)で初期化してソートする場合（n=100万）
|#4|qsort(a, n, sizeof (int), cmpInt);|0.124秒|qsortは逆...
|#5|aQSortFast(0, int, cmpInt)(a, n);|0.023秒|aQSortなら...
|#6|aQSort12(a, n, sizeof (int), cmpInt);|0.071秒|qsort互...
~
-(4-4) 次の前提：
typedef struct Data_ { int key[4]; } Data;
inline static int cmpKey20(const void *a, const void *b)...
{
if ((*(Data **)a)->key[2] > (*(Data **)b)->key[2]) r...
if ((*(Data **)a)->key[2] < (*(Data **)b)->key[2]) r...
if ((*(Data **)a)->key[0] > (*(Data **)b)->key[0]) r...
if ((*(Data **)a)->key[0] < (*(Data **)b)->key[0]) r...
return 0;
}
// 乱数で初期配列を準備(c)
aXorShift32_seed(0); // seedをデフォルトに固定.
for (i = 0; i < n; i++) {
for (j = 0; j < 4; j++)
d[i].key[j] = aXorShift32() % 1000;
a[i] = &d[i];
}
-(4-5) (c)で初期化してソートする場合（n=100万）
|#7|qsort(a, n, sizeof (Data *), cmpKey20);|0.586秒||
|#8|aQSortFast(0, n, cmpKey20)(a, n);|0.332秒|#7の1.76倍速|
-(4-6) 比較関数に追加のパラメータを渡したい（ソートの軸の...
inline static int cmpKeyIj(const void *a, const void *b,...
{
int i = ((int *) extParam)[0], j = ((int *) extParam...
if ((*(Data **)a)->key[i] > (*(Data **)b)->key[i]) r...
if ((*(Data **)a)->key[i] < (*(Data **)b)->key[i]) r...
if ((*(Data **)a)->key[j] > (*(Data **)b)->key[j]) r...
if ((*(Data **)a)->key[j] < (*(Data **)b)->key[j]) r...
return 0;
}
-(4-7) (c)で初期化してソートする場合（n=100万）
|#9|static int extParam[] = { 2, 0 }; aQSortFast(2, n, cm...
-(4-8) まとめ
|#0|qsort(a, n, sizeof (int), cmpInt);|0.112秒|（比較の基...
|#1|aQSortFast(0, int, cmpInt)(a, n);|0.057秒|#0の1.96倍速|
|#2|aQSortFast(1, int, cmpInt)(a, n, &a[n / 2 - 1], &a[n ...
|#3|aQSort12(a, n, sizeof (int), cmpInt);|0.112秒|qsort互...
|#4|qsort(a, n, sizeof (int), cmpInt);|0.124秒|qsortは逆...
|#5|aQSortFast(0, int, cmpInt)(a, n);|0.023秒|aQSortなら...
|#6|aQSort12(a, n, sizeof (int), cmpInt);|0.071秒|qsort互...
|#7|qsort(a, n, sizeof (Data *), cmpKey20);|0.586秒||
|#8|aQSortFast(0, n, cmpKey20)(a, n);|0.332秒|#7の1.76倍速|
|#9|static int extParam[] = { 2, 0 }; aQSortFast(2, n, cm...
ページ名:
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
