5

我试图在 Java 中创建一个并行快速排序，我认为这是一个幼稚的（因为我还没有研究过 Interface Executor 等）

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

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

所以我有两个问题..

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

  2. 我在主要方法中显示排序数组的解决方案是否正确？

这是我的代码：

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);
        }
    }
}
4

3 回答 3

3

如果我们知道线程的总数，我们可以使用用线程数初始化的CountDownLatch 。但是由于我们不知道线程的数量，我们需要一个扩展的 CountDownLatch 允许在创建后增加计数器。不幸的是，我们不能仅仅扩展 CountDownLatch 类，因为底层计数器是私有的。一种方法是复制 CountDownLatch 的原始代码以访问底层计数器。不太冗长的方法是扩展Semaphore以访问该reducePermits方法，因为它在Reduceable Semaphore中完成。原则上，CountDownLatch 和 Semaphore 是类似的工具，但对内部计数器的解释不同：第一个计数否决，后者计数允许。

整个想法是在创建或启动线程时减少许可数量，并在方法结束时释放许可run()。初始许可数为 1，因此如果没有线程启动，则主程序自由结束。请注意，在方法开始时减少许可数量run()为时已晚。

要获得真正好的工作代码，您还需要使用具有固定数量线程的线程池，并对小型数组进行串行排序。

于 2013-05-08T11:04:43.470 回答
1

线程的行为方式取决于您的硬件。在单核 CPU 和无超线程的情况下，计算机在一个循环中逐行逐线程处理 1 个线程。如果您有超线程和/或多个内核，它们可以同时运行多条线路。对 examplethread.join() 的调用使调用线程等待直到 examplethread 完成其工作（通过从 run() 方法返回）。如果您创建一个线程并稍后调用 2 行加入，您将拥有非常类似于使其成为单线程的多线程同步任务。

我建议创建一个 ArrayList 并将每个线程添加到列表中，在所有线程都设置好并且工作之后，你调用一个

for(Thread t : mythreadlist) {
    try {
        t.join();
    } catch (InterruptedException e) { System.err.println("Interrupted Thread"); } 
}

让您的应用程序等待所有线程退出。

编辑：

// [...]
public class QuickSortWithThreads {
    ArrayList<QuickSortThread> threads = new ArrayList<>();
public QuickSortWithThreads(ArrayList <Integer> arr, int left, int right){  
    quicksort(arr, left, right); // Pretty much make your threads start their jobs
    for(Thread t : threads) { // Then wait them to leave.
        try {
            t.join();
        } catch (InterruptedException e) { System.err.println("Interrupted Thread"); } 
    } 
}
// [...]
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();
        threads.add(threadLeftSide());
        // 
        quicksort(arr, left, pivot - 1);  
    }
}
// [...]
于 2013-05-08T11:34:47.427 回答
1

一般意见

是的，您的代码并行运行。结果打印看起来也很好。

通过深度限制线程数

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

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

quicksort(3, …)
  quicksort(2, …)
    quicksort(1, …)
      quicksort(0, …)
      quicksort(0, …)
    quicksort(1, …)
      quicksort(0, …)
      quicksort(0, …)
  quicksort(2, …)
    quicksort(1, …)
      quicksort(0, …)
      quicksort(0, …)
    quicksort(1, …)
      quicksort(0, …)
      quicksort(0, …)

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

通过 Executors 限制线程数

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

于 2013-05-08T10:06:22.067 回答