2

現在、文字列を同時にソートするプログラムに取り組んでいます。私のプログラムはファイルを受け取り、ファイルの各行を配列に読み取り、文字列の配列をより小さな文字列の配列に分割します。次に、プログラムは小さい配列ごとに 1 つのスレッドを開始し、それらをクイックソートします。すべてのスレッドが配列の並べ替えを完了すると、メイン スレッドはスレッド オブジェクトからすべての結果を収集します。次に、ソートされた小さい配列を 1 つの大きなソートされた配列にマージすることになっています。

私は現在、シングルスレッドマージソートを使用して、クイックソートスレッドによって返されたソート済み配列をネストすることでこれを解決しました。ここでの問題は、マージが同時に行われないため、少数のスレッド (1 ～ 4) を使用してファイル内をソートすると、実際にはプログラムのソートが可能な限り高速になることです。スレッドの数を少し (たとえば 15 スレッド) 増やすと、実際にはプログラムの実行速度はスレッド数が少ない場合よりもかなり遅くなります。これを解決するために、マージソート/配列のネストに並行性を導入したいと考えています。

私がやりたいことは、2 つのスレッドがファイル内の部分のクイックソートを完了すると、ファイル内のすべての部分がソートされるまで、新しいスレッドがこれら 2 つの部分を一緒にネストすることです。

サンプルコードや疑似コードに感謝します。前もって感謝します！:)

配列をソートする現在のコード:

public synchronized String[] sort(){
    String[] sortedWords = new String[words.length];
    SortingThread[] sts = new SortingThread[threads];

    for(int i = 0; i < threads; i++){
        sts[i] = new SortingThread(this, splitWords[i]);
    }

    for(SortingThread st : sts){
        st.start();
    }

    for(SortingThread st : sts){
        try {
            st.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
            System.exit(-1);
        }
    }

    indexes = new int[sts.length];

    for(int i = 0; i < indexes.length; i++){
        indexes[i] = 0;
    }


//This is where my merge-sorting currently starts.

    ArrayList<String> toAddTo = new ArrayList<String>();

    while(!allIndexesHaveBeenRead(sts)){
        String globalMinimum = null;
        int globalMinThread = -1;
        currentIteration: for (int i = 0; i < sts.length; i++) {
            String current;
            try{
                current = sts[i].sorted[indexes[i]];
            } catch(Exception e){
                continue currentIteration;
            }
            try{
                if(globalMinimum == null){
                    globalMinimum = current;
                    globalMinThread = i;
                }
                else if(current.compareTo(globalMinimum) < 0){
                    globalMinimum = current;
                    globalMinThread = i;
                }
            } catch (NullPointerException e){
                continue;
            }
        }
        toAddTo.add(globalMinimum);
        indexes[globalMinThread]++;
    }

    sortedWords = toAddTo.toArray(sortedWords);

    int len = 0;
    for (int i = 0; i < sortedWords.length; i++) {
        if(sortedWords[i] != null){
            len++;
        }
    }

    String[] toReturn = new String[len];

    for (int i = 0; i < toReturn.length; i++) {
        toReturn[i] = sortedWords[i];
    }

    return toReturn;
}
4

2 に答える 2

1

あなたの問題のシナリオはこのようなものです

  • メインスレッドは N 個のタスクを実行する必要があります
  • プールから M 個のスレッドを生成し、N 個のタスクで動作します。
  • 少なくとも 1 つのスレッドがタスクを完了し、その結果で何かを行うまで待機します。
  • N 個のタスクがすべて完了するまで、結果を処理し続けます。

Java 5 の CompletionService は、まさに要件を満たしています。

ここにあなたの問題文の解決策があります、

 public class Sorter implements Callable<List<String>> {

    private List<String> data;

public Sorter(List<String> input) {
    data = input;
}

@Override
public List<String> call() throws Exception {
    Collections.sort(data);
    return data;
}

 }

そしてメインクラスでは、

  CompletionService service = new  ExecutorCompletionService(Executors.newFixedThreadPool(5));

    List<String> result = new ArrayList<String>();

    String readline = null;
    Callable<List<String>> sorter = null;
    String[] words = null;
    int noOfRunningFutures = 0;

     while ((readline = br.readLine()) != null) {
        words = readline.split(" ");
        List<String> input = Arrays.asList(words);
        sorter = new Sorter(input);

        service.submit(sorter);

        // add them to the number of futures which I am creating - to keep track of the Queue length
        noOfRunningFutures ++;
    }


    while (noOfRunningFutures > 0) 
    {
        try {

            // this is a blocking call - whenever there is a worker which is already completed
            // then it is fetched from the Queue                 
            Future<List<String>> completed = service.take();
            noOfRunningFutures --;

            // get the value from computed from the Future
            List<String> sorted =  completed.get();

            result.addAll(sorted);

            Collections.sort(result);
        } catch (InterruptedException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        } catch (ExecutionException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
    }

これがお役に立てば幸いです。

于 2013-05-12T21:02:27.623 に答える
1

私は、SourceForge の TymeacDSE という fork-join プロジェクトを管理しています。これはまさにあなたが探しているものです。サブセットを並べ替えてから、サブセットのグループを 1 つの最終的な配列にマージします。こちらをご覧ください

于 2013-05-13T13:11:57.040 に答える