algorithm - 平衡分配算法

Question

我正在为一个松散耦合的集群编写一些代码。为了在作业期间实现最佳性能，我让集群在每次 child 进入或退出时重新映射其数据。这最终将成为可选的，但现在它默认执行数据平衡。我的平衡基本上只是确保每个 child 拥有的文件数永远不会超过每台机器的平均文件数加一。如果除法不干净，则加一是余数。由于余数总是小于 child 的数量[除了 0 的情况，但我们可以排除这种情况]，平衡后的 child 最多有 avg + 1。

一切似乎都很好，直到我意识到我的算法是 O(n!)。沿着 child 的名单往下看，找出平均数，余数，谁太多，谁太少。对于太多列表中的每个 child ，遍历列表，发送给每个太少的 child 。

有更好的解决方案吗？我觉得一定有。

编辑:这里有一些伪代码来展示我是如何导出 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。我想我今天早上没有喝足够的咖啡! ;)

将来我想转向更灵活、更有弹性的分布方法[权重和启发式]，但现在，数据的均匀分布是可行的。

Answer 1

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

See previous answer

最后一步看起来像这样:

在第二步中，在 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;
  }
}