java中的多線程quicksort

Question

我一直在嘗試使用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 

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

雖然，在defaut設置爲可用的處理器的數量，除非你有一個理由去改變它，那就不要。

有關如何使用Java Fork/Join庫編寫快速排檔的教程可用here。

而在另一點上，您正在過度使用static方法。他們應該是實例方法。有關何時使用靜態方法的詳細信息，請查看here。