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)ます。

マージは非常にシーケンシャルであり、検索した結果、この論文を見つけました。この論文のアイデアは、二分探索を使用して、最終的なリスト内の要素のランクを取得することです。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) ]

これら2つのリストを更新した後、

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 elem@( 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 

[ntro@localhost parBsearch]$ ghc -c -Odph -fdph-par -fforce-recomp Bsearch.hs
[ntro@localhost parBsearch]$ ghc -c -Odph -fdph-par -fforce-recomp Main.hs
[ntro@localhost parBsearch]$ ghc -o Bsearch -threaded -rtsopts -fdph-par Main.o Bsearch.o

[ntro@localhost 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))]
[ntro@localhost 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))]

誰かが更新を手伝ってくれませんか。よくわかりませんが、このアルゴリズムには多くのデータ移動が含まれているため、この目的のためにもっと良いものを提案してください。

4

1 に答える 1

3

私は haskell 言語に不慣れですが、ソートされたリストをマージするときは、バイトニック ソートを使用します。これは優れたアルゴリズムであり、設計において高度に並列化されています。唯一の制限は、サイズが 2^n のリストをマージすることです。リスト内の既知の値よりも高い値で短いリストをパディングすることで、この制限を回避しています。2 の累乗の制限に簡単に対応できるように、並べ替える膨大なリストがあります。

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

于 2012-02-02T22:08:13.037 に答える