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

主要class：

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

你在这里最大的问题是你在开始一个新话题后就加入了。这会导致调用线程等待新线程完成。您需要同时启动所有您打算运行的线程，然后等待它们全部运行ning。所以代替：

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。

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

java 中的多线程快速排序

multithreaded quicksort in java

java

multithreading

quicksort