15

固定長6int配列の最速のソートに関して、このソートネットワークが挿入ソートのようなアルゴリズムをどのように凌駕するかを完全には理解していません。

その質問から、ソートを完了するために必要なCPUサイクル数の比較を次に示します。

Linux 32ビット、gcc 4.4.1、Intel Core 2 Quad Q8300、-O2

  • 挿入ソート（Daniel Stutzbach）：1425
  • ソーティングネットワーク（Daniel Stutzbach）：1080

使用されるコードは次のとおりです。

挿入ソート（Daniel Stutzbach）

static inline void sort6_insertion_sort_v2(int *d){
    int i, j;
    for (i = 1; i < 6; i++) {
            int tmp = d[i];
            for (j = i; j >= 1 && tmp < d[j-1]; j--)
                    d[j] = d[j-1];
            d[j] = tmp;
    }
}

ソーティングネットワーク（Daniel Stutzbach）

static inline void sort6_sorting_network_v1(int * d){
#define SWAP(x,y) if (d[y] < d[x]) { int tmp = d[x]; d[x] = d[y]; d[y] = tmp; }
    SWAP(1, 2);
    SWAP(0, 2);
    SWAP(0, 1);
    SWAP(4, 5);
    SWAP(3, 5);
    SWAP(3, 4);
    SWAP(0, 3);
    SWAP(1, 4);
    SWAP(2, 5);
    SWAP(2, 4);
    SWAP(1, 3);
    SWAP(2, 3);
#undef SWAP
}

一部のステップは他のステップから独立しているため、ソーティングネットワークは並列ソートに非常に適していることを理解しています。ただし、ここでは並列化を使用していません。

正確な要素数を事前に知っているという利点があるので、より高速になると思います。挿入ソートはどこで、なぜ不必要な比較を行うのですか？

編集1：

これは、これらのコードが比較される入力セットです。

int d[6][6] = {\
    {1, 2, 3, 4, 5, 6},\
    {6, 5, 4, 3, 2, 1},\
    {100, 2, 300, 4, 500, 6},\
    {100, 2, 3, 4, 500, 6},\
    {1, 200, 3, 4, 5, 600},\
    {1, 1, 2, 1, 2, 1}\
};\
4

6 に答える 6

20

ただし、ここでは並列化を使用していません。

最新のCPUは、命令がいつ独立しているかを把握し、それらを並列に実行します。したがって、スレッドが1つしかない場合でも、ソーティングネットワークの並列処理を利用できます。

挿入ソートは正確にどこで不要な比較を行いますか？

追加の比較を確認する最も簡単な方法は、手作業で例を実行することです。 

Insertion sort:
6 5 4 3 2 1
5 6 4 3 2 1
5 4 6 3 2 1
4 5 6 3 2 1
4 5 3 6 2 1
4 3 5 6 2 1
3 4 5 6 2 1
3 4 5 2 6 1
3 4 2 5 6 1
3 2 4 5 6 1
2 3 4 5 6 1
2 3 4 5 1 6
2 3 4 1 5 6
2 3 1 4 5 6
2 1 3 4 5 6
1 2 3 4 5 6

Sorting network:
6 5 4 3 2 1
6 4 5 3 2 1
5 4 6 3 2 1
4 5 6 3 2 1 # These three can execute in parallel with the first three
4 5 6 3 1 2 #
4 5 6 2 1 3 #
4 5 6 1 2 3
1 5 6 4 2 3
1 2 6 4 5 3
1 2 3 4 5 6
1 2 3 4 5 6
于 2010-10-10T16:34:37.710 に答える
4

より良い質問は、なぜソートネットワークが挿入ソート（通常は非常に遅いソート）よりも約50％優れているのかということです。n答えは、小さい場合はbig-Oはそれほど重要ではないということです。OPの質問に関しては、ダニエルが最良の答えを持っています。

于 2010-10-10T17:48:45.860 に答える
1

並列アルゴリズムと直列アルゴリズムで行われる「作業」の量は常にほぼ同じだと思います。仕事が分散されるので、それだけがあなたはより速く出力を得るでしょう。入力のサイズが並列アルゴリズムを使用して正当化するのに十分である場合、説得力のある速度で出力を取得できると思います。

プロセッサ間での配列の挿入ソート分割は、パイプラインを形成するようなものであり、パイプラインを埋めるのに時間がかかり、並列アルゴリズムの利点が得られます。

于 2010-10-10T17:00:24.920 に答える
1

ループの巻き戻しが、ソーティングネットワークアルゴリズムでより速い結果を引き起こしていると思います

于 2010-10-10T16:32:21.740 に答える
0

理論的には、コンパイラが挿入ソートでループを完全に展開できれば、コードはほぼ同じになる可能性があります。最初のループは簡単に展開できますが、2番目のループはそれほど簡単に展開できません。

また、コードはネットワークソートコードほど単純ではないため、コンパイラは最適化を少なくすることができる場合もあります。ネットワークソートよりも挿入ソートの方が依存関係が多いと思います。これは、コンパイラがコードを最適化しようとするときに大きな違いを生む可能性があります（間違っている場合は修正してください）。

于 2010-10-10T16:33:11.317 に答える
0

皆さんの質問は、元の投稿に対するDanielStutzbachの回答で回答されていると思います。

あなたが投稿したアルゴリズムは挿入ソートに似ていますが、より多くの比較を犠牲にしてスワップの数を最小限に抑えたようです。ただし、ブランチによって命令パイプラインが停止する可能性があるため、比較はスワップよりもはるかにコストがかかります。

于 2010-10-10T16:35:45.617 に答える