分布式系统中的插入排序

Question

插入排序如何处理分布式系统中数组的多个副本？ 我问这个问题是因为读取数据比写入数据更容易。 就更新次数而言，分布式系统中算法的成本是多少？

Answer 1

这完全取决于您的分布式插入排序版本。一种解决方案如下：

1. 数组 A（具有 n 个元素）被系统中的所有节点共享。
2. 数组 A 可以分为子数组 A1 、 A2 、 A3 、 ... 、 Ap ，其中 p 是系统中机器的数量。该分区是分布式执行的。也就是说，每个节点找到其子数组的下界和上界。 （这可以通过查找中位数、分割数组并再次查找中位数等来完成。）
3. 现在，每个节点都可以使用插入排序对其切片进行排序。
4. 每个节点中已排序的子数组可以通过归并排序或插入排序进行合并。

注意：通过计算更新次数来衡量分布式算法的有效性是不正确的。只要同时执行许多更新，就应考虑执行的总时间复杂度。