java - java中的多线程快速排序

Question

我一直在尝试使用java编写一个多线程快速排序程序。网上有很多使用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

Answer 1

您最大的问题是您在开始新线程后立即加入。这会导致调用线程等待新线程完成。您需要启动想要同时运行的所有线程，然后等待它们全部运行。所以代替:

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 库编写快速排序的教程已发布 here .

另外一点，您过度使用静态方法。它们应该是实例方法。看看here有关何时使用静态方法的详细信息。