C++ Intel TBB 和 Microsoft PPL，如何在并行循环中使用 next_permutation？

Question

我安装了 Visual Studio 2012 和 Intel parallel studio 2013，所以我有 Intel TBB。

假设我有以下代码:

const int cardsCount = 12; // will be READ by all threads
// the required number of cards of each colour to complete its set:
// NOTE that the required number of cards of each colour is not the same as the total number of cards of this colour available
int required[] = {2,3,4}; // will be READ by all threads
Card cards[cardsCount]; // will be READ by all threads
int cardsIndices[cardsCount];// this will be permuted, permutations need to be split among threads !

// set "cards" to 4 cards of each colour (3 colours total = 12 cards)
// set cardsIndices to {0,1,2,3...,11}

 // this variable will be written to by all threads, maybe have one for each thread and combine them later?? or can I use concurrent_vector<int> instead !?
int logColours[] = {0,0,0};

int permutationsCount = fact(cardsCount);

for (int pNum=0; pNum<permutationsCount; pNum++) // I want to make this loop parallel !!
{
    int countColours[3] = {0,0,0}; // local loop variable, no problem with multithreading
    for (int i=0; i<cardsCount; i++)
    {
        Card c = cards[cardsIndices[i]]; // accessed "cards"

        countColours[c.Colour]++; // local loop variable, np.
            // we got the required number of cards of this colour to complete it
        if (countColours[c.Colour] == required[c.Colour]) // read global variable "required" !
        {
                    // log that we completed this colour and go to next permutation
            logColours[c.Colour] ++; // should I use a concurrent_vector<int> for this shared variable?
            break;
        }
    }
    std::next_permutation(cardsIndices, cardsIndices+cardsCount); // !! this is my main issue
}

我正在计算的是，如果我们从可用的卡片中随机挑选，我们将完成多少次颜色，这是通过遍历每个可能的排列并按顺序挑选来完成的，当颜色“完成”时，我们打破并开始到下一个排列。请注意，每种颜色我们有 4 张卡片，但完成每种颜色所需的卡片数量是 {2,3,4}(红色、绿色、蓝色)。 2 张红色卡片足以完成红色，而我们有 4 张可用，因此红色比蓝色更有可能完成，蓝色需要全部 4 张卡片都被选中。

我想让这个 for 循环并行，但我的主要问题是如何处理“卡片”排列？你这里有大约 5 亿个排列(12!)，如果我有 4 个线程，我如何将它分成 4 个不同的部分并让每个线程通过它们中的每一个？

如果我不知道机器的核心数，而我希望程序自动选择正确的并发线程数怎么办？肯定有办法使用 Intel 或 Microsoft 工具来做到这一点？

这是我的卡片结构以防万一:

struct Card
{
public:
    int Colour;
    int Symbol;
}

Answer 1

让N = cardsNumber , M = required[0] * required[1] * ... * required[maxColor] .然后，实际上，您的问题可以在 O(N * M) 时间内轻松解决。在您的情况下，即 12 * 2 * 3 * 4 = 288操作。 :)

执行此操作的一种可能方法是使用递归关系。考虑一个函数 logColours f(n, required) .让n是当前已经考虑过的牌的数量； required是您示例中的一个 vector 。函数返回 vector 中的答案 logColours .您对f(12, {2,3,4})感兴趣.函数内部的简短循环计算 f可以这样写:

std::vector<int> f(int n, std::vector<int> require) {
    if (cache[n].count(require)) {
        // we have already calculated function with same arguments, do not recalculate it again
        return cache[n][require];
    }

    std::vector<int> logColours(maxColor, 0); // maxColor = 3 in your example

    for (int putColor=0; putColor<maxColor; ++putColor) {
         if (/* there is still at least one card with color 'putColor'*/) {
              // put a card of color 'putColor' on place 'n'
              if (require[putColor] == 1) {
                  // means we've reached needed amount of cards of color 'putColor'
                  ++logColours[putColor];
              } else {
                  --require[putColor];
                  std::vector<int> logColoursRec = f(n+1, require);
                  ++require[putColor];
                  // merge child array into your own.
                  for (int i=0; i<maxColor; ++i)
                      logColours[i] += logColoursRec[i];
              }
          }
     }

     // store logColours in a cache corresponding to this function arguments
     cache[n][required] = std::move(logColours);
     return cache[n][required];
 }

缓存可以实现为 std::unordered_map<int, std::unordered_map<std::vector<int>, std::vector<int>>> .

一旦您理解了主要思想，您将能够以更高效的代码来实现它。