在分布式环境中拆分数组，找到两个子数组之和的最小差值

Question

昨天我被问到了这个问题。我需要编写一段代码，将数组分成两部分，使得这两部分之间的差值最小。

以下是我的代码，时间复杂度为O(n)

function solution(a) {
  let leftSum = 0;
  let rightSum = a.reduce((acc, value) => acc + value ,0);
  let min = Math.abs(rightSum - leftSum);
  a.forEach((item, i) => {
   leftSum += a[i];
   rightSum -= a[i]; 
   const tempMin = Math.abs(rightSum - leftSum);
   if(tempMin < min) min = tempMin;
  })
  return min;
}

但是如果输入数组长度为1000万，我该如何在分布式环境下解决这个问题呢？

我刚接触分布式编程，需要帮助。

- Mohd Hassan

---

如果只有1000万，网络延迟可能会成为一个负担。如果网络不是问题，您可以将每个计算节点分配给单独的块，并让节点为其块计算解决方案。这样，您还可以在开始时并行化求和。每个节点还需要其块左右值的总和。 - Nico Schertler

但如果节点计算它们自己块的最小差异，那么组合结果将与非分布式环境中的结果不同。我们可以并行化求和，但除此之外我不知道如何并行地计算最小差异。 - Mohd Hassan

两个长度相等的子数组之间的和？ - zer00ne

数组中允许负值吗？这会使事情变得复杂。 - Peter Cheng

@zer00ne 不，长度可能会有所不同。 - Mohd Hassan

@PeterCheng 是的，允许负值。 - Mohd Hassan

Answer 1

如果您有 N 个节点，则将数组拆分为 N 个顺序子数组；这将给您 N 个顺序求和结果。进行一次遍历以确定哪个子数组包含所需的拆分点。"之前"和"之后"总和之间的差是下一阶段的目标...

现在将"中间"数组分成 N 个部分。再次查找适当的拆分点，但现在您已经知道了确切的结果（因为您已经有了数组总和和缺失的差异）。

重复第二段直到能够将整个子数组放入一个节点中，并且这是完成项目计算的最快方式。

通过在每个值处保留累积总和，可以加快速度；这将使您能够在每个阶段之后使用二进制或插值搜索更快地找到适当的拆分点。

- Prune

Answer 2

给定一个长度为N的数组和M个可用节点，将数组分成大小为N/M的块。每个节点计算其块的总和并报告回来。总和通过添加部分和来计算。然后将总和和部分和分配给每个节点。每个节点确定其块内的最佳分割点（局部最小值），并报告回来。全局最小值从局部最小值中计算出来。

例如，如果数组有1000万个条目，并且有200个节点可用，则块大小为50000。因此，每个节点接收50000个数字，并报告回总和。通过添加200个部分和来计算数组的总和。然后将总和与200个部分和一起分配给每个节点。现在，每个节点的信息包括：

- 一个块编号 - 该块的50000个数组条目 - 数组总和 - 200个部分和

从这些信息中，每个节点都可以计算其局部最小值。全局最小值从200个局部最小值中计算出来。

在理想情况下，网络带宽无限，网络延迟为零，并且可以使用任意数量的节点，块大小应为sqrt(N)。因此，每个节点接收sqrt(N)个数组元素，然后接收sqrt(N)个部分和。在这些理想条件下，运行时间为O(sqrt(N))而不是O(N)。

当然，在现实世界中，尝试分发这样的问题是没有意义的。将数组元素通过网络发送的时间（每个数组元素）相当大。比在单个计算机上解决问题所需的时间（每个数组元素）要长得多。

- user3386109

---

如果在输入数据的范围内没有任何假设（特别是可能存在负数），那么每个节点如何确定它是否包含分裂点？ - GZ0

@GZ0 你说得对，我假设了数组元素都是非负数。如果有负数的话，每个节点会计算出最佳分割点，并报告其最小差值和最佳分割点。控制节点随后需要做出最终决定。 - user3386109

如果是非负数组，则控制节点可以已经确定最佳分割点的位置，并仅向所选节点发送指令。 - GZ0

@GZ0 感谢您的见解。我已经更新了答案。 - user3386109

Answer 3

假设数组按顺序存储在多个节点N_1，...，N_k上。您原始算法的简单分布式版本可能如下所示。

1. 在每个N_i上，计算存储在N_i上的子数组的总和s_i，并将其发送到控制节点M
2. 在节点M上，使用s_1，...，s_k，为每个N_i的左侧子数组边界计算leftSum_i和rightSum_i，并将它们发送回N_i
3. 在每个N_i上，使用leftSum_i和rightSum_i进行搜索以找到最小值min_i，并将其发送回M
4. 在节点M上，从min_i，...，min_k中计算全局最小值min

一个附注：您的原始算法可以优化为仅保留值rightSum-leftSum而不是两个单独的值leftSum和rightSum。分布式版本也可以相应地进行优化。

- GZ0