4

问题

我有一个有限的值列表：

values :: [A]

...以及对这些值的昂贵但纯粹的功能：

expensiveFunction :: A -> Maybe B

如何在每个值上并行运行该函数，并且只返回n完成的第一个结果Just并停止计算未完成的结果？

takeJustsPar :: (NFData b) => Int -> (a -> Maybe b) -> [a] -> [b]
takeJustsPar maxJusts f as = ???

动机

我知道如何使用Control.Concurrent.，但我想尝试使用 Haskell 的并行功能。此外，我能找到的（很少的）文献似乎表明，Haskell 的并行特性使得产生并行计算和在众多功能之间调整工作负载变得更便宜。

4

1 回答 1

4

我尝试了两种解决方案。第一个使用Par单子（即Control.Monad.Par）：

import Control.Monad.Par (Par, NFData)
import Control.Monad.Par.Combinator (parMap)
import Data.Maybe (catMaybes)
import Data.List.Split (chunksOf)

takeJustsPar :: (NFData b) => Int -> Int -> (a -> Maybe b) -> [a] -> Par [b]
takeJustsPar n chunkSize f as = go n (chunksOf chunkSize as) where
    go _ [] = return []
    go 0 _  = return []
    go numNeeded (chunk:chunks) = do
        evaluatedChunk <- parMap f chunk
        let results      = catMaybes evaluatedChunk
            numFound     = length results
            numRemaining = numNeeded - numFound
        fmap (results ++) $ go numRemaining chunks

使用的第二次尝试Control.Parallel.Strategies：

import Control.Parallel.Strategies
import Data.List.Split (chunksOf)

chunkPar :: (NFData a) => Int -> Int -> [a] -> [a]
chunkPar innerSize outerSize as
  = concat ((chunksOf innerSize as) `using` (parBuffer outerSize rdeepseq))

后者最终变得更加可组合，因为我可以写：

take n $ catMaybes $ chunkPar 1000 10 $ map expensiveFunction xs

...而不是将takeandcatMaybes行为融入并行策略。

后一种解决方案也提供了近乎完美的利用。在我测试的令人尴尬的并行问题上，它为 8 个内核提供了 99% 的利用率。我没有测试Parmonad 的利用率，因为我是借用同事的电脑，不想在我满意的性能时浪费他们的时间Control.Parallel.Strategies。

所以答案是使用Control.Parallel.Strategies，它提供了更多的可组合行为和出色的多核利用率。

于 2012-10-18T18:04:54.847 回答