algorithm - 均匀划分连续的数字序列

Question

在 K workers 之间连续并行化 N 令人尴尬的并行工作 block 的一项常见任务是使用以下算法在伪代码中进行分区:

acc = 0
for _ in range(K):
    end = acc + ceil(N/K)
    emit acc:end
    acc = end

这将发出 K 个连续分区，通常大小为 N/K，并且适用于大的 N。但是，如果 K 大约为 N，这可能会导致不平衡，因为最后一个 worker 将获得很少的项目。如果我们将不平衡定义为分区大小之间的最大绝对差异，则迭代算法从任何随机分区开始并减少潜力，直到最大差异为 1(如果 K 将 N) 将是最优的。

在我看来，通过执行在线“重新规划”，以下可能是获得相同答案的更有效方法。这个算法有名字和最优性证明吗？

acc = 0
workers = K
while workers > 0:
    rem = N - acc
    end = acc + ceil(rem/workers)
    emit acc:end
    acc = end
    workers -= 1

编辑。鉴于我们可以递归地定义上面的循环，我可以看到归纳最优性证明可能有效。无论如何，我们将不胜感激 :)

Answer 1

划分范围的一种简单方法是:

for i in range(K):
  emit (i*N // K):((i+1)*N // K)

这具有本身可并行化的优势，因为迭代不需要按顺序执行。

很容易证明每个分区都有 floor(N/K) 或 ceil(N/K) 元素，而且很明显每个元素都会恰好在一个分区中。由于下限和上限最多相差 1，因此该算法必须是最优的。

您建议的算法也是最优的(并且结果相似)。不过我不知道它的名字。

另一种可以并行完成的划分范围的方法是使用范围 start(N, K, i):start(N, K, i+1) 其中 start(N, K, i) 是 (N//K)*i + min(i, N%K)。 (注意 N//K 和 N%K 只需要计算一次。)这个算法也是最优的，但是分配了不平衡，所以第一个分区是较大的。这可能有用也可能没用。