這個問題本質上減少到一個連接操作,然后是一個過濾器操作(刪除重復,只保留內部匹配).

由于輸入都已經排序,所以可以通過O(O(size(a)size(b))的merge join來有效地實現連接.

過濾器操作將為O(n),因為連接的輸出被排序,并且要刪除重復項,所有您需要做的是檢查每個元素是否與之??前的元素相同.僅過濾內部匹配是微不足道的,您只是丟棄任何不匹配的元素(外連接).

并行機制(在連接和過濾器中)都有機會實現更好的性能.例如,Hadoop上的Apache Pig框架提供了parallel implementation的合并連接.

在性能和復雜性之間存在明顯的權衡(從而可維護性).所以我會說一個很好的答案面試問題真的需要考慮到性能要求.

>設置比較 – O(nlogn) – 如果沒有性能問題,相對較慢,非常簡單.簡單勝利.

>合并連接過濾器 – O(n) – 快速,容易出現編碼錯誤,使用if

表現是一個問題.理想情況下,嘗試利用現有庫來執行此操作,或者甚至在適當的情況下使用數據庫.

>并行實現 – O(n / p) – 非常

快速,需要其他基礎設施到位,如果卷是使用的

非常大,預計會增長,這是一個主要的表現

瓶頸.

(另請注意,intersectSortedArrays中的函數本質上是一個修改的合并連接,其中過濾器在連接期間完成,您可以稍后過濾,盡管內存容量略有增加).

最后的想法

事實上,我懷疑大多數現代商業RDBMS在實現聯接時提供線程并行性,所以Hadoop版本提供的是機器級并行性(分發).從設計的角度來看,也許一個很好的簡單的解決方案就是將數據放在數據庫上,A和B上的索引(有效排序數據),并使用SQL內部連接.