parallel-processing - 大きな配列の中央値の並列計算

Question

私は一度この質問をされましたが、まだそれを理解することができませんでした:

N整数の配列があります。ここで、Nは大きく、たとえば 10 億です。この配列の中央値を計算します。ジョブを分散するm+1マシン (mワーカー、1 つのマスター) があるとします。これをどのように行うつもりですか？

中央値は非線形演算子であるため、各マシンで中央値を見つけて、それらの値の中央値を取得することはできません。

Answer 1

並列計算モデルに応じて、アルゴリズムは異なる可能性があります。（注：前の文でリンクされているpdfには、考えられる多くのPDFの一部が含まれています）。

中央値を見つけることは、i^番目の要素を見つける特別な場合です。この問題は「選択問題」と呼ばれるため、Webで並列選択を検索する必要があります。

これが役立つかもしれない1つの論文（残念ながら無料ではありません）です：クラスターの分析を伴う並列選択アルゴリズム。

そして、クエリ「パラレルセレクション」に対するグーグルの最初のリンクは次のようになります：http ：//www.umiacs.umd.edu/research/EXPAR/papers/3494/node18.htmlこれは実際には中央値の中央値を使用します中央値の発見。

Answer 2

高度に並列化可能な並べ替え (マージ並べ替えなど) を実行し、結果から中央値を取得できます。

Answer 3

配列の並べ替えはやり過ぎでしょうか? そうでない場合は、配列を分割してから結果をマージすることをお勧めします。