你能在 O(n/p) 时间内进行并行计数排序吗？

Question

是否可以并行进行计数排序并实现 O(n/p) 运行时？

举个例子，我们有一个包含数百万个元素的数组，范围从 1 到 10。合并排序的运行时间不会超过 O(nlogn) 时间。应用于此问题的计数排序将在 O(n) 时间内运行。并行化计数排序可能很有趣。如果我们为每个处理器分配一个包含 n/p 个元素的子数组，并且每个处理器都有自己的大小为 9 的计数数组，那么累积元素计数的初始步骤应该花费 O(n/p) 时间。将所有计数数组合并为单个数组应该花费 O(p) 时间，因为您只迭代 p 个计数数组，每个数组的大小都是恒定的。

我一直无法完全思考计数排序的最后一步，其中元素按顺序排列。如果计数数组的元素是原子的，您可以将原始数组的 n/p 部分分配给各个处理器并实现一些并行化，但计数数组的各个元素会出现争用，这可能会大大减少并行化。如果输入数组都是 10，则所有处理器都将在计数数组的第 9 个元素上进行序列化，从而将算法效率降低到 O(n)。

您可以将 count 数组的子数组分配给 p 个处理器中的每一个，然后返回 O(n/p) 运行时，但前提是元素分布相当均匀。而且，在我们的示例中，您将被限制为 10 个处理器。如果元素分布不均，一个或多个处理器可能会承担更大比例的工作。例如，如果输入数组中的一半元素为 10，则一个处理器将不得不单步执行该数组的一半。最坏的情况是，数组全部为 10，单个处理器必须遍历整个数组，将运行时间降低到 O(n)。

也许您可以在多个处理器之间划分计数数组的各个元素。例如，如果输入数组中有 50 个 10，则计数数组的元素 9 将反映这一点。您可以让 5 个处理器将 10 个 10 写入输出数组中的正确位置。如果 count 数组的每个索引位置的元素少于 p 个，这又会转化为 O(n) 运行时，但它避免了元素值分布不均匀的问题。

是否可以在 O(n/p) 时间内进行计数排序？

Answer 1

对的，这是可能的。将数组分成p等长的部分。然后为每个进程创建一个计数数组“c”。让每个进程计算元素的数量并将它们存储在c. 这将需要O(n/p). 现在将所有计数数组加c在一起并使该数组共享给所有进程。这将需要O(p*b)，其中b是可能值的数量。到目前为止，这正是您的方法。现在您可以在p进程中重新创建数组，因为您可以从c. 对于每个值，i它的第一个索引是 中所有先前值的总和c。它的最后一个索引是它的第一个索引 plus c[i]。这种计算可以做到O(i)哪里i是smalleer然后b，所以就少了O(b)。每个进程现在都可以重新填充自己的部分。这又需要O(n/p). 总而言之，你有n/p + p*b + b + n/p。如果p*b << n会导致O(2*n/p). （由于2/p是一个常数因子，您仍然拥有 class O(n)。但并行化将显着加快您的算法。）