如何在Haskell中使用并行策略编写嵌套循环问题

我在玩并行策略并想知道我是否按照正确的方式执行下列操作。 Java代码：如何在Haskell中使用并行策略编写嵌套循环问题

double x = 0.0; 
    double[] arr = new double[2000]; 

    for (int i = 0; i < arr.length; i++) 
     arr[i] = i; 

    for (int i = 0; i < arr.length; i++) { 
     x += arr[i] * 5; 

     for (int j = i + 1; j < arr.length; j++) 
      x -= arr[j] * 3; 
    }

它采用并行策略来计算结果

哈斯克尔程序：

n = 2000 
    ns = [0..n-1] 

    segments = chunk 100 ns 

    chunk n [] = [] 
    chunk n xs = ys : chunk n zs 
     where (ys,zs) = splitAt n xs 

    parCompute = foldl' (+) 0 (map (\ts -> compute ts) segments `using` parList rdeepseq) 

    compute ts = foldl' addfunc 0 ts 
     where 
      addfunc acc i = (acc + x) - (foldl' minusfunc 0 [(i+1)..(n-1)]) 
       where 
        x = (ns!!i) * 5 
        minusfunc acc' j = (acc' + x') 
         where 
          x' = (ns!!j) * 3 

    main = print parCompute

我的问题是：

是它的使用权与foldl”在这里吗？我想因为所有计算都需要完成以获得结果，所以我应该强制评估。
有没有更好的方法来使用段？在这个问题中我可以利用哪些常见模式？
其他什么策略可以应用于这个问题？此外，任何使用par和seq原语进行并行化的可能性。

来源

2011-06-22 vis

风格评论：嵌套wheres丑陋。 – rampion

我不认为这些代码是等价的。代码“x - = arr [j] * 3”被应用于列表中位置“i”之后的所有项目，但在haskell代码中，等价物仅应用于本地块，而不是所有位于“i”位置的值。或者，也许我读错了。 –

@Tim：它给出了相同的答案。我已经检查了Haskell对Java的结果。 – vis

好吧，让我们使用惹巴（常规并行阵列）这段时间，并将其与parListChunk方法比较（因为Java示例使用数组不是列表）：

module Main where 

import Control.Parallel.Strategies 
import Data.List (tails) 
import System.Environment (getArgs) 
import qualified Data.Array.Repa as R 
import qualified Data.Array.Repa.Shape as RS 

chunksize = 100 

parListCompute :: [Int] -> [Int] 
parListCompute ts = (computes `using` parListChunk chunksize rseq) 
    where 
    computes = zipWith f ts (tail (tails ts)) 
    f t tls = 5 * t - 3 * sum tls 

parRepaCompute :: R.Array R.DIM1 Int -> R.Array R.DIM1 Int 
parRepaCompute arr = R.force $ computes 
    where 
    computes = R.map f arr 
    f x   = 5*x - 3*(sumRest (x+1) 0) 
    sumRest x acc | x > (RS.size . R.extent $ arr) = acc 
        | otherwise      = sumRest (x+1) (acc+x) 

main = do 
    (s:_) <- getArgs 
    case s of 
    "1" -> putStrLn . show .sum $ parListCompute l 
    "2" -> putStrLn . show . R.sum $ parRepaCompute r 
    where l = [1..70000] 
     r = R.fromList (R.Z R.:. (length l)) l

这里是结果：

~/haskell$ ghc --make nestloop.hs -O2 -rtsopts -threaded 
[1 of 1] Compiling Main    (nestloop.hs, nestloop.o) 
Linking nestloop ... 
haskell$ time ./nestloop 1 +RTS -N4 
-342987749755000 

real 0m5.115s 
user 0m19.870s 
sys  0m0.170s 
~/haskell$ time ./nestloop 2 +RTS -N4 
[-342987749755000] 

real 0m1.658s 
user 0m3.670s 
sys  0m0.070s

我希望你会喜欢这个比较。

来源

2011-06-24 03:52:04 aycanirican

感谢您的比较。这绝对有用。在选择哪种答案最适合我的情况之前，我会等待看看是否有其他选择。 – vis

这是我会怎么翻译你的Java程序到并行的Haskell程序：

parCompute ts = sum (computes `using` parListChunk 100 rseq) 
    where 
    computes = zipWith f ts (tail (tails ts)) 
    f t tls = 5 * t - 3 * sum tls

第一关 - 是的，引入严格这里是一个不错的主意。另一方面，GHC非常聪明，足以发现这一点！实际上，无论您使用的是foldl,foldl'还是仅使用sum，生成的代码都是完全相同的。

要评估分段中的列表，可以简单地使用上面所述的分块策略。然而，每个块代表的工作量可能会大不相同，因此您可以尝试通过在列表末尾制作更大的块来实现。除此之外，我认为这里没有太多改进的余地。

来源

2011-06-23 15:02:15

谢谢你。你的解决方案看起来不错，而且很有用，但我不太确定生成的代码是否与foldl，foldl'相同。 foldl'强制每次应用函数完成累计结果评估。在某些情况下，它比使用foldl提供了更好的加速，但不确定生成的代码的方式可能相同。 – vis

如何在Haskell中使用并行策略编写嵌套循环问题

回答

相关问题