我一直在尝试使用Java编写多线程quicksort程序。有网上使用大量的样本ThreadPool，CountDownLatch等等。
但是，我只想使用一个计数来保持创建线程数的计数。
该程序背后的逻辑是：
1. The main thread calls the parallel quicksort method
2. The method partitions the array and check for the number of current threads
3. Spawn new threads for next step using the same parallel method
4. Or use the single normal quicksort method
我一直在使用并行方式来获得性能，但还不是很多。有人可以帮助我改善密码吗？
这是我所做的：
class Quicksort extends Thread {
private int arr[];
private int low,high;
public static int numThreads = Runtime.getRuntime().availableProcessors();
public static int count = 0;
public Quicksort(int[] arr, int low, int high){
this.arr = arr;
this.low = low;
this.high = high;
}
public void run(){
parallelQuicksort(arr,low,high);
}
public static void quicksort(int[] arr, int low, int high){
if (high>low){
int i = partition(arr,low,high);
quicksort(arr,low,i-1);
quicksort(arr,i+1,high);
}
}
public static void parallelQuicksort(int[] arr, int low, int high){
if (high>low){
int i = partition(arr,low,high);
if (count < numThreads){
count++;
Quicksort quicksort = new Quicksort(arr, low, i-1);
quicksort.start();
try{
quicksort.join();
}
catch (InterruptedException e){}
}
else{
quicksort(arr,low,i-1);
}
if (count < numThreads){
count++;
Quicksort quicksort = new Quicksort(arr, i+1, high);
quicksort.start();
try{
quicksort.join();
}
catch (InterruptedException e){}
}
else{
quicksort(arr,i+1,high);
}
}
}
public static int partition(int[] A, int l,int r)
public static void swap(int[] A,int i,int j)
public static int median(int[] A,int l,int mid,int r)
}
主班：
public class Test{
public static void main(String[] args) {
//generate random array of size 1000000
long start = System.currentTimeMillis();
Quicksort.quicksort(arr,0,arr.length -1);
System.out.println("Single array sorted in "+(System.currentTimeMillis()-start)+" ms");
start = System.currentTimeMillis();
Quicksort.parallelQuicksort(arr2,0,arr.length -1);
System.out.println("Threaded array sorted in "+(System.currentTimeMillis()-start)+" ms");
}
}
我得到的示例输出：
Single array sorted in 393 ms
Threaded array sorted in 367 ms
Single array sorted in 325 ms
Threaded array sorted in 305 ms
Single array sorted in 344 ms
Threaded array sorted in 320 ms
您最大的问题是，您在启动新线程后立即加入。这将导致调用线程等待新线程完成。您需要启动打算同时运行的所有线程，然后在它们全部运行后等待它们。因此，而不是：
Quicksort quicksort = new Quicksort(arr, low, i-1);
quicksort.start(); // Start new thread.
quickstart.join(); // Wait for it to run before moving on
Quicksort quicksort = new Quicksort(arr, i+1, high);
quickstart.start(); // Start second thread (after first has finished)
quickstart.join(); // Wait for second thread.
您需要执行以下操作：
Quicksort low = new Quicksort(arr, low, i-1);
low.start(); // Start first thread
Quicksort high = new Quicksort(arr, i+1, high);
high.start(); // While first thread is running, start second.
low.join(); // Wait for first thread.
high.join(); // Immediately returns if already finished
我认为您打算编写上面的代码，但效率仍然很低。在等待其他线程完成时，它不会将任何工作分配给主线程。
除了这些问题外，编写线程的方式也不会减少计数。相反，主线程只会处理更多工作。这意味着您没有正确分配负载。
正如@Sergei在评论中所说，您可能希望研究Fork / Join框架来管理线程。Java中的Fork / Join允许您将工作分解为多个任务，并将它们排队，以便将它们分配给备用线程。如果要限制正在使用的线程数，可以通过在创建时设置所需的并行度来实现ForkJoinPool。
ForkJoinPool pool = new ForkJoinPool(numThreads);
虽然，默认值设置为可用处理器的数量，并且除非您有理由对其进行更改，否则不要这样做。
此处提供了有关如何使用Java Fork / Join库编写quicksort的教程。
另一方面，您正在过度使用static方法。它们应该是实例方法。请在此处查看有关何时使用静态方法的详细信息。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句