C++: 简单的排列和组合并行化
5.00/5 (6投票s)
简单的排列和组合并行化示例
目录
主要动机
我的Github仓库，Boost CPU上的并发排列和组合，自2017年1月以来一直存在。然而，下载量几乎为零，而我较早的单线程next_combination却有大量的下载。因此，我认为这一定是代码的使用被认为过于复杂。本文的目的是展示一个非常简单的，尽管效率低下的多线程示例，为用户提供指导。一旦他们理解了本文中的示例，用户应该能够相对容易地提出一个高效的多线程代码。对于每个排列和组合部分，我将从一个单线程示例开始，然后是一个多线程示例。
单线程排列
首先，我将向您展示在单线程场景中使用next_permutation的示例。while循环显示std_permuted，直到next_permutation返回false，当检测到std_permuted以降序排列时，即“54321”。
void usage_of_next_perm()
{
std::string std_permuted = "12345";
do
{
std::cout << std_permuted << std::endl;
} while (std::next_permutation(std_permuted.begin(), std_permuted.end()));
}
输出如下
12345
12354
12435
12453
12534
12543
...
54123
54132
54213
54231
54312
54321
多线程排列
接下来，我将向您展示如何在多线程场景中查找排列。在包含5个元素的集合中总共有120种不同的排列。在我的示例中，我们将使用4个线程，这意味着每个线程将找到120/4=30个排列。说实话，每个线程将找到30-1=29个排列，因为第一个排列已经在主线程中通过find_perm_by_idx计算出来并传递给线程。为了使讨论简单，我们假设每个线程计算30个排列。第一个线程找到第0到29个排列，而第二个线程从第30个到第59个排列开始，第三个线程从第60个到第89个开始，依此类推。从第二个线程和第三个线程分别从第30个和第60个排列开始，我们需要利用find_perm_by_idx来查找第30个和第60个排列及其索引，我们将使用next_permutation找到其余的排列。从技术上讲，可以通过提供从0到119的索引来使用find_perm_by_idx找到所有排列，但这根本不可行，因为find_perm_by_idx比next_permutation慢得多。作为警告，index_to_find必须是足够大的类型才能存储阶乘(n)。例如，您只想找到前10个排列，index_to_find类型可以存储0到10，但是如果它不能存储阶乘(n)，find_perm_by_idx将无法正确生成排列。这也适用于find_comb_by_idx。如果您的最大整数类型不够大，您可以考虑使用Boost Multiprecision Integer。并且vector_type可以是支持push_back()和size()方法的任何集合类型，例如std::string。您可以看到我在示例中使用std::string。
我在启动下一个线程之前加入了我的线程，因为all_results与所有线程共享，并且没有使用锁保护，因此不是线程安全的。这只是一个关于如何find_perm_by_idx的简单示例。您的工作是尝试找出如何在工作线程中调用find_perm_by_idx。
template<typename int_type, typename vector_type>
vector_type find_perm_by_idx(int_type index_to_find,
vector_type& original_vector);
void usage_of_perm_by_idx()
{
uint64_t index_to_find = 0;
std::string original_text = "12345";
std::string std_permuted = "12345";
std::vector<std::string> all_results;
size_t repeat_times = 30;
for (size_t i=0; i<4; ++i)
{
std::string permuted = concurrent_perm::find_perm_by_idx(index_to_find, original_text);
std::thread th([permuted, &all_results, repeat_times] () mutable {
// do your work on the permuted result, instead of pushing to vector
all_results.push_back(permuted);
for (size_t j=1; j<repeat_times; ++j)
{
std::next_permutation(permuted.begin(), permuted.end());
// do your work on the permuted result, instead of pushing to vector
all_results.push_back(permuted);
}
});
th.join();
index_to_find += repeat_times;
}
}
我在这里跳过输出，我已经验证它们与单线程next_permutation生成的相同。
单线程组合
接下来，我们进入next_combination部分。要计算总组合数，我们使用compute_total_comb。total必须是足够大的类型才能存储阶乘(n)。
void usage_of_next_comb()
{
std::string original_text = "123456";
std::string std_combined = "123";
uint64_t total = 0;
if(concurrent_comb::compute_total_comb(original_text.size(), std_combined.size(), total))
{
std::cout << std_combined << std::endl;
for (uint64_t i = 1; i < total; ++i)
{
stdcomb::next_combination(original_text.begin(), original_text.end(),
std_combined.begin(), std_combined.end());
std::cout << std_combined << std::endl;
}
}
}
输出如下。如果您的集合已排序，例如original_text，则所有生成的组合也将被排序，如下所示
123
124
125
126
134
135
136
145
146
156
234
235
236
245
246
256
345
346
356
456
多线程组合
index_to_find必须是足够大的类型才能存储阶乘(n)，并且vector_type可以是支持push_back()和size()方法的任何集合类型，例如std::string。与上面提到的find_perm_by_idx类似，可以使用find_comb_by_idx找到所有组合，但与next_combination相比，它慢得多，因此我们诉诸于next_combination来查找其余的组合。总共有20个组合，因此4个线程中的每个线程将找到20/4=5个组合。实际上，每个线程将找到5-1=4个组合，因为第一个组合已经在主线程中通过find_comb_by_idx计算出来并传递给线程。
template<typename int_type, typename vector_type>
vector_type find_comb_by_idx(const uint32_t subset,
int_type index_to_find,
vector_type& original_vector);
void usage_of_comb_by_idx()
{
uint64_t index_to_find = 0;
std::string original_text = "123456";
std::string std_combined = "123";
std::vector<std::string> all_results;
size_t repeat_times = 5;
for (size_t i = 0; i < 4; ++i)
{
std::string combined = concurrent_comb::find_comb_by_idx(std_combined.size(),
index_to_find, original_text);
std::thread th([original_text, combined, &all_results, repeat_times] () mutable {
// do your work on the combined result, instead of pushing to vector
all_results.push_back(combined);
for (size_t j = 1; j < repeat_times; ++j)
{
stdcomb::next_combination(original_text.begin(), original_text.end(),
combined.begin(), combined.end());
// do your work on the combined result, instead of pushing to vector
all_results.push_back(combined);
}
});
th.join();
index_to_find += repeat_times;
}
}
这里跳过输出，毕竟我已经验证它们与单线程next_combination生成的相同。