分佈式系統中的插入排序

Question

插入排序如何處理分佈式系統中數組的多個副本？ 我問，因爲讀取數據比寫入數據要容易。 在更新數量方面，分佈式系統中算法的成本是多少？

Answer 1

這完全取決於您的分佈式插入排序版本。一種解決方案可以如下：

1. 陣列A（具有n個元素）被共享給系統中的所有節點。
2. 數組A可以被分割成子數組A1，A2，A3，...，Ap，其中p是系統中機器的數量。該分區是分佈式執行的。也就是說，每個節點都會找到其子數組的下限和上限。 （這可以通過找到中位數和拆分數組並重新找到中間值來完成，等等。）
3. 現在，每個節點都可以使用插入排序對其切片進行排序。
4. 每個節點中的排序子數組可以通過合併排序插入排序合併。

注意：通過計數更新數量來衡量分佈式算法的有效性是不對的。就許多更新同時執行而言，應該考慮執行的總時間複雜度。