-1

コードを見て、コメントを提供してください。私が実装しようとしているのは、マルチスレッド マージ ソートです。もっと並列にできる？

私が入れた2つの「結合」呼び出しについて少し心配しています。それらは並列処理を妨げるためです。

次のロジックが使用されます:
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 桁 (またはそれ以上)実行する可能性があります。

2 つ目の問題は、作成するスレッドの数に関係なく、実際の並列処理は、使用しているハードウェア上の物理プロセッサ/コアの数によって制限されることです。コアよりも多くのスレッドがある場合、ほとんどの場合、スレッドは実行待ちのキューに置かれます。

並列ソートに真剣に取り組んでいる場合は、それを適切に行う方法を読む必要があります。（現在行っているように）たくさんのスレッドを作成するだけではうまくいきません。また、並べ替える要素が 100,000 個以上ない限り、わざわざ (スレッドを使用して) 並列化する価値さえないでしょう。

参考文献:

于 2013-08-22T11:41:47.380 に答える