平衡分布算法

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

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

• 浏览列表,找出平均值为O(n)
• 列出数据块过多或过少的子级也是O(n)

你是怎么到达O(n!)的?

您可能想尝试一种完全不同的方法,例如一致性哈希。

请参见此处,以获得对该主题的相对简单的介绍: http://www8.org/w8-papers/2a-webserver/caching/paper2.html

我已经在Erlang中创建了一个一致性哈希的工作实现,如果您愿意,可以对其进行检查:

http://distributerl.googlecode.com/svn/trunk/chash.erl

您发布的代码的复杂性为O(n^2)。尽管如此,正如malach所观察到的那样,可以在线性时间内完成,其中n是子列表中的项目数。

考虑:内部循环有n次迭代,它被执行 顶多 n次。n=2。