1

マルチスレッドのマージソートを作成しようとしていますが、非常に紛らわしい問題が発生しています。スレッドが変数を共有/使用する方法のルールを完全には認識していません...

たとえば、Runnableクラス内で、そのRunnableの別のインスタンスを作成し、それを配列の1つとしてパラメーターとして渡す場合、そのクラスを編集すると転送されますか？彼らがそうしているように見えますが、私が予期しない行動をしているようにも見えます。

これが私のコードです：

public class PSort implements Runnable {

private int [] Arr;
private int begin;
private int end;

public void run () {
    // Base Case - Insertion sort
    if(this.end-this.begin <= 10) {
        InsertionSort();
    }
    else {
        int left_start  = this.begin;
        int left_end    = this.begin + (this.end-this.begin)/2;
        int right_start = this.begin + (this.end-this.begin)/2 + 1;
        int right_end   = this.end;


        Thread t1 = new Thread(new PSort(this.Arr, left_start, left_end));
        Thread t2 = new Thread(new PSort(this.Arr, right_start, right_end));
        t1.start();
        t2.start();

        try {
            t1.join();
            t2.join();

            merge(left_start, left_end, right_start, right_end);
        } catch (Exception e) {}
    }
}

public PSort (int[] A, int begin, int end) {
    this.Arr = A;
    this.begin = begin;
    this.end = end;
    System.out.println("New thread: " + this.begin + " " + this.end);
}

public static void ParallelSort (int[] A, int begin, int end) {

    PSort psort = new PSort(A, begin, end);
    Thread thread = new Thread(psort);

    thread.start();

    try {
        thread.join();
        psort.printArray();
    } catch (InterruptedException e) {}
}

public void printArray() {
    int count = 0;
    for(int x = this.begin; x < this.end; x++) {
        if(count < 10) {
            System.out.print(Arr[x] + " ");
            count++;
        }
        else {
            count = 1;
            System.out.print("\n" + Arr[x] + " ");
        }
    }
}

private void InsertionSort () {
    for(int x = this.begin; x < this.end; x++) {
        int currentNum = this.Arr[x];
        int hole = x;
        while((hole > 0) && (this.Arr[hole-1] > currentNum)) {
            this.Arr[hole] = this.Arr[hole-1];
            hole = hole - 1;
        }
        this.Arr[hole] = currentNum;
    }
}

private void merge (int left_start, int left_end, int right_start, int right_end) {
    /*
    int length = right_end - left_start;

    int[] temp = new int[length];
    int leftP = left_start;
    int rightP = right_start;
    int index = 0;

    while((leftP <= left_end) && (rightP < right_end)) {
        if(Arr[leftP] < Arr[rightP]) {
            temp[index++] = Arr[leftP++];
        }
        else {
            temp[index++] = Arr[rightP++];
        }
    }   
    while(leftP <= left_end) {
        temp[index++] = Arr[leftP++];
    }
    while(rightP < right_end) {
        temp[index++] = Arr[rightP++];
    }

    System.arraycopy(temp, 0, Arr, left_start, length);
    */

}
}

ここで、0〜9のランダムな整数で満たされたサイズ40の配列を使用してPSort.ParallelSortを呼び出しています。これは、次の出力です。

New thread: 0 40
New thread: 0 20
New thread: 21 40
New thread: 0 10
New thread: 11 20
New thread: 21 30
New thread: 31 40
0 1 1 2 2 2 6 7 7 8 
8 3 3 3 4 4 5 5 6 7 
9 2 3 3 3 4 7 8 9 9 
2 2 6 7 7 7 8 8 9 9

ルーチンの「マージ」セクションをコメントアウトしたので、出力の個々の行が正しくソートされることを期待しますが、そうではないことに注意してください。私はInsertionSortを単独でテストしましたが、失敗することはないようです。そのため、ここでは、完全に無視している並行性の問題がいくつか発生しているようです。

注：ここでは、より深刻な問題が発生していることに気付きました。これは、マージしていなくても、配列全体の最後の2行に向かって数値が大きくなるためです...

4

1 に答える 1

2

バグはInsertionSortメソッドにあります（ちなみに、小文字で始まる名前を付ける必要があります）。

int hole = x;
while ((hole > 0) && /* ... */) {
    // ...
    hole--;
}

したがって、割り当てられたセグメント内にあるxから開始しますが、0に戻ると、すべてのスレッドが同じセグメントに書き込むことになります。はい、データはスレッド間で共有されます。これは、マルチスレッドの場合の問題です。

于 2012-09-09T05:57:32.243 に答える