优化C++函数生成组合
我试图得到一个函数来生成所有可能的数字组合，但我的问题是精化时间太长。所以我认为我必须优化它。问题:用1到n个元素生成所有"r“大小集，而不按反向顺序重复(1,2等于2，1)。
示例：
n = 3 //elements: 1,2,3
r = 2 //size of set
Output:
2 3
1 3
1 2我使用的代码如下：
void func(int n, int r){
vector <vector <int>> reas;
vector<bool> v(n);
fill(v.end() - r, v.end(), true);
int a = 0;
do {
reas.emplace_back();
for (int i = 0; i < n; ++i) {
if (v[i]) {
reas[a].push_back(i+1);
}
}
a++;
} while (next_permutation(v.begin(), v.end()));
}如果n=3和r=2时，输出将与上面的例子相同。我的问题是，如果我输入n= 50和r= 5，精化时间太长，我需要在n=50.100和r=1.5的范围内工作，有方法优化这个函数吗？
非常感谢
回答 1
Stack Overflow用户
发布于 2020-04-05 09:39:14
是的，有几件事你可以大幅度提高。但是，您应该记住，您正在计算的组合数量非常多，如果要枚举所有子集，则必须是缓慢的。在我的机器和我的个人耐心预算(100,5)是无法达到的。
考虑到这一点，以下是您无需完全重写整个算法就可以改进的地方。
第一:缓存局部性
vector<vector<T>>不会是连续的。嵌套向量相当小，所以即使预先分配，这也总是不好的，迭代它的速度会很慢，因为每个新的子向量(并且有大量的)可能会导致缓存丢失。
因此，使用单个vector<T>。然后，您的kth子集将不是位于k位置，而是位于k*r。但这对我的机器来说是个重大的加速。
第二:使用cpu友好的置换向量。
您使用next_permutation的想法还不错。但是使用vector<bool>的事实使得这个过程非常慢。矛盾的是，使用vector<size_t>比快得多，因为加载和检查size_t比使用bool更容易。
因此，如果将这些合并在一起，代码如下所示：
auto func2(std::size_t n, std::size_t r){
std::vector<std::size_t> reas;
reas.reserve((1<<r)*n);
std::vector<std::size_t> v(n);
std::fill(v.end() - r, v.end(), 1);
do {
for (std::size_t i = 0; i < n; ++i) {
if (v[i]) {
reas.push_back(i+1);
}
}
} while (std::next_permutation(v.begin(), v.end()));
return reas;
}第三:不要将整个结果按在一个巨大的缓冲区中
使用回调来处理每个子集。因此，您不必返回一个巨大的向量。相反，您需要为找到的每个独立子集调用一个函数。如果你真的需要一个庞大的集合，这个回调仍然可以将子集推到一个向量中，但它也可以对它们进行就地操作。
std::size_t func3(std::size_t n, std::size_t r,
std::function<void(std::vector<std::size_t> const&)> fun){
std::vector<std::size_t> reas;
reas.reserve(r);
std::vector<std::size_t> v(n);
std::fill(v.end() - r, v.end(), 1);
std::size_t num = 0;
do {
reas.clear(); // does not shrink capacity to 0
for (std::size_t i = 0; i < n; ++i) {
if (v[i]) {
reas.push_back(i+1);
}
}
++num;
fun(reas);
} while (std::next_permutation(v.begin(), v.end()));
return num;
}，这在我的实验中产生了超过2倍的加速比。但是你越往上爬，n 和 r**.**就越快。
另外:使用编译器优化
使用编译器选项尽可能加快编译速度。在我的系统中，从-O0到-O1的跳转是一个大大超过10倍的加速。从-O3到-O1的跳转要小得多，但仍然存在(大约x1.1)。
与性能无关，但仍然相关：Why is "using namespace std;" considered bad practice?
https://stackoverflow.com/questions/61039694
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号