题

我工作上的一些代码为一个松散耦合的集群。要实现最佳业绩期间的工作，我们的集群的重新它的数据，每次一个孩子进入或退出。这最终将做出可选择的，但现在它执行其数据均衡的默认。我的平衡基本上只是确保每个儿童从来没有超过该平均数量的文件每台计算机，再加上一个。加一是对剩余部分，如果该司不干净的。并且因为其余会 总是 将低于儿童人数[，除了0情况，但我们可以排除]、儿童后一平衡将具有至多平均+1.

一切似乎都很好,直到我意识到我的算法是O(n!).下列表中的儿童，找出平均，其余的，谁有太多的和谁拥有太少。对于每个儿童在太多的清单，通过名单，发送给每个孩子已经太少。

是否有更好的解决这个?我觉得有必要。

编辑：这里是一些psuedocode以显示如何我源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]，但是现在，一个均匀分布的数据的工作。

有帮助吗？

解决方案

@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)
  • 使得名单的儿童过多或过少数据的区块也是O(n)
  • 移动数据的数量成比例的数据

你怎么到达O(n!)?

你可以排序的清单[O(n lg n)中的儿童数量]，以便在前你有孩子有太多的工作，并在结束儿童与太少的工作。然后穿越列从两端的同时：一个迭代分子用过量的数据，其他为儿童与缺乏数据。传输数据，以及移动无论是一个迭代的前进，或者该其他落后。

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

请参阅此处以获得相对简单的主题介绍： http://www8.org/w8-papers/2a-webserver/缓存/ paper2.html

（还有更深入的论文，从Karger等开始）

我在Erlang中创建了一致的哈希工作实现，您可以根据需要进行检查：

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

您发布的代码具有复杂度O（n ^ 2）。尽管如此，有可能在malach观察到的线性时间内完成，其中n是子列表中的项目数。

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

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top