3

我正在尝试并行合并两个列表。我有两个排序列表[(i, j, val)]。列表按 排序j，对于相同j，按 排序i。如果两个列表包含相同(i, j)的值，则将它们的值相加并组合为一个，例如，如果第一个列表包含(i, j, val_1)，第二个列表包含，(i, j, val_2)则将两个组合在一起(i, j, val_1 + val_2)。

合并是高度顺序的，经过搜索，我找到了这篇论文。本文的想法是使用二进制搜索来获取最终列表中元素的排名。假设我们在i第一个列表中的第 th 位置，所以我们的(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) ]

搜索引擎

{-# 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 ) )

主文件

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 回答