並行泡泡分類性能

Question

我的目標是實現排序算法泡泡排序使用線程，程序似乎運行良好。然而，這些表現太糟糕了，所以我想知道如何讓代碼運行得更快，爲什麼它運行得非常糟糕。

的代碼是基於如下算法：

並行的冒泡排序（A） - 算法

> 1.For k = 0 to n-2 
> 2.If k is even then 
> 3. for i = 0 to (n/2)-1 do in parallel 
> 4.  if A[2i] > A[2i+1] then 
> 5.  Exchange A[2i] <-> A[2i+1] 
> 6.Else 
> 7. for i = 0 to (n/2)-2 do in parallel 
> 8. if A[2i+1] > A[2i+2] then 
> 9.  Exchange A[2i+1] <-> A[2i+2] 
> 10.Next k 

---

public static void sort(){ 
    int n = input.length; //length of the array to sort 
    Thread[] thr1 = new Thread[(int)n/2]; 
    Thread[] thr2 = new Thread[(int)n/2]; 
    int count1; 
    int count2; 

    for(int i = 0; i<n-1;i++){ 
     if(i % 2 == 0){ // i even 
     count1 = 0; 

     for(int j = 0; j<n/2; j++){ 
      final int tmp = j; 
      count1++; 
      thr1[tmp] = new Thread(){ 
       public void run(){ 
        if (input[2*tmp]>input[2*tmp+1]) 
         swap(2*tmp,2*tmp+1); 
       } 
      }; 
      thr1[tmp].start(); 
     } 
     //waiting for threads to finish 
     for(int m = 0; m<count1; m++){ 
      try { 
       thr1[m].join(); 
      } catch (InterruptedException e) { 
       e.printStackTrace(); 
      }} 
     } 
     else{ // i odd 
     count2 = 0; 
     for(int k = 0; k<n/2-1;k++){ 
      final int tmp = k; 
      count2++; 
      thr2[tmp] = new Thread(){ 
       public void run(){ 
        if (input[2*tmp+1]>input[2*tmp+2]) 
         swap(2*tmp+1,2*tmp+2); 
       } 
      }; 
      thr2[tmp].start(); 
     } 
     // Waiting for threads to finish 
     for(int m = 0; m<count2; m++){ 
      try { 
       thr2[m].join(); 
      } catch (InterruptedException e) { 
       e.printStackTrace(); 
      } 
     }}   
    } 
} 

編輯：

這裏是新版本不幸的是，正如預測的那樣，ExecutorService仍然運行得非常糟糕，比順序版本慢。

public static void sort(){ 
    int n = input.length; //length of the array to sort 
    ExecutorService executor = Executors.newFixedThreadPool(8); 

    for(int i = 0; i<n-1;i++){ 
     if(i % 2 == 0){ // i even 

     for(int j = 0; j<n/2; j++){ 
      final int tmp = j; 
      executor.submit(new Runnable(){ 
       public void run(){ 
        if (input[2*tmp]>input[2*tmp+1]) 
         swap(2*tmp,2*tmp+1);} 
      });} 
     } 

     else{ // i odd 
     for(int k = 0; k<n/2-1;k++){ 
      final int tmp = k; 
      executor.submit(new Runnable(){ 
       public void run(){ 
        if (input[2*tmp+1]>input[2*tmp+2]) 
         swap(2*tmp+1,2*tmp+2);} 
      });} 
     }  
    } 
executor.shutdown(); 
try { 
    executor.awaitTermination(1, TimeUnit.DAYS); 
} catch (InterruptedException e) { 
    e.printStackTrace();} 
} 

Answer 1

它之所以這麼慢是因爲調用new Thread()是非常昂貴的。它需要數千倍的時鐘週期才能啓動另一個線程來完成部分排序，而不是完成原始線程中的所有排序。

此外，即使new Thread()並不昂貴，您仍然沒有看到太多（或任何）的性能改進，因爲排序是一個內存綁定操作，並且您最有可能試圖在單CPU上運行它，多核系統，但CPU只有一個地址總線和一個數據總線，所以核心將主要等待對方放開數據總線。