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

Question

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

P.S。我的O(log(n))方案是把A中的一个元素分配给一个CPU个核，每个CPU用二分查找数组B中是否存在该元素。我记得面试官可能建议在给定无限 CPUs 的情况下，可以将二分搜索优化为 O(1)。但我不确定。以防万一

Answer 1

以下是Common CRCW模型中的O(1)PRAM algorithm，即只有写入相同的值才能并发写入。假设原始数组 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 聚合，我认为也存在相应的下限。

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

Answer 2

让每个核心采用 A 中的一个元素和 B 中的一对相邻元素。对每种可能的组合使用不同的核心。核心将各自比较它们的三个元素。如果 A 中的元素曾经介于 B 中的两个元素之间（并且不等于任何一个），则 A 中有一个元素未出现在 B 中。

这缺少一些明显的优化。例如，a1000 不需要与 b1 和 b2 进行比较，但有无限的机器，who cares.

Answer 3

为了补充 Niklas B. 的非常好的答案，我补充说对于 O(1) 解决方案，我怀疑在最坏的情况下，即使使用排序数组，您也可以使用少于 Ω(MN) 的内核.

如果所有元素在两个数组中都出现一次（并且隐式 M=N），您可以在 "facing" 个元素之间并行执行 N 次比较，即使用 Θ(N) 核。

但是当允许重复时，相等的元素可能会出现偏移，它可以增长到 Ω(M+N) 并且事先不知道。要对所有元素尝试所有可能的偏移，您执行 Ω(MN) 比较。

Answer 4

设 A 共有 a 个元素，B 共有 b 个元素（我假设这些元素可能会重复） .

我们将需要 总数 ((a * b) + 1) 个核心 ：我们要检查 B 中 A 的每个元素. 所以我们需要总共 b 个处理器来处理 A 的每个元素，因此 a * b。最后 +1 用于主处理器，运行是主程序。

每个处理器将简单地比较两个元素是否相等。如果是，它将 return true，否则 false。以 A[0] 为例。我们只是比较 B 的 any 元素是否等于 A[0]。因此，我们将 A[0] 和 B[0] 传递给第一个处理器，将 A[0] 和 B[1] 传递给第二个处理器，依此类推，并对结果进行或运算。相应地，test() 方法的代码将在每个核心上运行为：

public static bool test (int aElement, int bElement)
{
    return aElement == bElement;
}

接下来我们对 A[1] 做同样的事情，然后是 A[2].. 直到 A[a-1] 所有这些都是并行的。

我们对这个结果进行与运算，例如：

(test(A[0], B[0]) || test(A[0], B[1])...) && (test(A[1], B[0]) || test(A[1], B[1])... )

所以，Main() 看起来像：

public void Main (string[] args)
{
    //Read A and B arrays and create the next line dynamically
    var allPresent = (test(A[0], B[0]) || test(A[0], B[1]) ||... test(A[0], B[b-1]))
                  && (test(A[1], B[0]) || test(A[1], B[1]) ||... test(A[1], B[b-1]))
                  .
                  .
                  .
                  && (test(A[a-1], B[0]) || test(A[a-1], B[1]) ||... test(A[a-1], B[b-1]))
    Console.WriteLine("All Elements {0}", (allPresent ? "Found" : "Not Found"));
}

我们并行生成所有 test(A[k], B[l])，在 O(1) 时间内给出结果。

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

The best way to compare two arrays when there are infinite CPUs?

arrays

algorithm

parallel-processing