3
我想並行合併兩個列表。我有兩個排序列表[(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