如何在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中使用並行策略編寫嵌套循環問題

回答

相關問題