-1

私は大学の 1 年生の CS 学生です。私の現在の課題は、並行性とクイックソート アルゴリズムに関するものです。これは課題なので、すべてがどのように機能するかをよりよく理解するために、自分でコードを書きたいと思っています。したがって、回答の際は Java ではなく疑似コードを使用してください。

私のプログラムは、3 つの引数を指定してコマンド ラインで起動することになっています。単語を含むインファイル、アウトファイル名、および数値 (インファイルをソートするときに使用するスレッドの数をプログラムに通知します)。プログラムを起動すると、クイックソートアルゴリズムと同時実行性を使用して、ファイル内の単語をソートすることになっています。各スレッドには、ファイル内の単語の配列のセクション (スレッドの長さを単語数で割ったもの) が割り当てられます。すべてのスレッドが配列のセクションの並べ替えを完了すると、プログラムはスレッドから返された各配列を 1 つの長い並べ替えられた単語の配列に追加し、それらを出力ファイルに書き込みます。

私の質問は次のとおりです。どこから始めればよいですか? では、どの時点で配列セクションのピボット要素を選択すればよいでしょうか? セクションを作成したら、またはセクションで作業するスレッドが開始したら? スレッドを使用したクイックソート アルゴリズムの疑似コードの例を教えてください。

うわー、それはたくさんの質問です！前もって感謝します！:)

4

3 に答える 3

2

データの等しい部分をクイックソートするために複数のスレッドを作成します。各スレッドが完了したら、結果をマージソートして、ソート済みファイルを生成できます。

直面する主な課題は、ファイルの読み取りと書き込みに時間がかかりすぎて、複数のスレッドを使用してもあまり速くならないことです。

もう 1 つの方法は、ピボット ポイントを使用してコレクションを 2 つの部分 (場合によっては不均一) に分割し、2 つのスレッドで両側を並べ替える方法です。スレッド数が cpu と同じになるまでこれを繰り返し、各部分をシングル スレッドで並べ替えます。繰り返しますが、これは 1 つのスレッドを使用するよりも効率的であることに注意する必要があります。

于 2013-04-29T19:12:35.430 に答える
1

これは、ウィキペディアのクイックソート アルゴリズム(疑似コード)です。

  function quicksort('array')
      if length('array') ≤ 1
          return 'array'  // an array of zero or one elements is already sorted
      select and remove a pivot value 'pivot' from 'array'
      create empty lists 'less' and 'greater'
-----------Partition section----------
      for each 'x' in 'array'
          if 'x' ≤ 'pivot' then append 'x' to 'less'
          else append 'x' to 'greater'
-----------End Partition section------
      return concatenate(quicksort('less'), 'pivot', quicksort('greater')) // two recursive calls

分割セクションは同時に実行できません。ただし、複数のスレッドで再帰呼び出しを実行できます。

return concatenate(quicksort('less'), 'pivot', quicksort('greater'))

なる

return concatenate(new Thread(quicksort('less')), 'pivot', new Thread(quicksort('greater')))
于 2013-04-29T19:12:55.117 に答える