尽可能均匀地将间隔分为n部分
如何更有效地做到这一点?我认为有一个标准的快速方法来做到这一点。但我无法找到。尽可能均匀地将间隔分为n部分
这是用于在n个cpu内核之间划分一些内存的工作。
输出:
# Divide [0, 11) to 4 parts #
interval 0: [0, 3) with length: 3
interval 1: [3, 6) with length: 3
interval 2: [6, 9) with length: 3
interval 3: [9, 11) with length: 2
# Divide [0, 12) to 4 parts #
interval 0: [0, 3) with length: 3
interval 1: [3, 6) with length: 3
interval 2: [6, 9) with length: 3
interval 3: [9, 12) with length: 3
程序:
#include <iostream>
int part(int L, int n_parts, int part_id) {
int out = L/n_parts * part_id;
int r = L % n_parts;
if (part_id < r) {
out += part_id;
} else {
out += r;
}
return out;
}
void test(int L, int n_parts) {
std::cout << "# Divide [0, " << L << ") to "
<< n_parts << " parts #\n";
for (int i = 0; i < n_parts; ++i) {
int st = part(L, n_parts, i);
int en = part(L, n_parts, i + 1);
int len = en - st;
std::cout << "interval " << i <<": [" << st
<< ", " << en << ") "
<< "with length: " << len
<< "\n";
}
}
int main() {
test(11, 4);
test(12, 4);
}
到目前为止,它使用1个区,1%,1次乘法,1点相比,和1除了(嗒嗒机器人在左右) 。
我平时写解决这类问题,像这样:
size_t num_of_elements = 10'000;
size_t num_of_groups = 17;
for(size_t i = 0; i < num_of_groups; i++) {
std::pair<size_t, size_t> pair{
i * num_of_elements/num_of_groups,
(i + 1) * num_of_elements/num_of_groups
};
std::cout << "Group " << (i+1) << ": [" << pair.first << "," << pair.second << ") - " << (pair.second - pair.first) << " elements." << std::endl;
}
我们得到以下的结果,如果冲裁成mundane int main()
program:
Group 1: [0,588) - 588 elements.
Group 2: [588,1176) - 588 elements.
Group 3: [1176,1764) - 588 elements.
Group 4: [1764,2352) - 588 elements.
Group 5: [2352,2941) - 589 elements.
Group 6: [2941,3529) - 588 elements.
Group 7: [3529,4117) - 588 elements.
Group 8: [4117,4705) - 588 elements.
Group 9: [4705,5294) - 589 elements.
Group 10: [5294,5882) - 588 elements.
Group 11: [5882,6470) - 588 elements.
Group 12: [6470,7058) - 588 elements.
Group 13: [7058,7647) - 589 elements.
Group 14: [7647,8235) - 588 elements.
Group 15: [8235,8823) - 588 elements.
Group 16: [8823,9411) - 588 elements.
Group 17: [9411,10000) - 589 elements.
如果你想要这个逻辑提取到一个功能:
std::pair<size_t, size_t> get_bounds(size_t group_id, size_t num_of_groups, size_t num_of_elements) {
return std::make_pair<size_t, size_t>(
group_id * num_of_elements/num_of_groups,
(group_id + 1) * num_of_elements/num_of_groups
);
}
为什么需要“矢量”?应该计算分区而不需要向量或数组(或容器)。 –
@ThomasMatthews我已将其删除。我从我已经创建的项目中复制了代码wholecloth,并调整了变量名称,而不考虑在这里不需要该向量。 – Xirema
最糟糕的情况之一是10012 –
如果这个问题关闭,这意味着没有更快的方法。 –
我认为这个问题可能更适合[代码评论](https://codereview.stackexchange.com/) – Isac
那个地方是坟墓。好长时间的节目...这样简单的事情不应该花那么长时间。 –