arrays - 当有无限 CAMPU 时，比较两个数组的最佳方法是什么？

Question

这是我在面试中遇到的问题。有两个已排序的数组A和B。检查数组A中的每个元素是否出现在数组B中。假设有无限个CPU核。面试官建议算法应该在 O(1) 中运行。我只想出了一个 O(log(n)) 解决方案。有什么想法吗？

附言我的O(log(n))解决方案是将A中的一个元素分配给一个CPU核心，每个CPU使用二进制搜索来检查该元素是否存在于数组B中。我记得面试官可能建议过二进制搜索可以在给定无限 CPU 的情况下优化为 O(1)。但我不确定。以防万一。

Answer 1

下面是一个O(1) PRAM algorithm在 Common CRCW 模型中，即只有在写入相同值时才能进行并发写入。假设原始数组 A 有 n 个元素，B 的大小为 m。

found = new bool[n]
parallel for i in 0..n-1:
  found[i] = false
  parallel for j in 0..m-1: 
    if A[i] == B[j]:
      found[i] = true

result = true
parallel for i in 0..n-1:
  if !found[i]:
    result = false

print result ? "Yes": "No"

当然，我不完全确定这个模型的实用性。实际上，您可能没有并发写入。在具有独占写入的 CREW 模型中，您可以在 O(log log n) 时间内计算 AND 和 OR 聚合，我认为也存在相应的下限。

向面试官询问他感兴趣的并行模型的具体细节可能是个好主意。