設置交叉點的並行算法

我有n個表示網格節點的數據集（分佈在n列），我想知道一個有效的並行算法來找到這些集合的交集，即公共節點。任何2組共享一個節點後立即定義交集。設置交叉點的並行算法

例如;

輸入：

Rank 0: Set 1 - [0, 1, 2, 3, 4] 

Rank 1: Set 2 - [2, 4, 5, 6] 

Rank 2: Set 3 - [0, 5, 6, 7, 8]

實現並行算法 - >結果：（發現交點之後）

Rank 0: [0, 2, 4] 

Rank 1: [2, 4, 5, 6] 

Rank 2: [0, 5, 6]

該算法需要在正行列進行與1組上的每個秩。

來源

2012-12-12 GK-F3D

我發現一個算法有效地做了2組交集，所以我正在考慮創建一個比較2個等級的樹結構，直到我耗盡所有的等級。 –

2組交叉算法看起來像這樣;我們可以有兩個索引，都從零開始。比較A和B的兩個第一個元素。如果A [0]大於B [0]，我們將B的索引增加1。如果B [0]大於A [0]，我們將A的索引增加1。如果它們相等，我們知道發生了交集，所以將其添加到列表並將A和B的索引增加1。一旦索引達到A或B的末尾，我們就找到了A和B的所有交集。這需要在排序後執行。 –

在數學上，你想要得到的每個等級的結果是該等級的集合與其他等級集合的交集**的聯合。對於並行實現，考慮一個等價問題可能是值得的：刪除不是任何其他集合的元素的每個元素。附：這些集合alwasys是否有序（如你的例子）？ –

你應該能夠用這個快速的O（N）並行哈希表。

對於每個集合S_i，對於每個成員m_x（所有成員都可以並行完成），將集合成員置於與集合名稱關聯的散列表中，例如。每當你從集合S_j的m_x的哈希表中得到一個命中，你現在就有相應的集合數S_i，並且你立即知道S_i與S_j相交。你可以把m_x放在派生的交集中。

您需要一個並行安全的散列表。這很容易;更新期間鎖定存儲桶。

[另一個答案建議排序集。對於大多數排序算法，將會是O（N ln N）時間，而不是快速]。

來源

2012-12-12 22:37:20

我想到了這一點，但是這不是內存密集？整個域中的節點數量（所有集合中所有條目的總和）可能爲100百萬。如果將所有組合放在1個等級上並使用優化的串行交叉算法，然後將此信息傳達給所有其他等級，會更好嗎？ –

你想要快。爲了獲得快速，你傾向於將時間換成空間。那麼，多少空間？估計，數據點可能是16個字節，集合ID可能是4個字節，哈希鏈接可能是8個字節，因此每個點有32個字節* 1億 - > 3200萬個字節。這是3.2 GB的RAM，在您當地的電腦經銷商處售價爲50美元。有什麼問題？ [你是不是已經把所有這些數據點都放在內存中了？] –

....如果你不想爲哈希表增加額外的內存，那麼對這些集合進行排序（爲空間支付時間）將是一個好的解決方案但是，1億是22（基數2），所以期望它明顯變慢。 –

設置交叉點的並行算法

回答

相關問題