我的目标是有一个并行的 foldr 功能。起初,似乎
相当直接地实现,这就是我的想法:
首先根据输入列表的数量将输入列表分解为分区
核心 (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
上面的代码不起作用,因为显然定义
文件夹,
(a -> b -> b) -> b -> [a] -> b
, 意味着输入列表类型(嗯,可以)不同于累加器和结果类型。
例如,
1)
foldr (+) 0 [1..10]
=> 列表类型 = 累加器类型(整数)2)
foldr (\i acc -> (i>5) && acc) True [1..10]
=> 列表类型(整数)!= 累加器类型 (Bool)
所以,看看我上面的代码, map 会生成一个
b
类型的列表。然后将其作为参数传递给第二个文件夹。但是第二个
foldr 接受类型列表
a
.所以,那是行不通的。一个丑陋的解决方案是为
parfoldr,例如
parfoldr :: (NFData a) => (a -> a -> a) -> a -> [a] -> a
这将起作用,但它并不完全等同于 foldr。例子
上面的 1 就可以了,但不是示例 2。
所以,问题 1 是:如何定义 parfoldr 以具有相同的类型签名
作为文件夹?
比较2折:
input = [1..1000000]
seqfold = foldr (+) 0
parfold = parfoldr (+) 0
我明白了。双核机器上的时间:
(无线程标志)
$ ./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
从这些测量中观察到:
这是为什么?
任何改进的建议和想法表示赞赏:)
最佳答案
foldr
通常不可并行化,因为它的接口(interface)允许顺序依赖。为了能够以您描述的方式重新排列计算,您需要将自己限制为具有标识元素的关联运算符。这被称为 monoid ,而您实现的基本上是并行的 mconcat
.
关于haskell - 比这更通用的 parfoldr,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6801351/