考慮以回圈方式M分布在N主機上的作業，其中每個主機必須獲得與其速度成正比的作業量。沒有比例，這是實作為：
int64_t AssignWorkToHost(const int64_t i_work) {
return i_work % N;
}
比例是p[i]總和為 的權重1.0，因此i-th 主機必須獲得更多或更少p[i]*M的作業。
M太大以致于存盤M值不適合單個主機的記憶體（但它適合的解決方案也很有趣）。N可以大到 10 000。理想情況下，每個主機必須存盤的O(M/N)值不超過 ，并且 的計算復雜度AssignWorkToHost()應該不超過O(N)。預處理沒問題。該演算法應該是確定性的，這意味著分布式組中的每個行程必須將相同的作業分配給主機。
uj5u.com熱心網友回復：
我建議使用一個優先級佇列存盤成對的(estimated processing time, worker)自定義比較器，按該順序進行比較。
在偽代碼中，assign to work 的主體如下所示：
(estimated_time, i) = queue.pop()
queue.push((estimated_time worker_time[i], i))
return i
這是確定性的，需要O(N)記憶體，并且每次分配都需要時間O(log(N))。
當然，您可以設定worker_time[i] = 1.0/worker_speed[i]，現在i分配的工人數量與其速度成正比。
對于查詢介面，我們可以通過重構歷史中的單個點，然后向前播放的簡單技巧來避免重播所有歷史。為此，在時間(i_work-1)/total_speed 不超過 i_work-1可已經產生。此外，不少于 i_work-N可以生產。（為什么？每個工人的產量都沒有達到理論elapsed_time / worker_speed[i]極限的<1 。因此N工人的產量N低于理論極限。因為它必須是一個整數，所以最多可以把它放在N-1后面。而且i_work-1 - (N-1) = i_work-N。）當時，對于每個工人，我們知道該工人生產了多少，并且我們知道下一次將生產另一個單位的時間。
這足以產生那個時刻的優先級佇列。然后我們向前播放。只需N幾步，k'th 就會彈出，正確分配。
查詢版本的總運行時間為O(N log(N)). 正如俗話所說，“對于所有意圖和目的，它log(N)都是一個常數。對于谷歌來說，它是一個更大的常數。”
（以相當多的復雜性為代價，我認為您可以使查詢介面真正實作O(N)。）
在幾乎是有效 Python 的偽代碼中：
total_worker_speed = sum(1/t for t in worker_time)
t = (i_work-1) / total_worker_speed
total_done = 0
todo = []
for i in 0..count_workers:
# At time t, this is how many are left.
done = floor(t/worker_time[i])
# This is how long until this worker produces the next unit
time_left = (done 1)*worker_time[i] - t
todo.push([time_left, i])
total_done = done
queue = heapify(todo) # turning array into priority queue is O(N)
while total_done < iwork:
# Get the next one.
(estimated_time, i) = queue.pop()
queue.push((estimated_time worker_time[i], i))
total_done = 1
# i now has the job that produced the iwork job.
return i
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/365911.html