我有一系列问题想要并行评估。这些问题使用与此非常相似的简单表达式类型来表达:
-- Expressions are either a constant value or two expressions
-- combined using a certain operation
data Expr
= Const NumType
| Binary BinOp Expr Expr
-- The possible operations
data BinOp = Add | Sub | Mul | Div
deriving (Eq)
这些表达式是动态构建的,并且应该计算出某个可能有效或无效的结果。这表示为一个 monad,用于在遇到无效结果时停止计算。
data Result a
= Val { val :: a }
| Exc { exc :: String }
instance Monad Result where
return = Val
(Exc e) >>= _ = (Exc e)
(Val v) >>= g = g v
为了确定每个已解决问题的值,我有两个相关函数:
eval :: Expr -> Result NumType
score :: Expr -> NumType
最后我有了解决函数,它将返回 [Expr]
。这导致我的主要功能目前如下所示:
main :: IO ()
main = do
strAvailableNumbers <- getLine
strTargetNumber <- getLine
let numbers = parseList strAvailableNumbers
target = parseTargetNumber strTargetNumber in
sequence $ map (print) $
solveHeuristic1 (Problem target numbers) [Add] [Sub] ++
solveHeuristic2 (Problem target numbers)
return ()
基本思想是我从标准输入读取数字列表和目标数字,然后在标准输出上打印表达式。
但是我有两个问题想要解决,但我不太确定它们之间的相关性:
这些启发式算法完全不了解彼此,因此不知道
score
是否有效。他们的解决方案的比例高于任何其他解决方案。我想向 map 函数引入某种状态,以仅打印新的Expr
如果它的分数更高,则Expr
之前打印过。我想并行执行这些计算,并尝试使用
(parMap rseq)
来实现。而不是map
,使用-threaded
进行编译选项并使用+RTS -N2
运行它。结果是运行时间从 5 秒增加到 7 秒。虽然不是我所期望的time
说明CPU利用率较高。我想我没有正确使用parMap
或者使用++
做错事。那么我将如何并行运行一个独立函数列表,每个函数返回一个元素列表?
更新:创建了 gist with complete source code .
最佳答案
这里的问题是,使用 seq
评估 IO
操作几乎没有任何作用。所以你只是按顺序运行,开销稍多一些。
你可以折射事物,使它们再次纯净
main :: IO ()
main = do
mapM_ (`seq` print "found it") -- make sure we're not
-- benchmarking printing stuff
. concat
. parMap rdeepseq (solve [1..10000000])
$ [42, 42]
return ()
并添加 NFData
实例以使用 rdeepseq
来全面评估事物
instance NFData BinOp -- Binop is just an enum, WHNF = NF
instance NFData Expr where
rnf (Const a) = a `deepseq` ()
rnf (Binary b e1 e2) = b `deepseq` e1 `deepseq` e2 `deepseq` ()
现在,如果我们运行它,我们会得到...一个 stackoverflow。我足够大地增加了我们搜索的大小,以便实际上使其花费足够长的时间来值得进行基准测试,现在将这两个结构完全加载到内存中将会破坏堆栈。将堆栈大小增加到不会破坏所有内容的程度,使我们使用 -N2
的运行速度比不使用时快 40%(3 秒与 5 秒)。我会考虑预期的结果。运行此程序时,我可以直观地看到 2 个核心短暂上升至 100%。
最终编译顺序
> ghc -O2 -threaded -rtsops bench.hs
> ./bench +RTS -K10000000 -N2
关于haskell - 并行最大计算,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19819428/