パフォーマンスのためにクイックソートを最適化しようとしていました。4M (1<<22) の整数項目 (それぞれ 4 バイト) の場合、72 の同時スレッド (72 コア) をサポートできるシステムで並べ替えるには、並列クイックソート アルゴリズムで 0.5 (0.499703) 秒かかります。並列クイックソートをさらに最適化する効率的な方法を知りたいです。また、特定のワークロードが与えられた場合に、すべての並べ替えアルゴリズムのリーグ テーブルがある場合、他の並べ替えアルゴリズムと比較することに興味がありますか?
質問する
344 次
1 に答える
0
私の知る限り、アルゴリズムをソートするための正規のリーダーボードはありません。ソート アルゴリズムのパフォーマンスは、取得する入力分布、入力のサイズ、プログラミング言語の選択、使用するコンパイラの種類と設定、コア数、環境温度など、さまざまな要因に依存します。部屋、オペレーティングシステムなど。
あなたの他の質問 - クイックソートを最適化する方法 - については、コードを見ずに、確かに言うのは難しいです. 以下は、試してみるとよい一般的なクイックソートの最適化のリストです。
小さな入力に対するより高速なソートへの切り替え: 挿入ソートは 2 次時間で実行されますが、小さな入力の場合は、クイックソートよりもはるかに高速になる可能性があります。ソートする要素の数が特定のしきい値を下回ると、クイックソートの実装が挿入ソートに切り替わることは珍しくありません。これにより、実行時間が大幅に短縮される可能性があります。
内省を追加します。Introsort は、再帰の深さを追跡し、アルゴリズムが劣化しているように見える場合にヒープソートに切り替えるクイックソートの高速バリアントです。これにより、ランタイムが O(n log n) になることが保証され、このケースがトリガーされない場合でもわずかなコストしか発生しません。
より優れたパーティショニング アルゴリズムを使用します。デュアル ピボット クイックソートは、従来のパーティショニング アルゴリズムに代わるものとして最近登場しました。多くの入力でパフォーマンスが向上します。また、多数の重複を含む入力を取得することが予想される場合は、重複要素を適切に処理するパーティショニング スキームの使用を検討してください。
テールコール除去を導入します。多くのクイックソートの実装では、ソートが必要な 2 つの部分配列に対して 2 つの再帰呼び出しが発生しますが、実際にはこれを行う必要はありません。1 つの再帰呼び出しを開始してから、パラメーターを最初の呼び出しに上書きし、全体を while ループに入れて、2 番目の呼び出しを末尾呼び出しとして扱うことができます。
于 2015-08-26T18:36:02.130 に答える