多线程合并排序，添加其他线程 [英] Multithreaded merge sort, adding additional threads

问题描述

我在Java中的多线程合并排序算法中遇到一个问题。

I am facing one problem in multithreaded merge sort algorithm in java.

我应该将代码修改为3、4、5、6、7、8线程合并通过将原始数组划分为 subArray s进行排序。当前它有2个 subArray s。
如何将原始数组分成3、4、5、6、7、8个 subArray s以实现我的目标？
此外，我应该编写更多方法，因为 mergeSort 方法调用 lefthalf 和目前，righthalf 方法。因此，对于3、4、5、6、7、8个线程，我应该编写其他方法。
我该如何处理？

I should modify the code into 3,4,5,6,7,8 threaded merge sorting by dividing original array into subArrays. Currently it has 2 subArrays. How can I split original array into 3, 4 ,5,6,7,8 subArrays to achive my goal? Moreover, I should write some more methods because mergeSort method calls lefthalf and righthalf methods at the moment. So for 3,4,5,6,7,8 threads I should write additional methods. How can i handle this?

two_threaded_merge_sort.java

two_threaded_merge_sort.java

public class two_threaded_merge_sort {

public static void finalMerge(int[] a, int[] b) {
    int[] result = new int[a.length + b.length];
    int i=0; 
    int j=0; 
    int r=0;
    while (i < a.length && j < b.length) {
        if (a[i] <= b[j]) {
            result[r]=a[i];
            i++;
            r++;
        } else {
            result[r]=b[j];
            j++;
            r++;
        }
        if (i==a.length) {
            while (j<b.length) {
                result[r]=b[j];
                r++;
                j++;
            }
        }
        if (j==b.length) {
            while (i<a.length) {
                result[r]=a[i];
                r++;
                i++;
            }
        }
    }
}

public static void main(String[] args) throws InterruptedException {
    Random rand = new Random();
    int[] original = new int[9000000];
    for (int i=0; i<original.length; i++) {
        original[i] = rand.nextInt(1000);
    }

    long startTime = System.currentTimeMillis();
    int[] subArr1 = new int[original.length/2];
    int[] subArr2 = new int[original.length - original.length/2];
    System.arraycopy(original, 0, subArr1, 0, original.length/2);
    System.arraycopy(original, original.length/2, subArr2, 0, original.length - original.length/2);

    Worker runner1 = new Worker(subArr1);
    Worker runner2 = new Worker(subArr2);
    runner1.start();
    runner2.start();
    runner1.join();
    runner2.join();
    finalMerge (runner1.getInternal(), runner2.getInternal());
    long stopTime = System.currentTimeMillis();
    long elapsedTime = stopTime - startTime;
    System.out.println("2-thread MergeSort takes: " + (float)elapsedTime/1000 + " seconds");
}

}

Worker.java

Worker.java

class Worker extends Thread {
private int[] internal;

public int[] getInternal() {
    return internal;
}

public void mergeSort(int[] array) {
    if (array.length > 1) {
        int[] left = leftHalf(array);
        int[] right = rightHalf(array);

        mergeSort(left);
        mergeSort(right);

        merge(array, left, right);
    }
}

public int[] leftHalf(int[] array) {
    int size1 = array.length / 2;
    int[] left = new int[size1];
    for (int i = 0; i < size1; i++) {
        left[i] = array[i];
    }
    return left;
}

public int[] rightHalf(int[] array) {
    int size1 = array.length / 2;
    int size2 = array.length - size1;
    int[] right = new int[size2];
    for (int i = 0; i < size2; i++) {
        right[i] = array[i + size1];
    }
    return right;
}

public void merge(int[] result, int[] left, int[] right) {
    int i1 = 0;   
    int i2 = 0;   

    for (int i = 0; i < result.length; i++) {
        if (i2 >= right.length || (i1 < left.length && left[i1] <= right[i2])) {
            result[i] = left[i1];   
            i1++;
        } else {
            result[i] = right[i2];   
            i2++;
        }
    }
}

Worker(int[] arr) {
    internal = arr;
}

public void run() {
    mergeSort(internal);
}
}

非常感谢！

推荐答案

需要有一个排序函数，该函数将数组分成k个部分，然后创建k个线程以使用自上而下或自下而上的方法对每个部分进行排序，（从下往上稍微快一点），然后等待所有线程完成。

There needs to be a sort function that separates the array into k parts, then create k threads to sort each part, using either top down or bottom up approach, (bottom up would slightly faster), and wait for all threads to complete.

这时有k个排序的部分。这些可以使用k路合并（复杂）一次全部合并，也可以一次使用多个线程一次合并一对零件（2路合并），但是此时该过程可能受内存带宽限制，因此多线程可能没有太大帮助。

At this point there are k sorted parts. These could be merged all at once using a k-way merge (complicated), or merged a pair of parts at a time (2 way merge), perhaps using multiple threads, but at this point the process is probably memory bandwidth limited, so multi-threading may not help much.

将数组分成k个部分时，可以使用类似的方法来保持大小相似：

When separating the array into k parts, something like this can be used to keep the sizes similar:

int r = n % k;
int s = n / k;
int t;
for each part{
    t = r ? 1 : 0;
    r -= t;
    size = s + t;
}

或

int r = n % k;
int s = n / k + 1;
while(r--){
   next part size = s; // n / k + 1
}
s -= 1;
while not done{
   next part size = s; // n / k
}

这篇关于多线程合并排序，添加其他线程的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！