均衡分配算法

我工作的松耦合集群一些代码。为了在作业期间实现最佳性能，每次儿童进入或退出时，我都会重新映射其数据。这将最终成为可选项，但现在它默认执行数据平衡。我的平衡基本上只是确保每个孩子的平均数不会超过每台计算机的平均数量，再加上一个。如果师不干净，则剩余的一个是余下的。而且，由于其余的将始终少于孩子的数量[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。我猜我今天早上没有足够的咖啡！）

在未来，我想移动到更柔性和弹性的分配方法[重量和hueristics]，但就目前而言，数据的均匀分布的工作原理。

来源

2008-09-26 Nicholas Mancuso

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

来源

2008-09-26 14:21:28