使用二進制搜索並行合併排序

我想在Designing Efficient Sorting Algorithms for Manycore GPUs上提到的CUDA上實現合併排序算法。使用二進制搜索並行合併排序

對於這個在中間級別，它建議分配一個線程塊來將兩個排序後的數組（比如A和B）合併到一個數組中。這個想法是將一個線程分配給數組A上的data - a_i，並使用Binary Search在B數組中找到它的位置。並且如果B上a_i的位置是j，則新陣列上a_i的位置是（i + j）

但是，當我實現這個（或試圖）時，我發現上述方法看起來不起作用。例如，如果是需要合併兩個陣列如下，

和

，使得第一陣列上的53（在灰色一個被遮蔽）將找到它在第二個數組上的位置是11，所以它在最後一個數組上的位置是（11 + 11 = 22）。同樣在第一個陣列上53位置的藍色陰影是（11 + 12 = 23）。

如果我們取第二個數組中的第53個數組，它的最終位置也是（11 + 11 = 22）。這與第一個陣列上的灰色53相沖突。

所以根據我的理解，一個簡單的二分搜索算法不能用於合併這兩個數組。有沒有一種已知或更簡單的方法來解決這個衝突？

來源

2016-08-02 BAdhi

在論文中，我讀：

鑑於已排序的序列A和B，我們想要計算排序序列C =合併（A，B）。如果這些序列足夠小，我們可以使用單個t線程塊將它們合併爲，其大小不大於每個t = 256個元素。對於一個元素ai∈A，我們只需要計算秩（ai，C），它是合併序列C中元素ai的位置。因爲A和B都被排序，所以我們知道rank（ai，C ）= i + rank（ai，B），其中rank（ai，B）僅僅是元素bj∈B與bj < ai的計數，並且我們使用二分搜索有效地計算了。 B的元素顯然可以以相同的方式在中處理。

當您在尋找等級（ai，B）時，您必須在二進制搜索中處理重複項。想象B作爲BST，rank（ai，B）= j的最大值應該很好。

來源

2016-08-02 11:15:44 hmicn

好的，即使我們使用了這種方法，當我們試圖找到灰色53的最終位置時，我們是否仍然會發生衝突，因爲藍色53是其他值？ – BAdhi

我們不會。讓我們舉一個數組A的例子，例如A = 78,73,63,53,53，... 53.我們是否應該與A中的另一個ai發生衝突？不，作爲秩（ai，C）= i +秩（ai，B），我實際上是ai在陣列A中的位置。對於A中的每個53我實際上是不同的。因此，對於常數秩，B），不可能與其他ai發生衝突。此外，讓我們取一個數組B，使得B = 84,58,58,53,53，二元搜索很容易確保rank（ai，B）在B中不是其他53。因此，rank（53，C）將是no其他等級（xi，C），其中xi在AUB和xi = 53 – hmicn

我指的是這樣一個例子，A = 78,73,53,49,45和B = 84,58,58,53,40。所以根據你的等級（ai，B）函數，rank（53_A，B）= 3（其中53_A在數組A中爲53），因此給出等級（53_A，C）= 2 + 3 = 5。類似地，等級（53_B （53_B，C）= 3 + 2 = 5。因此，我們有這樣一種情況，即rank（53_A，C）= rank（53_B，C），它寫入每個數組A和數組B進入C的第5個位置，這是一個衝突 – BAdhi

使用二進制搜索並行合併排序

回答

相關問題