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);
    */

}
}

现在，我用一个大小为 40 的数组调用 PSort.ParallelSort，其中填充了随机整数 0-9，这是我得到的输出：

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，它似乎从来没有失败过，所以这里似乎存在一些我完全忽略的并发问题。

注意：我意识到这里有一些更严重的问题，因为更高的数字被加权到整个数组的最后两行，即使我没有合并......

4

1 回答 1

2

该错误在您的 InsertionSort 方法中（顺便说一下，它应该以小写字母开头）：

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

所以你从 x 开始，它在分配的段内，但又回到0，所以所有线程最终都写在相同的段上。是的，数据在线程之间共享，这就是多线程时的难点。

于 2012-09-09T05:57:32.243 回答