并行合并两个排序列表

问题描述：

我想并行合并两个列表。我有两个排序列表[(i, j, val)]。列表根据j和j排序，按i排序。如果两个列表包含相同的(i, j)，则它们的值被添加并组合成一个，例如，如果第一个列表包含(i, j, val_1)并且第二个列表包含(i, j, val_2)那么组合两个将导致(i, j, val_1 + val_2)。并行合并两个排序列表

合并是高度顺序的，搜索后发现this paper。本文的想法是使用二进制搜索来获取最终列表中元素的排名。假设我们位于第一个列表中的第i个位置，因此我们在第一个列表中有(i - 1)个元素小于当前元素，并在第二个列表中执行对此元素位置的二进制搜索（假设此位置为j）。所以我们当前元素在最终列表中的位置将是i + j - 1（i - 1 + j - 1 + 1）。我使用dph-par编写了一个Haskell代码，但我有点被更新所困扰。我有两个列表

l_1 = [ (1, 1, 1), (2, 1, 1), (4, 1, 1), (1, 4, 1), (2, 4, 1), (4, 4, 1) ] 
l_2 = [ (1, 1, 1), (3, 1, 1), (4, 1, 1), (1, 4, 1), (3, 4, 1), (4, 4, 1) ]

和更新这两个列表后，我们应该有

l_3 = [ (1, 1, 2), (2, 1, 1), (3, 1, 1), (4, 1, 2), (1, 4, 2), (2, 4, 2), (3, 4, 1), (4, 4, 2) ]

Bsearch.hs

{-# LANGUAGE ParallelArrays #-} 
{-# OPTIONS_GHC -fvectorise #-} 

module Bsearch (interfaceSparse) where 
import qualified Data.Array.Parallel as P 
import Data.Array.Parallel.PArray 
import qualified Data.Array.Parallel.Prelude as Pre 
import qualified Data.Array.Parallel.Prelude.Int as I 
import qualified Data.Array.Parallel.Prelude.Double as D 

bSearch :: (I.Int , I.Int , D.Double) -> [: (I.Int , I.Int ,D.Double) :] -> I.Int 
bSearch [email protected](i , j , val) xs = ret where 
    ret = helpBsearch 0 len where 
     len = P.lengthP xs 
     helpBsearch :: I.Int -> I.Int -> I.Int 
     helpBsearch lo hi 
      | lo I.>= hi = lo 
      | cond = helpBsearch (mid I.+ 1) hi 
      | otherwise = helpBsearch lo mid 
      where mid = I.div (lo I.+ hi) 2 
      (i' , j' , val') = xs P.!: mid 
      cond = case() of 
        _| j' I.< j Pre.|| (j I.== j' Pre.&& i' I.<i) -> True 
         | otherwise -> False 

bSearchFun :: [: (I.Int , I.Int , D.Double) :] -> [: (I.Int ,I.Int , D.Double) :] -> [:I.Int :] 
bSearchFun xs ys = P.mapP (\(x , y) -> x I.+ y) (P.indexedP (P.mapP (\x -> bSearch x ys) xs)) 

bSearchMain :: [: (I.Int , I.Int , D.Double) :] -> [: (I.Int , I.Int , D.Double) :] -> [: (I.Int , (I.Int , I.Int , D.Double)) :] 
bSearchMain xs ys = l_1 where --here change l_2 for second list 
    lst = [: bSearchFun xs ys , bSearchFun ys xs :] 
    first = lst P.!: 0 
    second = lst P.!: 1 
    l_1 = P.zipP first xs 
    l_2 = P.zipP second ys 

interfaceSparse :: PArray (Int , Int , Double) -> PArray (Int ,Int , Double) -> PArray (Int , (Int , Int , Double)) 
{-# NOINLINE interfaceSparse #-} 
interfaceSparse xs ys = P.toPArrayP (bSearchMain (P.fromPArrayPxs) (P.fromPArrayP ys))

Main.hs

module Main where 
import Bsearch 
import qualified Data.Array.Parallel.PArray as P 
import Data.List 

main = do 
let 
    l_1 = P.fromList $ ([ (1 , 1 , 1) , (2 , 1 , 1) , (4 , 1 , 1) , (1 , 4 , 1) ,(2 , 4 , 1) , (4 ,4 , 1) ] :: [ (Int ,Int , Double) ]) 
    l_2 = P.fromList $ ([ (1 , 1 , 1) , (3 , 1 , 1) , (4 , 1 , 1) , (1 , 4 , 1) , (3 , 4 , 1) , (4 , 4 , 1) ] :: [ (Int , Int , Double)]) 
    e = interfaceSparse l_1 l_2 
print e

[[email protected] parBsearch]$ ghc -c -Odph -fdph-par -fforce-recomp Bsearch.hs 
[[email protected] parBsearch]$ ghc -c -Odph -fdph-par -fforce-recomp Main.hs 
[[email protected] parBsearch]$ ghc -o Bsearch -threaded -rtsopts -fdph-par Main.o Bsearch.o 

[[email protected] parBsearch]$ ./Bsearch --first list 
fromList<PArray> [(0,(1,1,1.0)),(2,(2,1,1.0)),(4,(4,1,1.0)),(6,(1,4,1.0)),(8,(2,4,1.0)),(10 (4,4,1.0))] 
[[email protected] parBsearch]$ ./Bsearch -- second list 
fromList<PArray> [(0,(1,1,1.0)),(3,(3,1,1.0)),(4,(4,1,1.0)),(6,(1,4,1.0)),(9,(3,4,1.0)),(10,(4,4,1.0))]

有人可以帮我更新。我不确定，但是这个算法涉及很多数据移动，所以好心的建议我为此目的更好。

我不明白冲突是如何多次被处理。如果您将列表与自身合并，则应该使用相同的键获得新列表，但所有值都加倍。如果每个元素都是平行放置的，那么处理元素X [i]的过程如何知道索引j pat 2012-01-29 20:00:20

@pat如果我找到了你，那么是的，它会在我的情况下留下洞（合并包含相同的i，j的元素）。如果我们考虑后来的例子，在位置1将会有（0,0,0），但是我们可以使用filterP对它进行过滤。 – 2012-01-29 21:33:59

@hammer感谢您设置帖子的格式。 – 2012-01-29 21:34:08

答

我不熟悉haskell语言，但是当我合并排序列表时，我使用了双向排序。这是一个很好的算法，并且在设计上非常平行。唯一的限制是你合并大小为2^n的列表。我通过填充短列表来填充这个限制，其值高于列表中的已知值，因此它们累积在一起并且可以被忽略。我有这样庞大的名单来排序，2限制的权力很容易适应。

http://en.wikipedia.org/wiki/Bitonic_sorter http://en.wikipedia.org/wiki/Odd-even_mergesort

并行合并两个排序列表

相关推荐