使用多線程的Java MergeSort加速

Question

我想使用多線程來實現Mergesort的一個版本。首先，我知道在這裏有十億個線程（給或者帶......），並且我已經閱讀了一些無濟於事的東西！我試圖說明，並行使用線程可以加速進程。然而，我遇到的問題是，我的代碼實際上並沒有顯示和加速，反而相反。

隨着一個線程，我的時間是在成千上萬的。隨着兩個，我的時間增加到幾十萬，然後用4個線程我的時間與7個數字接壤。我最初的想法是玩弄join（）方法，並確保它在正確的位置，並且已經這樣做了，但沒有成功。

任何幫助將不勝感激，一個示例命令行參數是類似的;

java正在工作16 4（4線程）。

對於整個評論缺乏抱歉！

import java.util.*; 

class working 
{ 
    private static int sizeVector; 
    private static int noThreads; 
    static void sort(int[] input) 
    { 
    mergeSort(input, 0, input.length - 1, noThreads); 
    } 

    static void mergeSort(int[] array, int low, int high, int noThreadsUp) 
    { 
    //private int noThreadsUp; 
    if (low < high) 
    { 
     int mid = (low+high)/2; 
     if (noThreadsUp > 1) 
     { 
     NewThread td = new NewThread(array, low, mid, noThreadsUp/2); 
     td.start(); 
     /*try{ 
     td.join(); 
     }catch(Exception e){}*/ 
     mergeSort(array, mid+1, high, noThreadsUp/2); 
       try{ 
     td.join();//UNSURE WHERE THIS SHOULD BE 
     }catch(Exception e){} 
     merge(array, low, mid, high); 

     } 
     else 
     { 
     mergeSort(array, low, mid, noThreadsUp/2); 
     mergeSort(array, mid+1, high, noThreadsUp/2); 
     merge(array, low, mid, high); 
     } 
    } 
    } 

    static void merge(int[] array, int low, int mid, int high) 
    { 
    int[] temp = new int[high - low + 1]; 
    int left = low; 
    int right = mid+1; 
    int k = 0; 
    while (left <= mid && right <= high) 
    { 
     if(array[left] < array[right]) 
     { 
     temp[k] = array[left]; 
     left = left+1; 
     } 
     else 
     { 
     temp[k] = array[right]; 
     right = right + 1; 
     } 
     k = k + 1; 
    } 
    if (left <= mid) 
    { 
     while(left <= mid) 
     { 
     temp[k] = array[left]; 
     left = left + 1; 
     k = k + 1; 
     } 
    } 
    else if (right <= high) 
    { 
     while(right <= high) 
     { 
     temp[k] = array[right]; 
     right = right + 1; 
     k = k + 1; 
     } 
    } 
    for (int m = 0; m < temp.length; m++) 
    { 
     array[low+m] = temp[m]; 

    } 
} 
    static int[] readInputArray() 
    { 

    int[] a = new int[sizeVector]; 
    for (int i = 0; i < sizeVector; i++) 
    { 
     Random generator = new Random(); 
     a[i] = generator.nextInt(); 
    } 
    return a; 
    } 

    static void printArray(int[] array) 
    { 
    for(int i = 0; i<array.length; i++) 
     System.out.println(array[i]); 
    } 

    public static void main(String[] args) 
    { 
    sizeVector = Integer.parseInt(args[0]); 
    noThreads = Integer.parseInt(args[1]); 
    int[] inputArray = readInputArray(); 
    System.out.println("INPUT ARRAY: "); 
    printArray(inputArray); 
    long startTime = System.nanoTime(); 
    sort(inputArray); 
    long endTime = System.nanoTime(); 
    long finalTime = endTime - startTime; 

    System.out.println("SORTED ARRAY: "); 
    printArray(inputArray);  
    System.out.println("Time: " + finalTime); 
    } 

static class NewThread extends Thread 
    { 
    private int low; 
    private int mid; 
    private int[] array; 
    private int noThreadsDown; 
    //private int threads; 
    public NewThread(int[] array, int low, int mid, int noThreadsDown) 
    { 
     this.low = low;//Ensure using the right start 
     this.mid = mid;//Ensure using the right end 
     this.array = array; 
     this.noThreadsDown = noThreadsDown; 
     //this.threads = threads; 
    } 
    public void run() 
    { 

     mergeSort(array, low, mid, noThreadsDown/2); 
     System.out.println(noThreadsDown); 
    } 
    }//End NewThread 
} 

