均衡分配算法

我工作的鬆耦合集羣一些代碼。爲了在作業期間實現最佳性能，每次兒童進入或退出時，我都會重新映射其數據。這將最終成爲可選項，但現在它默認執行數據平衡。我的平衡基本上只是確保每個孩子的平均數不會超過每臺計算機的平均數量，再加上一個。如果師不乾淨，則剩餘的一個是餘下的。而且，由於其餘的將始終少於孩子的數量[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