問題タブ [sorting-network]

これは私がずっと前に遭遇した問題です。私はあなたのアイデアを聞いてもいいと思いました。高速に並べ替える必要がある、4 つまたは 8 つの要素の非常に小さな数 (整数) のリストがあるとします。最良のアプローチ/アルゴリズムは何ですか?

私のアプローチは、最大/最小関数を使用することでした（4つの数字をソートする1​​0個の関数、分岐なし、iirc）。

私の質問は、アルゴリズムの種類ではなく、実装に関係していると思います。

この時点でハードウェア依存になるので、SSE3 を搭載した Intel 64 ビット プロセッサを想定します。

ありがとう

別のStackOverflowの質問（これ）に答えると、興味深いサブ問題に遭遇しました。6つの整数の配列をソートする最速の方法は何ですか？

質問は非常に低いレベルなので：

• ライブラリが利用可能であると想定することはできません（そして呼び出し自体にコストがかかります）。プレーンCのみです。
• 命令パイプライン（非常に高いコストがかかる）を空にすることを避けるために、おそらく分岐、ジャンプ、および他のすべての種類の制御フローの中断（&&またはのシーケンスポイントの背後に隠されているものなど）を最小限に抑える必要があり||ます。
• 部屋には制約があり、レジスタとメモリの使用を最小限に抑えることが問題です。理想的には、インプレースソートがおそらく最善です。

本当にこの質問は、ソースの長さを最小化するのではなく、実行時間を最小化することが目標である一種のゴルフです。マイケル・アブラッシュとその続編による「コードの最適化の禅」という本のタイトルで使用されているように、私はそれを「Zening」コードと呼んでいます。

それが興味深い理由については、いくつかの層があります。

• この例は単純で、理解と測定が簡単で、Cスキルはあまり必要ありません。
• 問題に適したアルゴリズムを選択した場合の影響だけでなく、コンパイラと基盤となるハードウェアの影響も示しています。

これが私のリファレンス（ナイーブ、最適化されていない）の実装と私のテストセットです。

生の結果

バリアントの数が増えているので、ここにあるテストスイートにそれらをすべて集めました。使用された実際のテストは、Kevin Stockのおかげで、上に示したものよりも少し単純ではありません。独自の環境でコンパイルして実行できます。さまざまなターゲットアーキテクチャ/コンパイラでの動作に非常に興味があります。（OKみんな、答えに入れてください、私は新しい結果セットのすべての貢献者を+1します）。

私は1年前にダニエル・スタッツバッハ（ゴルフ用）に答えました。彼は当時最速のソリューション（ソーティングネットワーク）のソースでした。

Linux 64ビット、gcc 4.6.1 64ビット、Intel Core 2 Duo E8400、-O2

• qsortライブラリ関数への直接呼び出し：689.38
• ナイーブな実装（挿入ソート）：285.70
• 挿入ソート（Daniel Stutzbach）：142.12
• 挿入ソート展開：125.47
• ランク順：102.26
• レジスター付きランク順：58.03
• ソーティングネットワーク（Daniel Stutzbach）：111.68
• ソーティングネットワーク（Paul R）：66.36
• 高速スワップを使用したネットワーク12の並べ替え：58.86
• ソーティングネットワーク12の並べ替えスワップ：53.74
• ソーティングネットワーク12はSimpleSwapを並べ替えました：31.54
• 高速スワップ付きの並べ替えられたソーティングネットワーク：31.54
• 高速スワップV2を使用した並べ替えネットワーク：33.63
• インラインバブルソート（Paolo Bonzini）：48.85
• 展開された挿入ソート（Paolo Bonzini）：75.30

Linux 64ビット、gcc 4.6.1 64ビット、Intel Core 2 Duo E8400、-O1

• qsortライブラリ関数への直接呼び出し：705.93
• ナイーブな実装（挿入ソート）：135.60
• 挿入ソート（Daniel Stutzbach）：142.11
• 挿入ソート展開：126.75
• ランク順：46.42
• レジスター付きのランク順：43.58
• ソーティングネットワーク（Daniel Stutzbach）：115.57
• ソーティングネットワーク（Paul R）：64.44
• 高速スワップを使用したネットワーク12の並べ替え：61.98
• ソーティングネットワーク12の並べ替えスワップ：54.67
• ソーティングネットワーク12はSimpleSwapを並べ替えました：31.54
• 高速スワップ付きの並べ替えられたソーティングネットワーク：31.24
• 高速スワップV2を使用した並べ替えネットワーク：33.07
• インラインバブルソート（Paolo Bonzini）：45.79
• 展開された挿入ソート（Paolo Bonzini）：80.15

驚くべきことに、いくつかのプログラムではO2の効率がO1よりも低いため、-O1と-O2の両方の結果を含めました。どのような特定の最適化がこの効果をもたらすのだろうか？

提案されたソリューションに関するコメント

挿入ソート（Daniel Stutzbach）

予想通り、ブランチを最小化することは確かに良い考えです。

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

挿入ソートよりも優れています。主な効果は外部ループを回避することから得られたのではないかと思いました。挿入ソートを展開して確認してみたところ、ほぼ同じ数値が得られました（コードはこちら）。

