挿入ソートと選択ソートのベンチマーク
Stack Overflowで、挿入ソートが平均して実行するデータ移動の量が多いため、（リンクリストデータではなく）配列データの選択ソートよりも挿入ソートが劣っていると主張する回答を読みました。この主張は私にとって新しいものであり、比較ソートのピアの中で挿入ソートが一般的に優れているという長年にわたって私が読んで受け入れてきた多くの主張に反しています。さらに、私自身のアルゴリズム分析は、両方のアルゴリズムの効率的な実装と、メモリの書き込みが読み取りよりもそれほど高価ではない環境を想定して、ランダムデータの平均で挿入ソートがわずかに優れていることをサポートしています。
しかし、2つのアルゴリズムの漸近コストが同じであるため、すべての議論はテストなしでは非常に多くの煙になります。そのため、実際のデータを再生するために、選択ソート、挿入ソート、およびテストハーネスを作成しました。私は結果に驚きました。私の挿入ソートはした道ソート（第1の走行時間程度）ランダムな入力に速く私の選択よりも、挿入も、逆ソート入力のその最悪のケースのための明確な勝者でした。挿入が平均的なケースでそれほど良くなるとは思っていませんでしたし、逆にソートされた入力の場合にはまったく勝つとは思っていませんでした。
そして、それは私をここに連れて来ます。レビューと解説のために、2つのソート機能とテストハーネスを紹介します。私は、テストが公正なものであることを保証するために、選択ソートのパフォーマンスがどのように改善されるかについての洞察に特に興味があります。また、結果にバイアスをかける可能性のあるテストハーネスの欠陥についての解説にも興味があります。
selection.c
void selection(int data[], unsigned int count) {
for (unsigned int i = 0; i < count - 1; i++) {
int min_value = data[i];
unsigned int min_index = i;
for (unsigned int j = i + 1; j < count; j++) {
if (data[j] < min_value) {
min_index = j;
min_value = data[j];
}
}
data[min_index] = data[i];
data[i] = min_value;
}
}
selection.h
void selection(int data[], unsigned int count);
挿入.c
void insertion(int data[], unsigned int count) {
for (unsigned int i = 1; i < count; i++) {
int test_value = data[i];
unsigned int j;
for (j = i; j > 0; j--) {
if (data[j - 1] > test_value) {
data[j] = data[j - 1];
} else {
break;
}
}
if (j != i) {
data[j] = test_value;
}
}
}
挿入.h
void insertion(int data[], unsigned int count);
main.c
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
#include "insertion.h"
#include "selection.h"
#define NUM_ITEMS 16384
#define RANDOM_SEED 17231
#define ITERATIONS 32
#define CLOCKS_PER_MS (CLOCKS_PER_SEC / 1000)
int original_items[NUM_ITEMS];
int selection_items[NUM_ITEMS];
int insertion_items[NUM_ITEMS];
int main(void) {
clock_t start_time;
clock_t total_time;
int num_distinct;
srand(RANDOM_SEED);
for (int i = 0; i < NUM_ITEMS; i++) {
original_items[i] = rand() % NUM_ITEMS;
}
// test selection
total_time = 0;
for (int i = 0; i < ITERATIONS; i++) {
memcpy(selection_items, original_items, sizeof(original_items));
start_time = clock();
selection(selection_items, NUM_ITEMS);
total_time += clock() - start_time;
}
// Validation / sanity check
num_distinct = 1;
for (int i = 1; i < NUM_ITEMS; i++) {
if (selection_items[i] < selection_items[i - 1]) {
printf("Selection result validation failed.\n");
}
if (selection_items[i] != selection_items[i - 1]) {
num_distinct++;
}
}
printf("%d distinct values sorted\n", num_distinct);
printf("Selection sort on %d items: %ld ms\n", NUM_ITEMS, (long) (total_time / ITERATIONS / CLOCKS_PER_MS));
// test insertion
total_time = 0;
for (int i = 0; i < ITERATIONS; i++) {
memcpy(insertion_items, original_items, sizeof(original_items));
start_time = clock();
insertion(insertion_items, NUM_ITEMS);
total_time += clock() - start_time;
}
// Validation
for (int i = 0; i < NUM_ITEMS; i++) {
if (insertion_items[i] != selection_items[i]) {
printf("Insertion result differs from selection result.\n");
}
}
printf("Insertion sort on %d items: %ld ms\n", NUM_ITEMS, (long) (total_time / ITERATIONS / CLOCKS_PER_MS));
}
Makefile
PROG = sort_test
OBJS = main.o selection.o insertion.o
CFLAGS = -O3 -Wall -Wextra -pedantic -std=c11
$(PROG) : $(OBJS)
$(CC) -o $@ $(CFLAGS) $(LDFLAGS) $^ main.o selection.o: selection.h main.o insertion.o: insertion.h clean: rm $(PROG) $(OBJS)
.PHONY: clean
GCC4.8.5を搭載したSUSELeap 42.3を実行するWSLコンテナーでコードをビルドし、テストしました。
回答
観察
非常に興味深い質問です。
プログラムを実行したときに思いついた数字は
ソートされた10248個の個別の値
16384アイテムの選択ソート：353ミリ秒
16384アイテムの挿入ソート：176ミリ秒
これにより、挿入ソートは選択ソートの2倍の速度になります。これは、32GBとInteli7-6820HQプロセッサを搭載した4年前のLenovoThinkpadP50でVisualStudio2019を使用しているWindows10です。
関数を使用するようにコードを書き直した後、これが私の結果です。選択ソート時間がわずかに増加したことに注意してください。
挿入によってソートされた
10248個の個別の値選択
選択によってソートされた10248個の個別の値16384アイテムのソート：355ミリ秒
16384アイテムの挿入ソート：176ミリ秒
グローバル変数に関するセクションを追加しようとしましたが、最初にコードを書き直そうとしたときに、その理由を発見しました。配列が大きすぎて、少なくとも私のラップトップでは、スタックがそれらをサポートできません。また、メモリ割り当てを使用して、スタックではなくヒープにできるだけ多くのデータを配置しました。これは、グローバル変数を回避する1つの方法です。
両方selectionを最適化しinsertionて数値を下げることができるかどうかを確認することをお勧めします。
必要に応じて変数を宣言します。Cプログラミング言語では、コードブロックの先頭ですべての変数を宣言する必要がなくなりました。
コードの改善
あなたは一生懸命働いたか、少なくともでコードを書きすぎましたmain()。
私は3つの異なる機能が可能であると考えており、そのうちの1つは既存のコードの繰り返しを減らしたでしょう。
ソート関数へのポインターを使用して、テスト用の共通関数を作成できます。
時間をテストする前にソートを検証することにしました。ソートの1つがタイミングで機能しない場合、それは意味がありません。
以下の実装を考えると、新しいソート関数を追加することで、より多くのソートをテストして最適なソートを見つけることができます。
これが私が見る関数です：
int original_items[NUM_ITEMS];
static void generate_unsorted_data(void)
{
srand(RANDOM_SEED);
for (int i = 0; i < NUM_ITEMS; i++) {
original_items[i] = rand() % NUM_ITEMS;
}
}
static void validate_results(void(*ptr_to_sort_function)(int data[], unsigned int count), char *func_name)
{
int *sorted_items = calloc(NUM_ITEMS, sizeof(*sorted_items));
if (!sorted_items)
{
fprintf(stderr, "calloc failed in validate_results\n");
return;
}
memcpy(sorted_items, original_items, sizeof(original_items));
ptr_to_sort_function(sorted_items, NUM_ITEMS);
int num_distinct = 1;
for (int i = 1; i < NUM_ITEMS; i++) {
if (sorted_items[i] < sorted_items[i - 1]) {
printf("%s result validation failed.\n", func_name);
}
if (sorted_items[i] != sorted_items[i - 1]) {
num_distinct++;
}
}
printf("%d distinct values sorted by %s\n", num_distinct, func_name);
free(sorted_items);
}
static void time_test_sort(void(*ptr_to_sort_function)(int data[], unsigned int count), char* func_name)
{
clock_t start_time;
clock_t total_time;
int* sorted_items = calloc(NUM_ITEMS, sizeof(*sorted_items));
if (!sorted_items)
{
fprintf(stderr, "calloc failed in validate_results\n");
return;
}
total_time = 0;
for (int i = 0; i < ITERATIONS; i++) {
memcpy(sorted_items, original_items, sizeof(original_items));
start_time = clock();
ptr_to_sort_function(sorted_items, NUM_ITEMS);
total_time += clock() - start_time;
}
printf("%s sort on %d items: %ld ms\n", func_name, NUM_ITEMS, (long)(total_time / ITERATIONS / CLOCKS_PER_MS));
free(sorted_items);
}
int main(void) {
generate_unsorted_data();
validate_results(insertion, "insertion");
validate_results(selection, "selection");
time_test_sort(selection, "selection");
time_test_sort(insertion, "insertion");
}
挿入ソートは、ほとんど知られていない最適化を可能にします。コード化されているように、内部ループの各反復は2つの比較を実行します：j > 0とdata[j - 1] > test_value。1つで逃げることは可能です：
if (test_value < data[0]) {
// No need to compare data anymore. Just shift.
for (j = i; j > 0; j--) {
data[j] = data[j - 1];
}
} else {
// No need to check for indices anymore. data[0] is a natural sentinel.
while (data[j - 1] > test_value) {
data[j] = data[j - 1];
--j;
}
}
data[j] = test_value;
ない裸ループマントラおもむく、ループが関数にリファクタリング、しなければならないshiftとunguarded_insert、それぞれ。
明確にするために、リンクされた質問に対するジョン・ボリンジャーの答えにコメントしたuser58697は私です。
質問の要点はリファクタリングではなくパフォーマンスに関するものなので、コードのパフォーマンスについて説明します。
残念ながら、質問には実際の数は含まれていません。
私の挿入ソートは、ランダム入力での選択ソートよりもはるかに高速であり（実行時間の約4分の1）、逆ソート入力の最悪の場合でも、挿入は明らかに勝者でした。
上記のコードは、現在使用しているコンピューター上のバージョンであるため、Linux上のGCC9.2.1でコンパイルしました。
結果は次のとおりです。
問題のコードの場合、ランダムな順序：
10350 distinct values sorted Selection sort on 16384 items: 78 ms Insertion sort on 16384 items: 38 ms逆ソートされた入力の場合：
16384 distinct values sorted Selection sort on 16384 items: 77 ms Insertion sort on 16384 items: 77 ms
複数回実行した場合の変動は約1msであるため、結果は十分に正確である必要があります。
つまり、次のことを意味します。
- お使いのコンパイラは、おそらく選択ソートの最適化、または挿入ソートの最適化に優れていません。
- ランダムデータでは挿入ソートが高速であることが期待されます。これは、挿入ソートの内側のループにブレーク条件があるためです。どちらもO（n ^ 2）の複雑さを持っていますが、ランダムデータの挿入ソートは平均してすでにソートされたデータの半分をチェックするだけでよく、選択ソートは常にソートされていない残りのデータ全体をチェックする必要があります。逆にソートされた入力データの場合、両方のアルゴリズムで同じ数の内部ループを実行する必要があります。
挿入によってより多くのデータが移動するのは正しいですが、それを行う方法では、基本的に無料で取得できます。つまり、移動する値はすでに読み取られており、次の書き込みに使用でき、書き込みはすでにキャッシュにあるメモリ位置に送られます。
他のアーキテクチャやコンパイラは、異なる結果をもたらす可能性があります。
誰かが数学に興味がある場合、選択ソートの比較の数はn *（n-1）/ 2です。これは挿入ソートの最悪の場合の数でもありますが、ランダムデータの挿入ソートの平均数はその値の半分であり、n *（n-1）/ 2/2です。
私はこれをHaswellで実行しています（4770Kですが、特定のモデルは重要ではありません）。私はMSVC2017バージョン15.9 ..とMASMでコンパイルしました。選択ソートと挿入ソートのパフォーマンスの違いは5倍でした：166ms対33ms。その違いはあなたが見たものと似ているので、同じ理由かもしれません。
私は、テストが公正なものであることを保証するために、選択ソートのパフォーマンスがどのように改善されるかについての洞察に特に興味があります。
結局のところ、あるかもしれませんが、そのバージョンとの比較がより公平であるかどうかは簡単な問題ではありません。
ベンチマークにおける他の公平性の懸念は、測定値を取得するものが測定されることを意図したものであることを保証することです。Cコードは実際に実行されるものではないため、Cコードを確認しても、必ずしもその質問に対する洞察が得られるとは限りません。そのことを念頭に置いて、ここに両方のアルゴリズムからの注釈付きの「最も重要なブロック」があり、IntelVTuneで分析されています。だから、ここに、からselection、重要な部分があります：
Address Instruction Clock ticks
0x140001040 mov edx, dword ptr [r11] 1,862,000,000
0x140001043 lea r11, ptr [r11+0x4] 7,000,000
0x140001047 cmp edx, eax 700,000,000
0x140001049 mov ecx, r10d 1,736,000,000
0x14000104c cmovnl ecx, r8d 1,837,500,000
0x140001050 cmovnl edx, eax 7,217,000,000
0x140001053 inc r10d 4,140,500,000
0x140001056 mov r8d, ecx 7,000,000
0x140001059 mov eax, edx 693,000,000
0x14000105b cmp r10d, 0x4000 1,683,500,000
0x140001062 jb 0x140001040
クロックティックの分布は、額面inc r10dどおりに取得した場合（無害である必要があります）、完全には意味がありませんが、速度低下のわずかな「スミアアウト」は正常です。とにかく、cmov使用され、cmovVTuneによると主な原因です。たぶん、かなりの時間cmov がかかるはずです、結局のところ、それは実際に仕事をしているものです（選択ソートの選択部分）。
cmov残念ながら、ブランチを使用するかどうかはソースコード次第ではありません。Cコードの観点からは、それは制御不能な変数であり、潜在的に大きな影響を及ぼします。完全を期すために、とにかく調査する必要があります。したがって、追加の実験として、MSVCが発行したコードを取得しselection、ブランチを使用するように変更しました（そして、それを機能させるために最小限の変更を行いましたが、MSVCはほんの少しだけ不正行為を行っています。実際にはポインタを関数に渡しますが、グローバルを直接参照します）：
_text SEGMENT
selection2 PROC FRAME
.endprolog
mov qword ptr [rsp+8],rbx
mov qword ptr [rsp+10h],rsi
mov qword ptr [rsp+18h],rdi
mov rsi,rcx
mov r9d,1
mov rbx,rsi
_block2:
mov eax,dword ptr [rbx]
mov edi,eax
lea r8d,[r9-1]
mov r10d,r9d
cmp r9d,4000h
jae _block5
mov ecx,r9d
lea r11,[rsi+rcx*4]
_block4:
mov edx,dword ptr [r11]
lea r11,[r11+4]
cmp edx,eax
jge _skip
mov r8d, r10d
mov eax, edx
_skip:
inc r10d
cmp r10d,4000h
jb _block4
_block5:
inc r9d
mov ecx,r8d
mov dword ptr [rsi+rcx*4],edi
mov dword ptr [rbx],eax
add rbx,4
lea eax,[r9-1]
cmp eax,3FFFh
jb _block2
mov rbx,qword ptr [rsp+8]
mov rsi,qword ptr [rsp+10h]
mov rdi,qword ptr [rsp+18h]
ret
selection2 ENDP
END
（これをLinuxに移植するには、さまざまな変更が必要になります。cmovブランチへの変換をやり直す方が簡単です）
でC側にインポートされextern void selection2(int* data);ます。
結果：72ms。はるかに高速！それでも挿入ソートの2倍の速度cmovですが、バージョンと比較すると大幅に改善されています。
しかし、何がcmov公正ですか、バージョンは公正ですか？これはMSVCがデフォルトで出力するものであるため、その意味では「選択ソートの実際のパフォーマンス」を表している可能性があります。ただし、これcmovはアルゴリズムに固有のものではなく、（明らかに誤った！）コンパイラ最適化によるアーティファクトです。 。別のコンパイラでもブランチの使用を決定できます。そのため、@ pacmaninbwは4倍または5倍のギャップではなく同様の2倍のパフォーマンスギャップを報告します。
幸いなことに（多分？）選択ソートは両方の方法を失ったので、これらすべてが勝者を変えることはありませんが、そうなる可能性があります。
MSVCが出力するコードinsertionは、実際にはそれほど興味深いものではありません。アセンブリコードは、カーブボールではなく、期待どおりの動作をします。念のために見ておくのは良いことです。
最後に、SIMDを使用して両方のアルゴリズムを最適化できることに注意してください。これにより、バランスが崩れる可能性があります。それらのアルゴリズムの「真の可能性を解き放つ」と見なすことができるので、その意味で公正かもしれません。または、「行き過ぎ」と見なされる可能性があります。これは、アルゴリズムを代表するものであるか、それをはるかに超えてアセンブリコードの特定のスニペットを比較することであり、その意味では不公平です。