均匀地划分连续的数字序列

Question

在N工作者中，K令人尴尬地并行工作块并行化的一个常见任务是使用以下算法进行分区，在伪代码中：

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

这将发出K通常大小N/K的连续分区，并适用于大型N。然而，如果K大约是N，这可能会导致不平衡，因为最后一名工人将获得非常少的物品。如果我们将不平衡定义为分区大小之间的最大绝对差异，那么从任何随机分区开始并且减小潜力直到最大差异为1（或者如果K除N则为0）的迭代算法将是最优的。

在我看来，通过执行在线“重新规划”，以下可能是一种更有效的方式来获得相同的答案。此算法是否具有名称和最优性证明？

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只需要计算一次。）此算法也是最优的，但是分配不平衡，以便第一个分区是较大的分区。这可能有用也可能没用。

Answer 2

这是一种更简单的方法。你有floor(N/K)任务，可以在工人之间完美地划分，留下N mod K剩余的任务。为了保持区域连续，您可以将剩余的任务放在第一个N mod K工作者上。

这是一种势在必行的风格。为了清楚起见，我正在编写任务{0 ..（N-1）}，并发出一组连续的任务编号。

offset = 0
for 0 <= i < K:
  end = offset + floor(N/K)
  if i < N mod K:
    end = end + 1
  emit {c | offset <= c < end}
  offset = end

并以更具说明性的风格：

chunk = floor(N/K)
rem = N mod K

// i == worker number
function offset(i) =
  i * chunk + (i if i < rem else rem)

for 0 <= i < K:
  emit {c | offset(i) <= c < offset(i+1)}

在这一点上，最优性的证明是非常微不足道的。工人i分配了offset(i+1) - offset(i)任务。根据i，这是floor(N/K)或floor(N/K) + 1任务。