Answer 1

它可能是最好的使用java 7中的RecurssionAcition類，它分爲左右兩部分。

Sum left = new Sum(array, low, mid); 
Sum right = new Sum(array, mid, high); 
left.fork(); 
long rightAns = right.compute(); 
long leftAns = left.join(); 
return leftAns + rightAns; 

Answer 2

這裏有一些代碼有效。

public class TestMergeSort{ 

    public static void main(String[] args){ 

     // Threaded merge sort (and printing) 
     int[] toSort = {191,2,3,5,6,7,5,3,21,3,4}; 
     printArr(toSort); 
     concurrentMergeSort(toSort); 
     printArr(toSort); 
    } 

    public static void concurrentMergeSort(int[] toSort){ 
     int[] tmpArray = new int[toSort.length]; 

     try{ 
      // Start the mergesort 
      ConcurrentMergeSort sort = new ConcurrentMergeSort(toSort, tmpArray, 0, toSort.length - 1); 
      sort.start(); 
      sort.join(); 

     } catch(InterruptedException e){ 
      e.printStackTrace(); 
     } 

    } 

    public static void printArr(int[] a){ 
     for(int i = 0; i < a.length; i++){ 
      System.out.print(a[i] + " ,"); 
     } 
     System.out.println(); 
    } 
} 



public class ConcurrentMerge extends Thread{ 
    private int[] a; 
    private int[] tmpArray; 
    private int leftPos; 
    private int rightPos; 
    private int rightEnd; 

    public ConcurrentMerge(int[] a, int[] tmpArray, int leftPos, int rightPos, int rightEnd){ 
     this.a = a; 
     this.tmpArray = tmpArray; 
     this.leftPos = leftPos; 
     this.rightPos = rightPos; 
     this.rightEnd = rightEnd; 
    } 

    public void run(){ 
     int leftEnd = rightPos - 1; 
     int tmpPos = leftPos; 
     int numElements = rightEnd - leftPos + 1; 

     // Main loop 
     while(leftPos <= leftEnd && rightPos <= rightEnd) 
      if(a[ leftPos ] <= a[ rightPos ]) 
       tmpArray[ tmpPos++ ] = a[ leftPos++ ]; 
      else 
       tmpArray[ tmpPos++ ] = a[ rightPos++ ]; 

     // Copy rest of the left half 
     while(leftPos <= leftEnd) 
      tmpArray[ tmpPos++ ] = a[ leftPos++ ]; 

     // Copy rest of the right half 
     while(rightPos <= rightEnd) 
      tmpArray[ tmpPos++ ] = a[ rightPos++ ]; 

     // Copy tmpArray back 
     for(int i = 0; i < numElements; i++){ 
      a[ rightEnd ] = tmpArray[ rightEnd-- ]; 
     } 
    } 

} 


import java.util.Arrays; 

public class ConcurrentMergeSort extends Thread{ 

    private int[] a; 
    private int[] tmpArray; 
    private int left; 
    private int right; 

    public ConcurrentMergeSort(int[] a, int[] tmpArray, int left, int right){ 
     this.a = a; 
     this.tmpArray = tmpArray; 
     this.left = left; 
     this.right = right; 
    } 

    public void run(){ 
     if(this.left < this.right){ 
      try{ 
       int center = (this.left + this.right)/2; 
       ConcurrentMergeSort p = new ConcurrentMergeSort(this.a, this.tmpArray, this.left, center); 
       ConcurrentMergeSort q = new ConcurrentMergeSort(this.a, this.tmpArray, center + 1, this.right); 
       ConcurrentMerge r = new ConcurrentMerge(this.a, this.tmpArray, this.left, center + 1, this.right); 

       // Sort 
       p.start(); 
       q.start(); 
       p.join(); 
       q.join(); 

       // Merge 
       r.start(); 
       r.join(); 
      } 
      catch(InterruptedException e){ 
       e.printStackTrace(); 
      } 
     } 
    } 

    public int[] getA(){ 
     return this.a; 
    } 

}