2

Java でnスレッドの Counting Sort アルゴリズムをコーディングする必要がある大学の課題があります。それ以上の情報は提供されていません。最善の方法は、配列をn 個のセクションに分割し、各スレッドがセクションをソートすることだと考えました。問題は、配列を適切に分割する方法がわからないことです。nセクションではなく、2 セクションに分割する方法の例を見ただけです。

私が説明したように、誰かがそれを分割する方法についてのロジックを提供してくれたり、疑似コードを提供してくれたりしてくれれば幸いです。ソース コードはありません。これは私がしなければならない課題です。

実際の並べ替えには問題はありません。パーティション分割だけです。

ありがとう。

4

2 に答える 2

4

定義

ソートする配列があり、スレッドa[0..n-1]を使用してそれを実行したいとしましょう。k

簡単にするために、最小の要素の値が 0 で、最大の要素の値が であると仮定しましょうm。最小値が 0 でない場合は、要素をスレッドに割り当てるときに値をスケーリングできます。

スレッドへの分割

配列をkチャンクに分割し、それぞれが最大でfloor(m/k) + 1異なる値の要素で構成されるようにします。

i-thチャンクは、次のような要素で構成されてa[j]います。

(i - 1) * (floor(m/k) + 1) <= a[j] < i * (floor(m/k) + 1)

たとえば、10 個の要素を持つ配列がある場合:

a[0..9] = {1, 2, 5, 0, 3, 7, 2, 3 ,4, 6}そしてk = 3、そしてm = 73 つのチャンクは次のとおりです。

chunk_1: elements in range [0,3) -> [1, 2, 0, 2]
chunk_2: elements in range [3,6) -> [5, 3, 3, 4]
chunk_3: elements in range [6,9) -> [6, 7]

次に、各チャンクを個別のスレッドに割り当てます。各スレッドは 1 つのチャンクをソートし、配列全体をソートするには、すべてのスレッドからの結果を順番に連結します。

thread_1 thread_2 ... thread_k

複雑：

ご存じのように、カウント ソートの複雑さは、 がソートする要素の数であり、 が要素O(n + L)の最大値です。nL

まず、各スレッド内の値をそのスレッド内で縮小できることに注意してください。そのL < floor(m/k) + 1ため、各スレッド内のカウント ソートの複雑さは、常にそのスレッド内の要素の数に依存します。

値の分布が均一であると仮定すると、各スレッドの予想される要素数も にfloor(m/k)なるため、各スレッドの合計複雑度は になりますO(m/k)。

于 2013-08-14T10:56:59.943 に答える
0

最初に頭に浮かんだアイデアは、配列を再帰的に分割することです。2分割できるなら4分割もできるってことですよね？

より高度で最新のアプローチは、スレッドやプロセスよりも多くの部分に分割することです。次に、これらのパーツを動的にスレッドに割り当てます。

于 2013-08-14T10:03:59.143 に答える