マルチスレッドクイックソート（Java）

Question

Javaでクイックソートをマルチスレッド化できますか？

私は次の問題があります： クイックソートの作業時間は、スレッドが2つか3つのクイックソートよりも少なくなっています。私が間違ったことは？

私は、労働者のために次のコードを書いた：

public class QuickSortWorker extends Thread { 

    private int workerId; 
    private double[] array; 
    private int low; 
    private int high; 

    public QuickSortWorker(double[] array, int low, int high) { 
     this.array = array; 
     this.low = low; 
     this.high = high; 
     this.workerId = WorkerManager.workersCount++; 
    } 

    public void run() { 
     System.out.println("Run new worker. ID: " + this.workerId); 
     System.out.println("Worker status: " + this.isAlive()); 

     this.quickSort(this.array, this.low, this.high); 

     System.out.println("Stop worker. ID: " + this.workerId); 
     WorkerManager.workersCount--; 
    } 

    protected void quickSort(double[] array, int low, int high) { 
     /*int i = low, j = high; 
     double pivot = array[low + (high - low)/2]; 

     while (i <= j) { 
      while (array[i] < pivot) { 
       i++; 
      } 

      while (array[j] > pivot) { 
       j--; 
      } 

      if (i <= j) { 
       this.exchange(array, i, j); 
       i++; 
       j--; 
      } 
     } 

     if (low < j) { 
      quickSort(array, low, j); 
     } 

     if (i < high) { 
      sort(array, i, high); 
     }*/ 

     int len = high - low + 1; 
     if (len <= 1) { 
      return; 
     } 

     double pivot = array[low + (high - low)/2]; 
     exchange(array, low + (high - low)/2, high); 

     int storeIndex = low; 
     for (int i = low; i < high; i++) { 
      if (array[i] < pivot) { 
       exchange(array, i, storeIndex); 
       storeIndex++; 
      } 
     } 

     exchange(array, storeIndex, high); 

     sort(array, low, storeIndex - 1); 
     quickSort(array, storeIndex + 1, high); 
    } 

    protected void exchange(double[] array, int i, int j) { 
     double tmp = array[i]; 
     array[i] = array[j]; 
     array[j] = tmp; 
    } 

    protected void sort(double[] array, int low, int high) { 
     if (WorkerManager.workersCount < WorkerManager.WORKERS_LIMIT) { 
      try { 
       WorkerManager.createWorker(array, low, high); 
      } catch (InterruptedException e) { 
       System.out.println("QuickSort worker was down. Reason: " + e.getMessage() + "\n"); 
       e.printStackTrace(); 
      } 
     } else { 
      this.quickSort(array, low, high); 
     } 
    } 
} 

そしてWorkerManagerについては、次のコード：

public class WorkerManager { 

    public static final int MAX_WORKER_COUNT = 10; 
    public static int WORKERS_LIMIT = 0; 
    public static int workersCount = 0; 

    private double _startTime = 0; 
    private double _stopTime = 0; 
    private double _workTime = 0; 

    public void createTask(double[] data, int workerCount) throws WorkerManagerException { 
     if (workerCount > MAX_WORKER_COUNT) { 
      throw new WorkerManagerException("Worker count cant be more than " + MAX_WORKER_COUNT); 
     } 

     try { 
      WORKERS_LIMIT = workerCount; 
      this.startTimer(); 
      WorkerManager.createWorker(data, 0, data.length - 1); 
      this.stopTimer(); 

      System.out.println("\nWorktime: " + this.getWorkTime() + " milliseconds."); 
     } catch (InterruptedException e) { 
      System.out.println("QuickSort worker was down. Reason: " + e.getMessage() + "\n"); 
      e.printStackTrace(); 
     } 
    } 

    public static void createWorker(double[] array, int low, int high) throws InterruptedException { 
     QuickSortWorker worker = new QuickSortWorker(array, low, high); 
     worker.start(); 
     worker.join(); 
    } 

    protected void startTimer() { 
     this._startTime = System.currentTimeMillis(); 
    } 

    protected void stopTimer() { 
     this._stopTime = System.currentTimeMillis(); 
    } 

    private void setWorkTime() { 
     this._workTime = (this._startTime == 0) 
       ? 0 
       : this._stopTime - this._startTime; 
    } 

    private double getWorkTime() { 
     if (this._workTime == 0) { 
      this.setWorkTime(); 
     } 
     return this._workTime; 
    } 
} 

Answer 1

あなたはメインスレッドで労働者を作成し、一度あなたがメインスレッドをブロックする（参加）と待って開始しました作業者が完了するために：

QuickSortWorker worker = new QuickSortWorker(array, low, high); 
worker.start(); 
worker.join(); 

これはあなたに望ましい並列性を与えません。ある時点では、1つのスレッドしか動作しないため、パフォーマンスが向上しません。