並行雙向選擇排序

Question

我編寫了代碼來並行執行雙向選擇排序。我使用了c＃和parallel.invoke函數。並行調用2個循環，一個尋找最小值，一個尋找最大值。然而，它不排序。我想知道是這個問題，因爲這種類型的處理不能並行處理，因爲每個循環都依賴於另一個循環中存在的數據嗎？或者是我的代碼有什麼問題嗎？

Parallel.Invoke(
      () => 
       {       
        for (int i=0; i < array.Length/2; i++) 
        { 
         int m; 
         int min = i; 
         for (m = i + 1; m < array.Length - 1; m++) 
          if (array[m] < array[min]) 
           min = m; 
         //swap 
         int temp = array[min]; 
         array[min] = array[m]; 
         array[m] = temp; 
        } 
       }, 
       () => 
        { 
         for (int m = 0; m < array.Length/2; m++) 
         { 
          int length = array.Length - 1; 
          int max = length - m; 
          int k; 
          for (k = length--; k > 0; k--) 
           if (array[k] > array[max]) 
            max = k; 
          //swap 
          int temp = array[max]; 
          array[max] = array[k]; 
          array[k] = temp; 
         } 
       }); 

Answer 1

我認爲，如果你搜索相同的循環內的最小和最大的1個線程更容易：（java的代碼，但我相信你會明白一個道理）

int minimum, maximum; 
    int k = size(); 
    for(int i = 0; i < size(); ++i) 
    { 
     --k; 
     minimum = i; 
     maximum = k; 
     if(k - i <= 0) 
      break; 
     for(int j = i; j <= k; ++j) 
     { 
      if(greaterThan(minimum, j)) 
       minimum = j; 
      if(lessThan(maximum, j)) 
       maximum = j; 
     } 

     if(minimum != i) 
     { 
      swap(minimum, i); 
      if(maximum == i) 
       maximum = minimum; 
     } 
     if(maximum != k) 
      swap(maximum, k); 
    } 

問題與您的代碼是這樣的：

之所以這樣說，是陣列：

[5,4，3，2，1]

迭代0：第一個線程將找到的最小元素穿上指數0
第一個線程發現在指數4
迭代0的最小元素：第二個線程會發現最大的元素穿上指數4
的第二個線程找到索引爲0的最大元素

您已經看到這樣做不會很好，因爲兩個線程都會在索引0和4之間執行交換，從而導致與現在相同的情況。

另一個問題是，如果你的第一個線程從m - > array.length - 1循環。如果在同一時間線程2從索引移動最小元素（它不需要，因爲它搜索最大值） k通過交換到「最大」。索引「max」爲<「m」。這意味着第一個線程永遠不會找到下一個最小值，因爲它在它的位置之前移動了。

編輯：經過考慮，我不認爲有可能實現一個簡單的選擇排序並行版本。我第一次推薦的版本確實不會工作，因爲算法每次都找到相同的最小值，因爲它沒有改變輸入數組。

什麼是可能的是隻對數組的前半部分執行選擇排序（只允許它在該半部分中找到最小值），而後半部分是針對第二個線程。然後最後你可以用mergesort-algorithm合併​​兩個半部分。

這樣你總是可以使用2個以上的線程;例如說「線程」數量的線程。每個負責輸入數組的N/p部分，其中「N」是輸入數據。最後，您只需將每個部分與mergesort算法合併即可。我從來沒有實現它，所以我不能說它是否有效，但我認爲會有更好的算法來並行化（像mergesort本身）。 PS：關於上面貼出的代碼。我以爲一切似乎除了這部分相當簡單：

  if(maximum == i) 
       maximum = minimum; 

這是對付這樣的情況：
。 。 。一世 。 。 。 k
[1，4，3，1，5]

所以i = 1和k = 3（指數）。

該算法會發現：
最大=索引1個
最小=指數3

與索引的一個I，形勢的變化這樣交換的最小值之後：
。 。 。一世 。 。 。 k
[1，3，4，5]

表示實際從索引「i」移動到索引「minimum」的最大值（整數4）。如果我們執行交換（最大值，k），那麼結果會很糟糕。這就是爲什麼我們需要更新最大元素的索引，如果它位於索引i。