平衡分配算法

Question

我正在为松散耦合的集群开发一些代码.为了在作业期间实现最佳性能,每次孩子进入或退出时,我都会重新映射其数据.这最终将成为可选的,但是现在它默认执行数据平衡.我的平衡基本上只是确保每个孩子的每台机器的平均文件数量不超过一个.如果除法不干净,则加上余数.并且由于其余部分总是小于儿童数量[除了0例,但我们可以排除],平衡后的儿童最多只有平均值+ 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).Foreach n,n => n*n => n ^ 2.我想我今天早上没有足够的咖啡!;)

在未来,我想转向一种更灵活,更有弹性的分配方法[权重和数据],但是现在,统一的数据分布工作.

Answer 1

@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;
  }
}