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

Question

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

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

Answer 1

以下是公共CRCW模型中的O(1) PRAM算法，即只有在写入相同值的情况下才能进行并发写入。假设原始数组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 n)时间内计算和和或聚合，我认为也存在一个相应的下限。

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

Answer 2

让每个核心从A中获得一个元素，而B中的两个相邻元素为每个可能的组合使用不同的核心。每个核将比较它们的三种元素。如果A中的元素介于B的两个元素之间(两者都不等于)，则A中有一个元素不出现在B中。

这缺少了一些明显的优化。例如，a1000不需要与b1 & b2相比，而是与无限机器相比，谁在乎呢。

Answer 3

设A有总a元素，B有总b元素(我假设可以重复这些元素)。

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

每个处理器将简单地比较两个元素是否相等。如果是，它将返回true，否则false。以A为例。我们只是比较B的任何元素是否等于A，所以我们把A和B传递给第一个处理器，A和B1传递给第二个处理器等等，然后对结果做一个OR。相应地，将在每个核心上运行的test()方法的代码如下：

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

接下来，我们对A1做同样的处理，然后用A2..一直到Aa-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)时间的结果。