有無限CPU時比較兩個數組的最佳方法？

這是我在面試時遇到的問題。有兩個有序的數組A和B.檢查數組A中的每個元素是否出現在數組B中。假設有無限的CPU核心。面試官建議算法應該在O（1）中運行。我只想出了一個O（log（n））解決方案。有任何想法嗎？有無限CPU時比較兩個數組的最佳方法？

P.S.我的O（log（n））解決方案是將A中的一個元素分配給一個CPU核心，每個CPU使用二進制搜索來檢查該元素是否存在於數組B中。我記得面試官可能已經建議二分查找可以是優化到O（1）給定無限的CPU。但我不確定。以防萬一。

來源

2015-10-04 Sie Kensou

你可以在A和B中有重複的元素嗎？ – displayName

要實際制定解決方案O（log n），您需要描述如何將這n個CPU中的每個CPU的答案組合成一個O（log n）時間內的「YES/NO」答案。你可以例如將CPU排列成二叉樹結構，以便兩個「子」CPU將其結果傳遞給他們的共享父項，該共享父項將它傳遞給根目錄計算最終答案。 –

@displayName是的，可以有。 –

以下是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聚合，並且我認爲也存在相應的下限。

它可能是一個好主意，你可以問面試官對並行模型他感興趣的細節。

來源

2015-10-04 11:41:05

中間數組「found」的需求是什麼？ '如果A [i] == A [j] result = true'就足夠了。 –

@YvesDaoust不是。發現[我]必須爲我所有。至少這就是我對問題的理解 –

Ooops，你是對的。 –

讓每個內核的時間從一個元素上，和一對從相鄰B.要素爲每種可能的組合使用不同的核心。核心將分別比較他們的三個要素。如果來自A的元素在兩個B之間（並且不等於），則A中有一個元素不會出現在B中。

這缺少一些明顯的優化。例如，a1000不需要與b1進行比較，而是與無限的機器相關，誰在乎。

來源

2015-10-04 13:59:02 Dave

對於A的每個元素還需要一個CPU來檢查它是在B的第一個元素之前，還是在最後一個元素之後。儘管如此，這並沒有改變。 –

我仍然認爲你需要某種方式在O（1）時間內將所有這些答案聚集在一起，儘管... –

當核心在值之間找到一個元素時，它可以發信號通知第一個核心（也許設置一個共享內存位），所以這是O（1）。爲了證明序列不匹配，只需要第一個失敗的例子，並且知道是否沒有人在一個週期內設置該序列是好的。 @j_random_hacker –

，以補充人Niklas B.很好的答案，我補充說，爲O（1）解決方案，我懷疑你可以用不到在最壞情況下Ω（MN）內核做，即使有排序的數組。

如果所有的元件在兩個陣列出現一次（和隱式M = N），則可以並行地進行N次比較中，「面對」的元素，即，使用Θ（N）芯部之間。

但是重複被允許的情況下，相等的元素可以與換檔，它可以生長爲Ω（M + N）一樣大並且在預先不知道出現。要嘗試所有元素的所有可能的移位，請執行Ω（MN）比較。

來源

2015-10-04 16:33:26

設A共有一個元件和B具有總b元件（以及我假定的元素可以被重複）。

我們需要總（（A * B）+ 1）核心：我們要檢查B. A的每個元素因此，我們需要總b處理器爲A的每個元素，因此a * b。 Last +1適用於運行主程序的主處理器。

如果兩個元素相等或不相等，每個處理器將簡單地進行比較。如果是，則返回true，否則返回false。以A [0]爲例。我們只比較B的任何元素是否等於A [0]。所以我們把A [0]和B [0]傳給第一個處理器，A [0]和B [1]傳給第二個處理器等等，然後對結果做OR。相應地，對於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 ）時間。

來源

2015-10-04 16:59:50 displayName

我不完全知道如何對O（1）時間的結果做OR或或？ –

@SieKensou：更新了我的答案。 – displayName

感謝您的更新:)我看到所有的測試（A [k]，B [1]）如何在O（1）中完成，但爲什麼在OR元素上執行OR和AND的過程需要O （1）時間而不是O（a * b）？有沒有使用特殊技術？ –

有無限CPU時比較兩個數組的最佳方法？

回答

相關問題