ソート・アルゴリズム入門から精通までの7--集計ソート
前の記事では、高速ソートについて説明しましたが、通常、高速ソートは最も速いアルゴリズムとされています.アルゴリズム性能の面から言えば,集計ソートは迅速なソートの有力な競争者である.高速ソートの欠点は、パフォーマンスが不安定で、特定のデータ分布がソートパフォーマンスを低下させることです.集計ソートは、データの分布に関係なく安定したソートです.集計ソートの欠点は、必要なメモリ容量が大きいことです.前のバブルソート、ソートを選択し、ソートを挿入し、ヒルソートは追加のメモリスペースを必要としないと近似することができます.通常、高速ソートに必要な余分なメモリ領域はO(log(n))である.集計ソートに必要な余分なメモリ領域はO(n)である.集計ソートのもう一つの利点は、外部ソートが可能であることである.外部ソートとは、ソート中に外部デバイスからデータを取り出し、並べた結果を外部デバイスに置くことを意味します.したがって,外部ソートはデータ規模が大きい場合に適用できる.最も簡単な集計ソートは2つの集計ソートであり,同様に3つの集計ソート,4つの集計ソートなどがある.集計ソートの通常の実装には、ソースデータと同じ大きさの追加のメモリ領域が必要です.次の実装では、必要な追加のメモリ領域を元の配列空間の半分に低減するために、少し改良されています.
2パス並び替えのアルゴリズムの説明1.集計プロセス1.1.2つの秩序化されたシーケンスaとbがある場合、シーケンスaとシーケンスbを結合し、新しい配列cに格納し、cの要素を秩序化します.簡単にするために、ここでは、昇順配列、すなわち、シーケンスaおよびシーケンスbが非減算シーケンスであることのみを考慮する.c中の要素も非減算で配列される.1.2. 2つのポインタpaおよびpbは、それぞれaおよびbの最初の要素を指す.ポインタpcは新しい配列cを指す.1.3. aとbが処理されていない場合、aヘッダの要素(paが指す要素)xとbヘッダの要素(pbが指す要素)yをチェックし、x<=yであれば、xを新しい配列に入れ、paを右に移動します.そうでなければ、yを新しい配列に入れ、pbを右に移動します.xまたはyを新しい配列に入れた後、cはpcを1つの位置に移動します.1.4. aまたはbの処理が完了するまで、ステップ1.3を繰り返します.1.5. aに未処理の要素がある場合は、aの残りの要素をcに追加します.1.6. bに未処理の要素がある場合は、bの残りの要素をcに追加します.次のコードではmerge_v 1とmerge_v 2とmerge_v2_asmは同じ機能を実現し、arr 1,arr 2を結合し(len 1およびlen 2はarr 1およびarr 2の長さ)、配列targetに格納する. 2. 関数merge_sort関数merge_sortは集計ソートを実現し,集計ソートには一時的なbuffが必要であり,tlen=(len+1)/2をとり,lenは元のシーケンス長であり,tlenバッファtbuffの長さを割り当てる.そしてmerge_を呼び出すsort_coreを並べ替えます.
3.関数merge_sort_coreの流れ
3.1. まず配列長をチェックし、配列長が値INSERT_より小さい場合SORT_THRESHOLDは、直接挿入してソートして戻ります.3.2. シーケンスarrをほぼ等しい2つの部分に分け、lenが偶数であれば左半分の長さと右半分の長さは同じであり、そうでなければ左半分の長さは右半分の長さより1つの要素が多い.3.3. まず自分を再帰的に呼び出し,左半分を並べ替え,右半分を並べ替える.3.4. 左半分を一時バッファtbuffにコピーし、tbuffを配列a、右半分を配列b、元の配列arrをターゲット配列cとする.呼び出しプログラムmerge_v 1集計操作を行う.
以下はすべてのソースコードです.
集計ソートの核心部分は集計操作であり、そのホットスポットは次の文の分岐文である.分岐文の実行はCPUの分岐予測機能にかかわることが知られている.ブランチ予測の精度が低いと、プログラムの実行速度が低下します.次のシナリオでは、データ分布がランダムであれば、2つのブランチの実行確率はそれぞれ50%を占めるので、ブランチ除去技術を用いてCPUの実行性能を向上させることを考慮することができる.
if ( *p1 <= *p2 ) *target++ = *p1++; else *target++ = *p2++; 関数merge_v 2はブランチを除去するバージョンで、そのコア部分は以下の通りです. a = *p1; b = *p2;
//if ( a>b) then m1=1, m2=0 else m1=0, m2=1 m1 = (a < b); m2 = (m1 ^ 1); p1 += m1; p2 += m2;
*target++ = (m1 ? a : b);
関数merge_v2_asmは関数merge_v 2のアセンブリ言語が実装され、このアセンブリバージョンではCコンパイラに比べて4つの命令が減少した.I 7-4700 HQでのテスト結果、merge_v2_asmは最も速いバージョンです.2百万個の整数をソートします.merge_v 1は159ミリ秒、merge_v 2は181ミリ秒、merge_v2_asmは142ミリ秒かかります.もちろん、これは説明ではありません.merge_v 2はmergeより遅いに違いないv 1、一部のCPUでは、merge_v 2反超merge_v 1は可能です.読者が興味があれば、自分のパソコンでこの3つのバージョンの性能をテストしてみてください.また、私のテスト結果は、場合によっては、集計ソートのパフォーマンスが高速ソートを上回ることを示しています.具体的なテストデータは後述する.
2パス並び替えのアルゴリズムの説明1.集計プロセス1.1.2つの秩序化されたシーケンスaとbがある場合、シーケンスaとシーケンスbを結合し、新しい配列cに格納し、cの要素を秩序化します.簡単にするために、ここでは、昇順配列、すなわち、シーケンスaおよびシーケンスbが非減算シーケンスであることのみを考慮する.c中の要素も非減算で配列される.1.2. 2つのポインタpaおよびpbは、それぞれaおよびbの最初の要素を指す.ポインタpcは新しい配列cを指す.1.3. aとbが処理されていない場合、aヘッダの要素(paが指す要素)xとbヘッダの要素(pbが指す要素)yをチェックし、x<=yであれば、xを新しい配列に入れ、paを右に移動します.そうでなければ、yを新しい配列に入れ、pbを右に移動します.xまたはyを新しい配列に入れた後、cはpcを1つの位置に移動します.1.4. aまたはbの処理が完了するまで、ステップ1.3を繰り返します.1.5. aに未処理の要素がある場合は、aの残りの要素をcに追加します.1.6. bに未処理の要素がある場合は、bの残りの要素をcに追加します.次のコードではmerge_v 1とmerge_v 2とmerge_v2_asmは同じ機能を実現し、arr 1,arr 2を結合し(len 1およびlen 2はarr 1およびarr 2の長さ)、配列targetに格納する. 2. 関数merge_sort関数merge_sortは集計ソートを実現し,集計ソートには一時的なbuffが必要であり,tlen=(len+1)/2をとり,lenは元のシーケンス長であり,tlenバッファtbuffの長さを割り当てる.そしてmerge_を呼び出すsort_coreを並べ替えます.
3.関数merge_sort_coreの流れ
3.1. まず配列長をチェックし、配列長が値INSERT_より小さい場合SORT_THRESHOLDは、直接挿入してソートして戻ります.3.2. シーケンスarrをほぼ等しい2つの部分に分け、lenが偶数であれば左半分の長さと右半分の長さは同じであり、そうでなければ左半分の長さは右半分の長さより1つの要素が多い.3.3. まず自分を再帰的に呼び出し,左半分を並べ替え,右半分を並べ替える.3.4. 左半分を一時バッファtbuffにコピーし、tbuffを配列a、右半分を配列b、元の配列arrをターゲット配列cとする.呼び出しプログラムmerge_v 1集計操作を行う.
以下はすべてのソースコードです.
#include
#include
#include "sorts.h"
void merge_v1(ELE_TYPE arr1[], int len1, ELE_TYPE arr2[], int len2, ELE_TYPE *target)
{
ELE_PTR p1,p2;
ELE_PTR p1End,p2End;
p1=arr1; p1End=arr1+len1;
p2=arr2; p2End=arr2+len2;
while ( p1b) then m1=1, m2=0 else m1=0, m2=1
m1 = (a < b);
m2 = (m1 ^ 1);
p1 += m1;
p2 += m2;
*target++ = (m1 ? a : b);
}
while (p1< p1End)
*target++ = *p1++;
while (p2< p2End)
*target++ = *p2++;
}
_declspec(naked)
void merge_v2_asm(ELE_TYPE arr1[], int len1, ELE_TYPE arr2[], int len2, ELE_TYPE *target)
{
#define _arr1 4
#define _len1 8
#define _arr2 12
#define _len2 16
#define _target 20
#define _OFS_P1END 0
#define _OFS_P2END 4
#define _ST_SIZE 24
#define REG_p1 esi
#define REG_p2 edi
#define REG_TGT ebp
#define REG_a eax
#define REG_b ebx
#define REG_M1 ecx
#define REG_M1L cl
#define REG_M2 edx
__asm
{
push esi ; save registers
push edi
push ebx
push ebp
sub esp,(_ST_SIZE-16)
mov REG_p1, dword ptr [esp+_ST_SIZE+_arr1]
mov eax, dword ptr [esp+_ST_SIZE+_len1]
lea edx, [REG_p1+eax*4]
mov dword ptr [esp+_OFS_P1END], edx
mov REG_p2, dword ptr [esp+_ST_SIZE+_arr2]
mov eax, dword ptr [esp+_ST_SIZE+_len2]
lea edx, [REG_p2+eax*4]
mov dword ptr [esp+_OFS_P2END], edx
mov REG_TGT, dword ptr [esp+_ST_SIZE+_target]
jmp merge_v2_cmp
merge_v2_loop_start:
xor REG_M1, REG_M1 ; REG_M1 = 0
mov REG_a, dword ptr [REG_p1]
mov REG_b, dword ptr [REG_p2]
cmp REG_a, REG_b
setl REG_M1L ; if a= b, then a = b
mov REG_M2, REG_M1
lea REG_p1, DWORD PTR[REG_p1 + REG_M1 * 4] ; if a=b, then REG_M2=1, else REG_M2=0
mov DWORD PTR[REG_TGT], REG_a ; *target = a
lea REG_p2, DWORD PTR[REG_p2 + REG_M2 * 4] ; if a>=b, REG_p2++
add REG_TGT, 4 ; target++
merge_v2_cmp:
cmp REG_p1, DWORD PTR [esp+_OFS_P1END]
jae SHORT merge_v2_p1_tail_cmp
cmp REG_p2, DWORD PTR [esp+_OFS_P2END]
jb merge_v2_loop_start
jmp merge_v2_p1_tail_cmp
merge_v2_p1_tail_loop:
mov eax, DWORD PTR [REG_p1]
mov [REG_TGT], eax
add REG_p1, 4
add REG_TGT, 4
merge_v2_p1_tail_cmp:
cmp REG_p1, DWORD PTR [esp+_OFS_P1END]
jb merge_v2_p1_tail_loop
jmp merge_v2_p2_tail_cmp
merge_v2_p2_tail_loop:
mov eax, DWORD PTR [REG_p2]
mov [REG_TGT], eax
add REG_p2, 4
add REG_TGT, 4
merge_v2_p2_tail_cmp:
cmp REG_p2, DWORD PTR [esp+_OFS_P2END]
jb merge_v2_p2_tail_loop
merge_v2_exit:
add esp, (_ST_SIZE-16)
pop ebp ; restore registers
pop ebx
pop edi
pop esi
ret
}
}
void merge_sort_core(ELE_TYPE arr[], int len, ELE_TYPE *tBuff)
{
int left_half;
int right_half;
#if 0
if ( len<=1)
return ;
#else
if (len <= INSERT_SORT_THRESHOLD)
{
insert_sort(arr, len);
return ;
}
#endif
left_half = (len+1)/2;
right_half = len - left_half;
merge_sort_core(arr,left_half, tBuff);
merge_sort_core(arr+left_half, right_half, tBuff);
memcpy(tBuff,arr,sizeof(ELE_TYPE)*left_half);
merge_v1(tBuff, left_half, arr+left_half, right_half, arr);
//merge_v2(tBuff, left_half, arr + left_half, right_half, arr);
//merge_v2_asm(tBuff, left_half, arr+left_half, right_half, arr);
}
void merge_sort(ELE_TYPE arr[], int len)
{
ELE_TYPE *tBuff= (ELE_TYPE*)malloc( sizeof(ELE_TYPE)*(len+1)/2);;
merge_sort_core(arr,len, tBuff);
free(tBuff);
}
void test_merge_sort()
{
ELE_TYPE arr[] = { 61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 };
int len = (int) sizeof(arr) / sizeof(arr[0]);
printf("original data are:");
print_array(arr, len);
merge_sort(arr, len);
printf("The data after sorted are:");
print_array(arr, len);
}
集計ソートの核心部分は集計操作であり、そのホットスポットは次の文の分岐文である.分岐文の実行はCPUの分岐予測機能にかかわることが知られている.ブランチ予測の精度が低いと、プログラムの実行速度が低下します.次のシナリオでは、データ分布がランダムであれば、2つのブランチの実行確率はそれぞれ50%を占めるので、ブランチ除去技術を用いてCPUの実行性能を向上させることを考慮することができる.
if ( *p1 <= *p2 ) *target++ = *p1++; else *target++ = *p2++; 関数merge_v 2はブランチを除去するバージョンで、そのコア部分は以下の通りです. a = *p1; b = *p2;
//if ( a>b) then m1=1, m2=0 else m1=0, m2=1 m1 = (a < b); m2 = (m1 ^ 1); p1 += m1; p2 += m2;
*target++ = (m1 ? a : b);
関数merge_v2_asmは関数merge_v 2のアセンブリ言語が実装され、このアセンブリバージョンではCコンパイラに比べて4つの命令が減少した.I 7-4700 HQでのテスト結果、merge_v2_asmは最も速いバージョンです.2百万個の整数をソートします.merge_v 1は159ミリ秒、merge_v 2は181ミリ秒、merge_v2_asmは142ミリ秒かかります.もちろん、これは説明ではありません.merge_v 2はmergeより遅いに違いないv 1、一部のCPUでは、merge_v 2反超merge_v 1は可能です.読者が興味があれば、自分のパソコンでこの3つのバージョンの性能をテストしてみてください.また、私のテスト結果は、場合によっては、集計ソートのパフォーマンスが高速ソートを上回ることを示しています.具体的なテストデータは後述する.