我正在为松散耦合的集群编写一些代码。为了在工作期间获得最佳性能，每次孩子进入或者退出时，我都会让群集重新映射其数据。最终将使它成为可选的，但现在默认情况下它将执行其数据平衡。我的平衡基本上只是确保每个孩子的平均文件数量不会超过每台计算机的平均文件数量加一。如果除法不正确，则余数为加号。而且由于剩余数将始终少于子项数(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. 我想我今天早上没有喝咖啡！ ;)

将来，我想使用一种更灵活，更具弹性的分配方法(权重和方法)，但就目前而言，统一分配数据是可行的。

解决方案

我认为分析是不正确的：

• 遍历列表以找出平均值为O(n)
• 列出数据块太多或者太少的孩子的列表也是O(n)
• 移动数据与数据量成正比

我们是怎么到达O(n！)的？

我们可以对列表进行排序[子代数中的O(n lg n)]，这样一来，我们前面的儿童工作量很大，而最后的孩子工作量却很少。然后从两端同时遍历该列表：一个迭代器指向具有多余数据的子代，另一个指向缺少数据的子代。传输数据，并向前移动一个迭代器，或者向后移动另一个迭代器。

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

我们发布的代码的复杂度为O(n ^ 2)。不过，正如马拉奇所观察到的那样，仍可以在线性时间内完成此操作，其中n是子级列表中的项数。

考虑：内部循环有n次迭代，并且最多执行n次。 n * n = n ^ 2.

我们可能想尝试一种完全不同的方法，例如一致的哈希。

请参阅此处，以对该主题进行相对简单的介绍：
http://www8.org/w8-papers/2a-webserver/caching/paper2.html

(从Karger等人开始，也有更深入的论文可用)

我已经在Erlang中创建了一个一致哈希算法的可行实现，我们可以检查是否愿意：

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