并发线程合并排序

Question

我必须编写并发合并排序应用程序。每次数组被拆分时，我都必须为右半部分创建一个新线程（最大线程数为 5 -> 所以 5 次），它继续 Mergesort 算法。

这是我的程序：

class Mergesorts implements Runnable{

    private int[] internal;

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

    private void processCommand(int [] array) {
        if (array.length > 1) { 
            int[] left = leftHalf(array);
            int[] right = rightHalf(array);
            processCommand(left);
            processCommand(right);
            merge(array, left, right);
        }
    }

    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 run() {
        processCommand(internal);
    }
}

如何重写我的代码以按上述方式进行并发排序？

我如何编辑我的代码以使其最多只创建 5 个线程而不是更多？

private void processCommand(int [] array) {
    if (array.length > 1) {


        int[] right = rightHalf(array);
        int[] left = leftHalf(array);


        Mergesorts worker2 = new Mergesorts(right);
        Thread s = new Thread(worker2);
        s.start();

        processCommand(left);

        try {
            s.join();
        } catch (InterruptedException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }

        merge(array, left, right);}

}

Answer 1

在 processCommand() 方法中启动新线程，而不是在 rightHalf() 方法中。如果您有可用的线程，则不要调用 processCommand(right) 行，而是在 right 上构造一个新的 Mergesorts 对象并使用它启动一个线程。不要忘记在线程上调用 join() 以确保它在进行合并之前完成。

为了提高并行性，可以在处理数组的左半部分之前在数组的右半部分启动新线程，这样两者是同时完成的——即将processCommand(left)移到之后执行 processCommand(right) 或启动新线程的块。 join() 调用应该在两部分都完成之后，但在合并之前。

编辑：你越来越近了；要解决您的评论，您需要这样的东西：

private void processCommand(int [] array) {
    if (array.length <= 1)
        {return;}

    int[] left = leftHalf(array);
    int[] right = rightHalf(array);
    Thread rightThread = null;

    if (b <= 5) {
        ++b;
        Mergesorts worker = new Mergesorts(right);
        rightThread = new Thread(worker);
        rightThread.start();
    } else {
        processCommand(right);
    }

    processCommand(left);

    if (null != rightThread) {
        try {
            rightThread.join();
            b--
        } catch (InterruptedException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
            // better error handling would be good
        }
    }

    merge(array, left, right);
}

b 还需要可变的以确保不同的线程可以看到当前有多少线程正在执行。

并发线程合并排序

concurrent Threads Merge Sort

java

concurrency

mergesort

multithreading