查找最大值及在2D陣列座標通過並行處理

Question

鑑於下面的代碼位，其執行一個非常簡單的任務：

for (int i = 0; i < 181; i++) 
{ 
    for (int j = 0; j < 360; j++) 
    { 
     if (Arr[i][j] > Max) 
     { 
      Max = Arr[i][j]; 
      MaxPosition[0] = i;    
      MaxPosition[1] = j; 
     } 
    } 
} 

和條件是使用mutex ES需要更多的時間比離開這個像它是否還有其他可能性在並行循環中做同樣的事情？我可以想到atomic和combinable找到Max的值，但不能獲得它在Arr陣列中的位置。

Answer 1

如果您有X個並行線程，每個線程檢查Arr的小分區，則可以使用X MaxPosition數組和一組X Max值。然後，當並行線程全部完成時，使用MaxPosition陣列中的位置，可以通過一個小循環找出Max陣列中的最終最大值。

---

簡單的例子：

void thread_function(int start_x, int end_x, 
        std::vector<std::vector<int>> const& arr, 
        int& max_value, 
        std::pair<int, int>& max_position) 
{ 
    max_value = std::numeric_limits<int>::min(); 

    for (int x = start_x; x < end_x; ++x) 
    { 
     for (int y = 0; y < 360; ++y) 
     { 
      if (arr[x][y] > max_value) 
      { 
       max_value = arr[x][y]; 
       max_positions.first = x; 
       max_positions.second = y; 
      } 
     } 
    } 
} 

現在如何使用它

std::vector<std::vector<int>> arr; // The array of numbers, filled with values somehow... 

constexpr size_t number_of_threads = 4; 

std::vector<int> max_values(number_of_threads); 
std::vector<std::pair<int, int>> max_positions(number_of_threads); 

// Initial values 
int start_x = 0; 
int end_x = arr.size()/number_of_threads; 

std::vector<std::thread> threads; 
for (int i = 0; i < number_of_threads; ++i) 
{ 
    threads.emplace_back(thread_function, 
         start_x, start_y, std::cref(arr), 
         std::ref(max_values[i]), 
         std::ref(max_positions[i])); 
} 

// Wait for threads to finish 
for (int i = 0; i < number_of_threads; ++i) 
{ 
    threads[i].join(); 
} 

// Now max_values contains the max value for each thread 
// and max_positions contains the positions for that value from each thread 

// Collate the data 
auto iter_pos = std::max_element(begin(max_values), end(max_values)); 

int max_value = *iter_pos; 
std::pair<int, int> max_position = max_positions[std::distance(begin(max_values), iter_pos)]; 

std::cout << "The max value is " << max_value << ", and it is found as position <" << max_position.first << ',' << max_position.second << ">\n"; 

注：

上述代碼要求中的元素的數量「第一」迪大小可以由number_of_threads平分。例如180可以工作，但不是181。我會把它作爲一個練習給讀者來解決這個問題。

有關所用類和函數的參考，請參閱this superb online C++ reference。