arrays - 使用并发在旋转的排序数组中查找最小值

Question

这是一道面试题。

在第一部分中，我被要求在旋转的排序数组中找到最小值（例如，排序数组[1,2,3,4]被旋转到[3,4,1,2]）。可以在此处找到执行此操作的算法。

然后我被要求通过使用并行计算来改进算法。那是我的建议：

1. 假设我们可以k并行运行线程，将数组分成k大小相等的子数组（可能除了最后一部分）。
2. k对每个子数组 执行上述算法。
3. k返回算法运行的最小值。

面试官说算法运行时间不够好。你知道更好的解决方案吗？

标签： arraysalgorithmperformancetime-complexity

Answer 1

假设您有n+1 个硬件线程。您可以让n 个线程处理数组，每个线程“负责”1 个条目并在 O(1) 时间内完成，其余线程等待结果。为了提高效率，线程应该预先启动并使用索引变量（i）进行初始化，否则初始化本身将是 O(n) 时间。每个线程中的进程可能是：

if arr[i] > arr[(i + 1) mod n]
  SharedMemResult = arr[(i + 1) mod n]

这显然是 O(1) 时间，所有“主”线程所要做的就是读取SharedMemResult直到它发生变化（当然这需要初始化为某个极值，并且应该使用内存屏障来防止重新排序......） .

使用相同的概念，我们可以利用m个线程，其中每个线程在 O(log(n/m) 的 (n*i/m) -> (n*(i+1)/m - 1) 范围内找到最小值) 时间，然后验证这是真正的最小值（仅与范围中的第一项相关的是最小值，但对于大多数范围来说都是这种情况）。

结果是一个在 O(log(n/m)) 时间内解决问题的算法。