logo标签列表

平衡分配算法

algorithmbig-oload-balancingcluster-computing
6
我正在为一个松散耦合的集群编写一些代码。为了在作业期间实现最佳性能，我让集群在每次子进程进入或退出时重新映射其数据。这将最终成为可选项，但目前默认情况下它会执行其数据平衡。我的平衡基本上只是确保每个子进程永远不会拥有超过每台机器上平均文件数加1的文件数。如果除法不干净，那么加1是为了余数。由于余数始终小于子进程数量[除0之外]，因此经过平衡后的子进程最多只有avg + 1个文件。
一切看起来都很好，直到我意识到我的算法是O(n!)。按照子进程列表，找到平均值、余数、谁有太多和谁有太少。对于太多名单中的每个子进程，在列表中进行遍历，发送给每个有太少的子进程。
这个问题是否有更好的解决方案？我觉得一定有。
编辑：以下是一些伪代码，展示了如何推导出O(n!)：
foreach ( child in children ) {
    if ( child.dataLoad > avg + 1 ) {
        foreach ( child2 in children ) {
            if ( child != child2 && child2.dataLoad < avg ) {
                sendLoad(child, child2)
            }
        }
    }
}

编辑：O(n^2)。对于每个n，n => n*n => n^2。我猜今天早上我喝的咖啡不够！ ;)

将来我想采用更灵活、更有弹性的分配方法[权重和启发式算法]，但现在，数据的均匀分布就可以了。

4个回答
4

@zvrba：您甚至不需要对列表进行排序。在第二次遍历列表时，只需将所有工作负载小于平均值的项目移动到列表末尾（您可以在第一次遍历时保留指向最后一个项目的指针）。顺序不必完美，它只是在迭代器必须在最后一步增加或减少时发生变化。

查看先前的答案

最后一步将类似于：

在第二步中，在child2中保持指向工作负载小于平均值的第一个项目的指针（以防需要双重链接列表）。

for each child in list {
  if child2 == nil then assert("Error in logic");
  while child.workload > avg + 1 {
    sendwork(child, child2, min(avg + 1 - child2.workload, child.workload - (avg + 1)))
    if child2.workload == avg + 1 then child2 = child2.next;
  }
}
2

我认为你的分析是错误的:

  • 遍历列表以找出平均值的时间复杂度是O(n)
  • 创建具有过多或过少数据块的子列表也是O(n)
  • 移动数据与数据量成正比

您是如何得出O(n!)的结论的？

您可以对列表进行排序[在儿童数量上为O(n lg n)]，以便在前面有太多工作的孩子，在后面有太少工作的孩子。然后同时从两端遍历列表：一个迭代器指向具有多余数据的孩子，另一个迭代器指向缺乏数据的孩子。转移数据，然后将一个迭代器向前移动，或将另一个迭代器向后移动。

对于每个孩子，如果其数据负载大于平均值加1，则将其与其他孩子进行比较。内部循环不会在每次迭代中缩短。 - Nicholas Mancuso
2
1
你所发布的代码具有O(n^2)的复杂度。不过，正如malach所观察到的那样，仍然有可能在线性时间内完成，其中n是children列表中项目的数量。
考虑一下：内部循环有n次迭代，并且最多执行n次。n*n = n^2。
你确定吗？如果内部循环从child.pos + 1开始，我认为它会是O(n^2)，但是它每次都从循环的开头开始，并且必须这样做以确保负载均衡。按照你所说的对列表进行排序更有意义，然后内部循环必须从child.pos + 1开始。 - Nicholas Mancuso
我同意zvrbra的观点 - 这是一个O(n^2)算法。 - rjzii
你说得对。我没有考虑清楚。对于每个n，n . n * n. n^2. ;)。 - Nicholas Mancuso
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接