ソーティングネットワーク（Paul R）

これまでで最高。私がテストに使用した実際のコードはここにあります。他のソーティングネットワークの実装のほぼ2倍の速度である理由はまだわかりません。パラメータの受け渡し？ファストマックス？

高速スワップを使用したネットワーク12SWAPの並べ替え

Daniel Stutzbachが提案したように、私は彼の12スワップソーティングネットワークをブランチレス高速スワップと組み合わせました（コードはここにあります）。それは確かに高速であり、1つ少ないスワップを使用して期待できるように、わずかなマージン（約5％）でこれまでのところ最高です。

ブランチレススワップは、PPCアーキテクチャでifを使用する単純なスワップよりもはるかに（4倍）効率が低いように見えることにも注目してください。

ライブラリqsortの呼び出し

別の参照ポイントを与えるために、私は提案されたようにライブラリqsortを呼び出すことも試みました（コードはここにあります）。予想どおり、はるかに遅くなります。10〜30倍遅くなります...新しいテストスイートで明らかになったように、主な問題は最初の呼び出し後のライブラリの初期ロードであるように見え、他のライブラリと比べてもそれほど悪くはありません。バージョン。私のLinuxでは3倍から20倍遅いです。他の人がテストに使用する一部のアーキテクチャでは、さらに高速に見えるようです（ライブラリqsortはより複雑なAPIを使用しているため、このアーキテクチャには本当に驚いています）。

順位

Rex Kerrは、まったく異なる別の方法を提案しました。配列の各項目について、その最終位置を直接計算します。ランク順の計算には分岐が必要ないため、これは効率的です。この方法の欠点は、配列の3倍のメモリ量（ランク順を格納するための配列と変数の1つのコピー）を必要とすることです。パフォーマンスの結果は非常に驚くべきものです（そして興味深いものです）。32ビットOSとIntelCore2Quad E8300を使用したリファレンスアーキテクチャでは、サイクル数は1000をわずかに下回りました（分岐スワップを使用したネットワークの並べ替えなど）。しかし、64ビットボックス（Intel Core2 Duo）でコンパイルして実行すると、パフォーマンスが大幅に向上しました。これまでのところ最速になりました。私はついに本当の理由を見つけました。私の32ビットボックスはgcc4.4.1を使用し、64ビットボックスはgcc4.4を使用します。

更新：

上記の公開された図が示すように、この効果はgccの新しいバージョンによってさらに強化され、ランク順は他の代替手段の2倍の速度になりました。

並べ替えられたスワップを使用したネットワーク12の並べ替え

gcc4.4.3を使用したRexKerr提案の驚くべき効率は、私に不思議に思いました。メモリ使用量が3倍のプログラムは、ブランチレスソーティングネットワークよりもどのように高速でしょうか。私の仮説は、書き込み後に読み取られる種類の依存関係が少なく、x86のスーパースカラー命令スケジューラをより適切に使用できるようにするというものでした。それは私にアイデアを与えました：書き込み後の読み取り依存関係を最小化するためにスワップを並べ替えます。もっと簡単に言えSWAP(1, 2); SWAP(0, 2);ば、両方が共通のメモリセルにアクセスするため、最初のスワップが終了するのを待ってから2番目のスワップを実行する必要があります。これを行うとSWAP(1, 2); SWAP(4, 5);、プロセッサは両方を並行して実行できます。私はそれを試しましたが、期待どおりに機能し、ソーティングネットワークは約10％高速に実行されています。

単純なスワップを使用したネットワーク12の並べ替え

Steinar H. Gundersonが最初の投稿から1年後、コンパイラーの裏をかくことを試みて、スワップコードを単純に保つべきではないと提案しました。結果のコードは約40％速いので、それは確かに良い考えです！彼はまた、x86インラインアセンブリコードを使用して手動で最適化されたスワップを提案しました。最も驚くべきことは（プログラマーの心理学に関するボリュームを示しています）、1年前にそのバージョンのスワップを試した人は誰もいなかったことです。私がテストに使用したコードはここにあります。他の人は、C高速スワップを書く他の方法を提案しましたが、それはまともなコンパイラを備えた単純なものと同じパフォーマンスをもたらします。

「最良の」コードは次のとおりです。

私たちのテストセットを信じるなら（そして、はい、それはかなり貧弱です、それは私たちが測定しているものを短く、単純で理解しやすいという単なる利点です）、1つのソートの結果のコードの平均サイクル数は40サイクル未満です（ 6つのテストが実行されます）。これにより、各スワップは平均4サイクルになります。私はそれを驚くほど速く呼んでいます。他に可能な改善はありますか？

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

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

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

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

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

挿入ソート（Daniel Stutzbach）

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

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

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

編集1：

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

5要素ソートのソーティングネットワークの実装を探していますが、SOに関する適切なリファレンスが見つからなかったため、nのすべての小さい値（少なくともn = 3）のソーティングネットワークを要求したいと思います。 n = 6までですが、より高い値も素晴らしいでしょう。良い答えは、少なくともそれらを「スワップ」（2つの要素でソート）操作のシーケンスとしてリストする必要がありますが、低次のソートネットワークの観点から再帰的な分解を見るのも良いかもしれません。

