これより一般的なparfoldr

Question

私の目的は、並列折り畳み機能を持つことです。最初は、それが達成するために かなりまっすぐ進むのようで、これは私が考えていたものです：

まず コア（numCapabilities）の数に基づいて、パーティションに入力リストを破ります。次に、各パーティションにfoldrを適用します。この場合、 は、各パーティションの折りたたまれた値のリストになります。次に、リストに 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] =>リストタイプ（整数）！ は=アキュムレータ型（BOOL）

したがって、上記の私のコードを見て、地図は、第2のfoldrに引数として渡されたタイプb のリストを生成します。しかし、2番目の 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を取得します。デュアルコアマシン上で時間： （NO -threadedフラグ）

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

これらの測定から

$ ./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 

観測（-threadedオンフラグ）：

• foldrを与えるように思われますコアの数が増えるとランタイムが低下します。 なぜですか？

• parfoldはNのためのより良いランタイムを提供します=>改善のための3

任意の提案やアイデアは大歓迎です:)

Answer 1

foldrは、インタフェースがシーケンシャルな依存関係を許しているため、一般にはパラレル化できません。説明した方法で計算を再配置できるようにするには、結合要素を識別要素で限定する必要があります。これはmonoidとして知られており、実装したのは本質的には並列のmconcatです。

Answer 2

をすることはできません、ない正確に、あなたが依存する必要があるためチャンクを分割できるプロパティつまり、追加のタイプ制限を追加する必要があります。特別なケースは、累積関数としてf :: a -> a -> aがあり、fが結合型である場合です。

したがって、チャンクで使用される関数とチャンク結果をフォールドするために使用される関数の2つの関数を用意する必要があります。元のバージョンはこの関数の結合にすぎません。

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] 

だろう、これはがはるかに醜いものではありません。