在分布式环境下，将一个阵列分割成两个子阵之和的最小差

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万，在分布式环境中如何解决这个问题？

我对分布式编程很陌生，在这方面需要帮助。

Answer 1

如果您有N节点，那么s将数组拆分为N顺序子数组；这将给出N顺序和。通过一次传递来确定哪个子数组包含所需的拆分点。“前”和“后”之和的区别是下一阶段的偏倚目标.

现在将“中间”数组划分为N片段。同样，您需要寻找适当的拆分点，但现在您知道了您想要的确切结果(因为您有数组和缺少的差异)。

重复第二段，直到您可以将整个子数组放入一个节点，这是完成项目计算的最快方法。

您可以通过在每个值上保持一个累积和来加速这一点；这将使您能够在每个阶段找到适当的分割点，因为您可以对第一个阶段之后的每个阶段使用二进制或插值搜索。

Answer 2

给定长度为N的数组和给定的M个可用节点，将数组划分为大小为N/M的块，每个节点计算其块的和，并报告返回。总数是通过加法部分和来计算的。然后，将总数和部分和分配给每个节点。每个节点确定其块内的最佳分割点(局部最小值)，并报告返回。全局最小值是从局部极小计算出来的。

例如，如果数组有1,000万个条目，并且有200个节点可用，则块大小为50000。因此，每个节点接收50000个数字，并报告和。数组的总数是通过添加200部分和来计算的。然后给出每个节点的总数，以及200部分和。现在，每个节点上的信息包括

• 块号
• 该块的50000数组条目。
• 数组总数
• 200部分和

根据这些信息，每个节点可以计算其局部最小值。全局最小值是从200个局部极小计算出来的。

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

当然，在现实世界中，试图散布这样的问题是没有意义的。通过网络发送数组元素的时间(每个数组元素)非常重要。比在一台计算机上解决这个问题所需的时间(每个数组元素)要大得多。

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_i，. min_k

附带注意:可以优化原始算法，使其只保留值rightSum - leftSum，而不是保留两个单独的值leftSum和rightSum。分布式版本也可以进行相应的优化。