私のアプリケーションでは、実際には5つの要素の中央値のみを考慮し、実際にはそれらを整理していません。つまり、中央値が正しい位置にある限り、他の4つの要素の順序は結果で指定されない可能性があります。ソーティングネットワーク関連のアプローチを使用して、完全なソートを実行するよりも少ないスワップで中央値を計算できますか？もしそうなら、私の問題（n = 5の場合）や他の場合のそのような解決策も素晴らしい答えになります。

（注：Cは私が使用する言語であり、Cタグをフォローしている人は良い答えがあると思うので、この質問にCのタグを付けましたが、答えが実際にCで書かれているか、擬似コードで書かれているかは気にしません。 Cに簡単に変換できる限り、上記の基準が満たされている限り、当然Cに変換されます。）

ソートを使用するアルゴリズムを実装しました。10^7要素の配列をソートするのに約0.4秒かかるThrust::sort_by_keyを試しました。

バイトニックソートネットワークはThrust::sort_by_keyよりも高速である必要があると思いました。ただし、バイトニックソートでは、上記と同じ配列をソートするのに約2.5秒かかりました。SDKが提供するバイトニックソートネットワークを使用しました。元のバイトニックソートを少し変更しました。

理由を教えてください。または私にいくつかのアドバイスを与えますか？

ありがとう、

Yik

2011年8月15日

C++ で約 3 ～ 10 個の要素を持つ非常に短い固定長配列をソートすることを含む、パフォーマンスが重要なコードがあります (パラメーターはコンパイル時に変更されます)。

それぞれの可能な入力サイズに特化した静的ソートネットワークは、おそらくこれを行うための非常に効率的な方法であると思いました: どのケースにいるかを把握するために必要なすべての比較を行い、次にソートするために最適な数のスワップを行います配列。

これを適用するには、ちょっとしたテンプレート マジックを使用して配列の長さを推測し、正しいネットワークを適用します。

明らかに、これらすべてをコーディングするのは非常に面倒なので、次のようにします。

• これが努力する価値があるかどうかについて、誰か意見はありますか?
• この最適化が std::sort などの標準実装に存在するかどうかは誰にもわかりませんか?
• この種の並べ替えネットワークを実装するコードを簡単に入手できる場所はありますか?
• おそらく、テンプレート マジックを使用して静的にこのような並べ替えネットワークを生成することは可能でしょう..

今のところ、展開やその他のコンパイル時の最適化を促進することを期待して、(上記のように) 静的テンプレート パラメーターを使用して挿入並べ替えを使用するだけです。

あなたの考えを歓迎します。

更新: 「静的」挿入ショートと std::sort を比較するテスト コードをいくつか書きました。(静的とは、配列のサイズが固定され、コンパイル時に推定されることを意味します (おそらくループのアンローリングなどを許可します)。少なくとも 20% の NET の改善が得られます (世代がタイミングに含まれることに注意してください)。プラットフォーム:クラン、OS X 10.9。

stdlib の実装と比較したい場合、コードはhttps://github.com/rosshemsley/static_sortingにあります。

私はまだ、コンパレータ ネットワーク ソーターの優れた実装セットを見つけていません。

C ++のRobert Sedwick Algorithmsで偶数マージソートを研究しています。

テキストの一部として、奇偶マージソートを使用してソートネットワークで並列ソートを実装する方法について言及しました。この文脈で、著者はバタフライネットワークについて言及しました

私の質問は、基本的にバタフライ ネットワークとは何か、なぜバタフライと呼ばれているのかということです。簡単な例で説明していただければ幸いです。

私はそれをグーグルで検索しましたが、例による簡単な説明が見つかりません。

並べ替えネットワークとして書き直された挿入並べ替えは、次のようなものを生成します。

たとえば、次の比較を使用して、6 つの項目を並べ替えます。

ここで、並べ替えたい 7 番目の値があるとします。変更は簡単で、別のセット/行の比較を追加します...

bitonic などの他の種類は、特に前の行に至る所で追加を行う必要があるという点で、より複雑な変更が必要です。

私の質問は次のとおり です。検索で余分な項目をサポートするために簡単に1行追加できる、挿入などの他の種類はありますか? 私は特に、bitonic のような計算の複雑さがより低いものに興味があります。

宿題のドキュメントに質問があり、質問を視覚化して理解するのに苦労しています。質問は次のとおりです。

1 から n の範囲の c 個の整数ペアのリストとして、c 個の比較器を持つ n 入力比較ネットワークを表すことができます。2 つのペアに共通の整数が含まれている場合、ネットワーク内の対応するコンパレータの順序は、リスト内のペアの順序によって決まります。この表現が与えられたとき、比較ネットワークの深さを決定するための O(n + c) 時間 (シリアル) アルゴリズムを説明してください。

比較ネットワークのコンテキストで整数のペアを持つとはどういう意味ですか? 通常、各水平線が数値を表す比較ネットワークを示すために、以下の表記を使用しました。