3

マージソートのマルチスレッドバージョンを作成する必要がある宿題の問題に取り組んでいます。実装することはできましたが、スレッドの作成を停止することはできません。ExecutorServiceを使用してスレッドの作成を制限することを検討しましたが、現在のコード内でそれを実装する方法がわかりません。

これが私の現在のマルチスレッドマージソートです。私のsort()方法が生まれるのは、特定の戦略パターンを実装する必要があるからです。

@Override
public int[] sort(int[] list) {
    int array_size = list.length;
    list = msort(list, 0, array_size-1);
    return list;
}

int[] msort(int numbers[], int left, int right) {
    final int mid;
    final int leftRef = left;
    final int rightRef = right;
    final int array[] = numbers;
    if (left<right) {
        mid = (right + left) / 2;
        //new thread
        Runnable r1 = new Runnable(){
            public void run(){
                msort(array, leftRef, mid);     
            }
        };
        Thread t1 = new Thread(r1);
        t1.start();

        //new thread
        Runnable r2 = new Runnable(){
            public void run(){
                msort(array, mid+1, rightRef);
            }
        };
        Thread t2 = new Thread(r2);
        t2.start();
        //join threads back together
        try {
            t1.join();
            t2.join();

        } catch (InterruptedException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
        merge(numbers, leftRef, mid, mid+1, rightRef);
    }
    return numbers;
}

void merge(int numbers[], int startA, int endA, int startB, int endB) {
    int finalStart = startA;
    int finalEnd = endB;
    int indexC = 0;
    int[] listC = new int[numbers.length];

    while(startA <= endA && startB <= endB){
        if(numbers[startA] < numbers[startB]){
            listC[indexC] = numbers[startA];
            startA = startA+1;
        }
        else{
            listC[indexC] = numbers[startB];
            startB = startB +1;
        }
        indexC++;
    }

    if(startA <= endA){
        for(int i = startA; i < endA; i++){
            listC[indexC]= numbers[i];
            indexC++;
        }
    }

    indexC = 0;
    for(int i = finalStart; i <= finalEnd; i++){
        numbers[i]=listC[indexC];
        indexC++;
    }
}

どんなポインタでもありがたいことに受け取られるでしょう。

4

2 に答える 2

3

@mcdowella のコメントに続いて、並行して実行されるスレッドの数を制限したい場合は、fork/join フレームワークが最善の策だと思います。

Java7 で fork/join フレームワークを使用することはおそらく許可されていないため、これが宿題の助けにならないことはわかっています。しかし、それは何かを学ぼうとしていますね?;)

私がコメントしたように、あなたのマージ方法は間違っていると思います。故障箇所は特定できませんが、書き直しました。そのマージ メソッド中に発生する可能性のあるすべてのエッジ ケースを含むテストケースを作成し、それが機能することを確認したら、それをマルチスレッド コードに戻すことを強くお勧めします。

@lbalazscs は、fork/join ソートが javadocs に記載されているというヒントも提供しましたが、他に何もする必要がありませんでした。そのため、Java7 で実装した場合の解決策を示します。

public class MultithreadedMergeSort extends RecursiveAction {

  private final int[] array;
  private final int begin;
  private final int end;

  public MultithreadedMergeSort(int[] array, int begin, int end) {
    this.array = array;
    this.begin = begin;
    this.end = end;
  }

  @Override
  protected void compute() {
    if (end - begin < 2) {
      // swap if we only have two elements
      if (array[begin] > array[end]) {
        int tmp = array[end];
        array[end] = array[begin];
        array[begin] = tmp;
      }
    } else {
      // overflow safe method to calculate the mid
      int mid = (begin + end) >>> 1;
      // invoke recursive sorting action
      invokeAll(new MultithreadedMergeSort(array, begin, mid),
          new MultithreadedMergeSort(array, mid + 1, end));
      // merge both sides
      merge(array, begin, mid, end);
    }
  }

  void merge(int[] numbers, int startA, int startB, int endB) {
    int[] toReturn = new int[endB - startA + 1];
    int i = 0, k = startA, j = startB + 1;
    while (i < toReturn.length) {
      if (numbers[k] < numbers[j]) {
        toReturn[i] = numbers[k];
        k++;
      } else {
        toReturn[i] = numbers[j];
        j++;
      }
      i++;
      // if we hit the limit of an array, copy the rest
      if (j > endB) {
        System.arraycopy(numbers, k, toReturn, i, startB - k + 1);
        break;
      }
      if (k > startB) {
        System.arraycopy(numbers, j, toReturn, i, endB - j + 1);
        break;
      }
    }
    System.arraycopy(toReturn, 0, numbers, startA, toReturn.length);
  }

  public static void main(String[] args) {
    int[] toSort = { 55, 1, 12, 2, 25, 55, 56, 77 };
    ForkJoinPool pool = new ForkJoinPool();
    pool.invoke(new MultithreadedMergeSort(toSort, 0, toSort.length - 1));
    System.out.println(Arrays.toString(toSort));

  }

スレッドプールの構築により、アクティブな並列スレッドの数がプロセッサのコア数に制限されることに注意してください。

ForkJoinPool pool = new ForkJoinPool();

それのjavadocによると：

デフォルトのスレッド ファクトリ、UncaughtExceptionHandler なし、非非同期 LIFO 処理モードを使用して、java.lang.Runtime.availableProcessors と等しい並列処理で ForkJoinPool を作成します。

それがあなたの主な問題だと思うので、私のマージ方法があなたのものとどのように異なるかも注目してください。あなたのマージ方法を私のものに置き換えれば、少なくともあなたのソートは機能します。

于 2013-01-30T21:36:28.083 に答える
1

mcdowella が指摘したように、Java 7 の Fork/Join フレームワークは、再帰的に小さな断片に分割できるタスクのためのものです。

実際、RecursiveActionの Javadoc には、最初の例としてマージソートがあります:)

また、ForkJoinPoolは ExecutorService であることにも注意してください。

于 2013-01-30T20:50:07.800 に答える