多线程

Question

我试图在Java中创建一个并行快速排序,我认为这是一个天真的(因为我还没有研究过接口执行器等)

所有线程完成后我需要一种打印排序数组的方法.但是我不知道我将提前有多少线程...所以我这样做的方式是每次递归等待使用join()方法..所以调用的第一个连接方法必须等到所有其他线程都完成..对吗？

这样当我在main()(打印数组)中执行我的最后两行时,我可以确定我的所有线程都已完成...

所以我有两个问题..

1. 这是一个并行运行的多线程程序,对吧？或者我是否犯了一些错误,它实际上是以线性的方式线程运行？

2. 我是否正确使用我在main方法中显示已排序数组的解决方案？

这是我的代码:

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> array = new ArrayList();
        //please assume that I have invoked the input for the array from the user 
        QuickSortWithThreads obj = new QuickSortWithThreads(array,0 ,array.size()-1 );
        for(int i = 0; i < array.size(); i++)
            System.out.println(array.get(i));
    }
}

public class QuickSortWithThreads {
    public QuickSortWithThreads(ArrayList <Integer> arr, int left, int right){  
        quicksort(arr, left, right);
    }

    static void  quicksort(ArrayList <Integer> arr, int left, int right)  {
        int pivot;

        if(left<right){
            pivot = partition(arr, left, right);    
            QuickSortThread threadLeftSide = new QuickSortThread(arr, pivot + 1, right);
            threadLeftSide.start();  
            quicksort(arr, left, pivot - 1);
            try {
                threadLeftSide.join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }           
        }
    }

    static  int partition(ArrayList<Integer> arr, int left, int right)  {
        int pivot = arr.get(right);
        int i = left -1;
        for( int j = left; j <= right - 1; j++) {
            if (arr.get(j) <= pivot){
                i = i + 1;
                exchange(arr, i, j);
            }
        }
        exchange(arr, i + 1, right);
        return i + 1;
    }
    static void exchange(ArrayList<Integer> arr, int i, int j) {
        int swap = arr.get(i);
        arr.set(i, arr.get(j)); 
        arr.set(j, swap);
    }

    private static class QuickSortThread extends Thread {
        int right;
        int left;
        ArrayList<Integer> refArray; 

        public QuickSortThread(ArrayList<Integer> array, int left, int right) {
            this.right = right;
            this.left = left;
            refArray = new ArrayList<Integer>();
            refArray = array;   
        }

        public void run() {
            quicksort(refArray, left, right);
        }
    }
}

Answer 1

一般意见

\n\n

是的，您的代码是并行运行的。而且打印出来的结果看起来也没什么问题。

\n\n

通过深度限制线程数量

\n\n

一个问题是您创建了大量线程：在最低级别，您将拥有大约与列表元素一样多的线程。并且您不会捕获由此产生的异常，因此您不会（在主线程中）知道这没有按预期工作。

\n\n

您可能应该限制生成新线程的级别数。一旦你通过了 3 个级别，你将拥有大约 2 ³ =8 个线程，这应该足以让大多数合理的机器上的所有核心都忙碌起来。然后，您可以继续进行其余的计算，而无需分支更多线程。branching您可以通过向您的方法传递一个附加参数来做到这一点quicksort。3在构造函数的调用中将其设置为QuickSortWithThreads，并在每次调用时递减它。一旦计数达到 就不要分支0。这将为您提供以下调用：

\n\n

quicksort(3, \xe2\x80\xa6)\n  quicksort(2, \xe2\x80\xa6)\n    quicksort(1, \xe2\x80\xa6)\n      quicksort(0, \xe2\x80\xa6)\n      quicksort(0, \xe2\x80\xa6)\n    quicksort(1, \xe2\x80\xa6)\n      quicksort(0, \xe2\x80\xa6)\n      quicksort(0, \xe2\x80\xa6)\n  quicksort(2, \xe2\x80\xa6)\n    quicksort(1, \xe2\x80\xa6)\n      quicksort(0, \xe2\x80\xa6)\n      quicksort(0, \xe2\x80\xa6)\n    quicksort(1, \xe2\x80\xa6)\n      quicksort(0, \xe2\x80\xa6)\n      quicksort(0, \xe2\x80\xa6)\n

\n\n

由于每个非叶调用与其子级之一共享一个线程，因此您可以从上面的叶数中扣除最多 8 个线程。

\n\n

通过执行器限制线程数量

\n\n

作为限制线程数量的自制方法的替代方法，您当然可以使用Executor您提到的接口来执行此操作。您可以创建ThreadPoolExecutor来管理您的线程，并将每个递归调用作为 的实例传递Runnable（这可能看起来类似于您的QuickSortThread）。这种方法的一个主要问题是检测终止。特别是如果您想在发生错误时避免死锁。因此，最好使用 aForkJoinTask来代替，因为在这种情况下，您可以让每个任务等待其另一个子任务的结束，这与您编写的非常相似，并且您仍然可以限制关联的ForkJoinPool. 您的实际实现最好使用RecursiveAction，一个专业化ForkJoinTask，文档中包含一个与您的场景非常相似的示例。

\n