-1

请查看代码并提供您的意见。我要实现的是多线程合并排序。它可以更并行地完成吗？

我有点担心我提出的两个“加入”电话。因为它们会妨碍并行性。

使用以下逻辑：
1) 使用多个线程递归地划分左数组。
2）使用多个线程递归地划分右数组。
3）等待两个线程完成。
4）最后合并和排序一切。

public class MergeSort {

static public void merge(int[] numbers, int left, int mid, int right) {
    int[] temp = new int[130];
    int i, left_end, num_elements, tmp_pos;

    left_end = (mid - 1);
    tmp_pos = left;
    num_elements = (right - left + 1);

    while ((left <= left_end) && (mid <= right)) {
        if (numbers[left] <= numbers[mid])
            temp[tmp_pos++] = numbers[left++];
        else
            temp[tmp_pos++] = numbers[mid++];
    }

    while (left <= left_end)
        temp[tmp_pos++] = numbers[left++];

    while (mid <= right)
        temp[tmp_pos++] = numbers[mid++];

    for (i = 0; i < num_elements; i++) {
        numbers[right] = temp[right];
        right--;
    }
}

static public void mergeSort(final int[] numbers, final int left,
        final int right) {

    if (right > left) {
        final int mid = (right + left) / 2;
        Thread t = new Thread() {
            @Override
            public void run() {
                mergeSort(numbers, left, mid);
            }
        };
        t.start();

        Thread t1 = new Thread() {

            @Override
            public void run() {
                mergeSort(numbers, (mid + 1), right);
            }
        };

        t1.start();

        try {
            t.join();
            t1.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        merge(numbers, left, (mid + 1), right);
    }
}

public static void main(String[] args) {
    int[] numbers = new int[] { 1, 4, 5, 2, 5, 67, 89, 34, 5, 56, 555, 655,
            33, 2, 34, 45, 5, 1, 2, 2334, 5, 55, 5, 577, 788, 99, 0, 9, 86,
            98, 1, 2, 3, 3, 344, 4, 3443, 343434, 34334343, 443, 3442, 55,
            6, 778, 86, 66, 67778, 8, 88, 9, 9, 999, 8, 900 };

    int len = numbers.length;
    mergeSort(numbers, 0, len - 1);
    for (int i = 0; i < len - 1; i++)
        System.out.println(numbers[i]);

}

}

4

1 回答 1

1

如果有的话，你的代码已经太并行了……尽管在实际意义上它根本不是很并行。

第一个问题是创建线程很昂贵。非常贵。您的代码可能会执行2 个（或更多）数量级的创建线程的指令，而不是线程将执行的有用工作。

第二个问题是，无论您创建多少线程，您的实际并行度都将受到您正在使用的硬件上的物理处理器/内核数量的限制。如果线程数多于内核数，则大多数时间线程将坐在队列中等待运行。

如果您对并行排序很认真，则需要阅读有关如何正确执行此操作的信息。仅仅创建大量线程（就像你现在正在做的那样）是行不通的。此外，除非您有 100,000 个或更多元素要排序，否则可能甚至不值得费心并行化（使用线程）。

参考：

于 2013-08-22T11:41:47.380 回答