c++ - 使用并行线程查找所有加起来等于给定数字的组合

Question

问题是找到一种方法来达到与下面代码中已经达到的结果相同的结果，但要使用自定义数量的线程，使用临界区和信号量，以便并行化下面的代码

我试图并行化代码的递归部分，但我没有想出任何合理的解决方案

代码可以在这里并行化，信号量可以用来并行化代码，但不清楚哪些部分可以并行运行

---

已经运行的解决方案:

找出所有组合的C++程序加起来等于给定数的正数

#include <iostream> 
using namespace std; 

//    arr - array to store the combination 
//    index - next location in array 
//    num - given number 
//    reducedNum - reduced number 

void findCombinationsUtil(int arr[], int index, 
                       int num, int reducedNum) 
{ 
    // Base condition 
    if (reducedNum < 0) 
        return; 

    // If combination is found, print it 
    if (reducedNum == 0) 
    { 
        for (int i = 0; i < index; i++) 
            cout << arr[i] << " "; 
        cout << endl; 
        return; 
    } 

    // Find the previous number stored in arr[] 
    // It helps in maintaining increasing order 
    int prev = (index == 0)? 1 : arr[index-1]; 

    // note loop starts from previous number 
    // i.e. at array location index - 1 
    for (int k = prev; k <= num ; k++) 
    { 
        // next element of array is k 
        arr[index] = k; 

        // call recursively with reduced number 
        findCombinationsUtil(arr, index + 1, num, 
                                 reducedNum - k); 
    } 
} 

找出所有组合的函数加起来等于给定数字的正数。它使用 findCombinationsUtil()

void findCombinations(int n) 
{ 
    // array to store the combinations 
    // It can contain max n elements 
    int arr[n]; 

    //find all combinations 
    findCombinationsUtil(arr, 0, n, n); 
} 

驱动代码

int main() 
{ 
    int n = 5; 
    findCombinations(n); 
    return 0; 
} 

来源:https://www.geeksforgeeks.org/find-all-combinations-that-adds-upto-given-number-2/

Answer 1

我引用另一个答案的一句话:

I'll take the advice route. Before trying to make your program faster using threads, you first want to make it faster in the single threaded case.

在你的具体问题中，我认为并行化函数有点困难。例如，你可以让每个线程在原始数组的一个子数组中找到数字的组合，但是不同子数组中的组合呢？显然，并行化这个问题是有限制的，因为每个数字都依赖于其他每个数字。您可以在进行并行计算之前预先缓存总和，但如果您想要数字形成组合，它就没有多大帮助。

有关详细信息，请参阅这些链接。

https://www.codeproject.com/Articles/1247260/Cplusplus-Simple-Permutation-and-Combination-Paral

Parallelizing recursive function using OpenMP in C++