4

現在、最新のマシンはすべてマルチコアであり、SSE 命令を使用して Windows および Linux ボックスで SIMD 命令をサポートしています。たとえば、C/C++ コードでマージ ソートに切り替えて、QuickSort を忘れる必要がありますか? 理論的には、これを行う理由は、マージソートがより適切に並列化し、メモリ/ディスクをより控えめに使用するため、QuickSort のメモリ集約型操作よりも高速になるためですが、私にはわかりません。実際の経験は何を示していますか？

何かをソートするたびにプロファイリングしてテストする必要はありません。1つの標準的なアプローチを使用したい。現在、そのアプローチは QuickSort です。これは、デフォルトのライブラリ ソート ルーチンであるためです。MergeSort に切り替えて、その切り替えによってより良い結果を経験した人が他にいるかどうか知りたいです。

アップデート - - - - - -

Graham.Reeds の回答は、実際には std::sort と std::stable_sort の間のパフォーマンスのギャップはどのくらい大きいですか? 上記の私の推測が正しく、MergeSort/stablesort への切り替えが正しい可能性があることを示しています。

4

5 に答える 5

2

多くの非回答を得た後、私は数時間を費やして独自の調査を行いました。この結果、はい、マージ ソート (およびその他の関連するソート) は、メモリの集中的な使用が少なくなり、並列化/マルチコアの活用が改善されるため、大幅に高速化されます。さらに、x86 マシン用のマージ型ソートを実装する IPP と呼ばれる Intel による標準の高性能ライブラリがあります。このライブラリに切り替えることで、私が行っている種類のプログラミングで、並べ替えのパフォーマンス (およびその他のベクター型操作) が大幅に向上するようです。

于 2012-12-14T00:01:01.997 に答える
1

C/C++ コードでマージソートに切り替えて、QuickSort を忘れるべきですか?

申し訳ありませんが、質問は時期尚早の最適化の試みのように聞こえます。

理論的には、これを行う理由は、マージソートがより適切に並列化し、メモリ/ディスクをより控えめに使用するため、QuickSort のメモリ集約型操作よりも高速になるためですが、私にはわかりません。実際の経験は何を示していますか？

実際には、常に最初にプロファイリングしてから、結果に基づいて最適化の領域を決定する必要があります。

結果が問題になるのに十分な大きさのデータ セットに対して (または処理フローの重要な領域で) 変更しない限り、使用する並べ替えアルゴリズムを変更する必要さえない可能性があります。

私は通常、std::sort を使用しますが、それが十分でない場合 (まだ発生していませんstd::sort)、アプリケーション フローとアルゴリズムを最適化します。

于 2012-12-12T16:13:43.323 に答える
1

決定的な答えはないと思います。状況によっては、並列化可能なブルート フォース ソートの方が高速な場合があります。特定のケースを分析することは常に重要です。たとえば、複数のコアと SIMD がある場合は、bitonic ソートも検討してください。

于 2012-12-12T15:57:26.470 に答える
0

プロセッサのコア数によって拡張可能で、各プロセッサの処理を利用/最適化するように設計された並列ソート パッケージがあります。TBB (Threading Building Blocks) には、平均時間複雑度 0(n log n) の比較ソートである parallel_sort 関数があることを知っています。

クイックソートにスレッドを実装することもできます。再帰関数は、TBB の parallel_for を使用して簡単に並列処理に変換できます。また、Cilk Plus を調べることもできます。ネット上にはスレッド化された例が多数あります。

于 2012-12-12T17:34:53.060 に答える
0

実際には、自分でプロファイリングして、アプリケーション、データ、環境などでどのように動作するかを確認する必要があります。これは、本質的に、SO に関するすべてのプロファイリング/パフォーマンス/最適化の質問の 99% のようなものに対する答えです。

于 2012-12-12T15:56:13.063 に答える