更多通用parfoldr比這

我的目標是有一個平行foldr函數。起初，它似乎而直截了當地實現，這是我腦子裏想的：更多通用parfoldr比這

首先打破了輸入列表轉換成基於核心（numCapabilities）的分區數目。然後將foldr應用於每個分區，其中將導致每個分區的摺疊值列表。然後在該列表上再次執行摺疊以獲得最終值。

listChunkSize = numCapabilities 

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

    parfoldr f z [] = z 
    parfoldr f z xs = res 
     where 
      parts = chunk listChunkSize xs 
      partsRs = map (foldr f z) parts `using` parList rdeepseq 
      res = foldr f z partsRs

上面的代碼不工作，因爲明顯 foldr相似，(a -> b -> b) -> b -> [a] -> b，的定義意味着輸入列表類型是（當然，也可以）從蓄壓器和結果類型不同。

例如，

1）foldr (+) 0 [1..10] =>列表類型=累加器類型（整數）

2）foldr (\i acc -> (i>5) && acc) True [1..10] =>列表類型（整數）！ =累加器類型（布爾）

所以，上面看我的代碼，所述映射將產生類型b ，然後將其作爲參數傳遞給第二foldr相似傳遞的列表。但第二個 foldr接受類型爲a的列表。所以，這是行不通的。

醜陋的解決辦法是爲提供不同類型的簽名parfoldr，例如 parfoldr :: (NFData a) => (a -> a -> a) -> a -> [a] -> a

這會工作，但那麼它是不完全等同於FOLDR。例如 1上面會做得很好，但不是例2 所以，問題1：如何定義parfoldr有相同類型的簽名爲foldr相似？

比較2倍：

input = [1..1000000] 
    seqfold = foldr (+) 0 
    parfold = parfoldr (+) 0

我得到的FOLL。雙核機上的時間：（無-threaded標誌）

$ ./test 
    seqfold: 4.99s 
    parfold: 25.16s

（上-threaded標誌）從這些測量

$ ./test 
    seqfold: 5.32s 
    parfold: 25.55s 
    $ ./test +RTS -N1 
    seqfold: 5.32s 
    parfold: 25.53s 
    $ ./test +RTS -N2 
    seqfold: 3.48s 
    parfold: 3.68s 
    $ ./test +RTS -N3 
    seqfold: 3.57s 
    parfold: 2.36s 
    $ ./test +RTS -N4 
    seqfold: 3.03s 
    parfold: 1.70s

觀察：

foldr相似，似乎給當核心數量增加時，運行時間減少。這是爲什麼？
parfold提供更好的運行時間爲N => 3

任何改進的建議和想法表示讚賞:)

來源

2011-07-23 vis

有趣的想法。不幸的是，據我所知，平行褶皺不以廣義形式存在...... – alternative

foldr通常不是可並行化的，因爲它的接口允許順序依賴性。爲了能夠按照您描述的方式重新排列計算，您需要將自己限制爲具有標識元素的關聯運算符。這被稱爲monoid，你實現的實質上是一個平行的mconcat。

來源

2011-07-23 16:05:05 hammar

你不能，不完全是，因爲你必須依賴於您可以拆分塊的屬性。這意味着，當然，你必須添加額外的類型限制...特殊情況是，如果您有f :: a -> a -> a作爲您的累積功能，並且f是關聯的。

因此，您將不得不提供兩個函數，一個用在塊中，另一個用於摺疊塊結果。您的原始版本只是該功能的加入。然後

parfoldr :: NFData a => (a -> a -> a) -> a -> [a] -> a 
parfoldr f = join $ parfoldr' f f 

parfoldr' :: NFData b => (a -> b -> b) -> (b -> c -> c) -> b -> c -> [a] -> c 
parfoldr' f g y z [] = z 
parfoldr' f g y z xs = foldr g z partsRs 
    where parts = chunk listChunkSize xs 
     partsRs = map (foldr f y) parts `using` parList rdeepseq

例2將

parfoldr' (\i acc -> (i>5) && acc) (&&) True True [1..10]

所有的一切，這不是是更噁心。

來源

2011-07-23 15:40:20 alternative

更多通用parfoldr比這

回答

相關問題