3
2つのリストを並行してマージしようとしています。私は2つのソートリスト[(i, j, val)]を持っています。リストはjにソートされ、同じjの場合はiにソートされます。 2つのリストに同じ(i, j)が含まれている場合、それらの の値が追加され、1つに結合されます。最初のリストに(i, j, val_1)が含まれ、2番目のリストに(i, j, val_2)が含まれている場合、2つを組み合わせると(i, j, val_1 + val_2)となります。2つのソート済みリストの並列マージ
マージは高度に連続しており、検索後にはthis paperが見つかりました。この文書の考え方は、バイナリ検索を使用して最終リストの要素のランクを取得することです。最初のリストのi番目の位置にあり、(i - 1)の要素が最初のリストの 現在の要素より小さく、2番目のリスト（この位置はj）でこの要素の位置をバイナリ検索します。したがって、最終リストの現在の要素の位置はi + j - 1（i - 1 + j - 1 + 1）になります。私はこのためにdph-parを使ってHaskellのコードを書いたが、私は更新に悩まされている。私は2つのリスト
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))]
更新してもらえますか？私は確信していませんが、このアルゴリズムはデータの動きが多いので、この目的のために何か良いことを教えてください。
私はどのように扱われるか多重衝突を理解していません。リストをマージすると、同じキーで新しいリストを取得する必要がありますが、すべての値は2倍になります。各要素がパラレルに配置されている場合、要素X [i]を処理しているプロセスは、現在のインデックスだけでなく、インデックスj
pat
@pat私があなたを正しく得たなら、それは私の場合に穴を残す（同じi、jを含む要素をマージする）。 postからの例を考えると、位置1に（0、0、0）がありますが、filterPを使用してフィルタリングできます。 –
@hammer投稿をフォーマットしてくれてありがとう。 –