8

我正在考虑利用并行性来解决我要解决的一个问题。问题大致是这样的：给定输入（点序列）找到最佳输出（由这些点组成的最大三角形、最长的线等）。在点序列中可以找到 3 种不同的“形状”，但是我只对具有“最佳分数”的那个感兴趣（通常是某种形式的“长度”乘以系数）。我们将形状称为 S1、S2、S3。

我有 2 种不同的算法来解决 S1 - 'S1a' 在 O(n 2 ) 中，'S1b' 大多表现更好，但最坏的情况大约是 O(n 4 )。

第一个问题：是否有一些简单的方法可以并行运行 S1a 和 S1b，使用先完成的一个并停止另一个？就我正在阅读文档而言，这可以使用一些 forkIO 进行编程，并在获得结果时终止线程 - 只是询问是否有更简单的东西？

第二个问题 - 更难：我这样调用优化函数：

optimize valueOfSx input

valueOfSx 对每个形状都是特定的，并返回一个“分数”（或对分数的猜测）一个可能的解决方案。优化调用此函数以找出最佳解决方案。我感兴趣的是：

s1 = optimize valueOfS1 input
s2 = optimize valueOfS2 input
s3 = optimize valueOfS3 input
<- maximum [s1,s2,s3]

但是，如果我知道 S1 的结果，我可以丢弃所有较小的解决方案，从而在不存在更好解决方案的情况下使 s2 和 s3 更快地收敛（或者至少丢弃最差的解决方案，从而提高空间效率）。我现在正在做的是：

zeroOn threshold f = decide .f
    where decide x = if (x < threshold) then 0 else x
s1 = optimize valueOfS1 input
s2 = optimize (zeroOn s1 valueOfS2) input
s3 = optimize (zeroOn (max s1 s2) valueOfS3) input

问题是：我能否以这样的方式并行运行例如 S2 和 S3，无论哪个先完成都会更新在另一个线程中运行的分数函数的“阈值”参数？某种意义上的东西：

threshold = 0
firstSolution = firstOf (optimize (zeroOn threshold valueOfS2), optimize (zeroOn threshold valueofS3))
update threshold from firstSolution
wait for second solution
4

2 回答 2

5

对于第一个问题，请查看 Conal Elliott 的unamb：http ://hackage.haskell.org/package/unamb

于 2010-02-05T10:33:11.203 回答
5

最终，任何解决方案都会在底层使用 ForkIO，因为您希望多个事务并行发生。甚至 Conal 的 unmb 也是这样工作的。

对于后者，您可能需要一个更复杂的 monad，它在偶尔检查 MVar 以获取单调发布的改进值之前分批运行一段时间，但交错（在一个线程内）的最简单答案是只编写一个 Partiality monad。

data Partial a = Return a | Partial (Partial a)

instance Monad Partial where
    return = Return
    Return a >>= f = f a
    Partial m >>= f = Partial (m >>= k)


run :: Partial a -> a
run (Partial m) = run m
run (Return a) = a

race :: Partial a -> Partial a -> Partial a
race (Return a) _ = a
race _ (Return b) = b
race (Partial m) (Partial n) = race m n

yield :: Partial ()
yield = Partial (Return ())

使用适当的 MonadFix 实例来处理递归或大量散布的 'yield' 调用，您可以在 Partial monad 中执行这两种操作并让它们竞争以获得确定性结果。

但在实践中，如果您想充分利用并行性，您需要定期更新和检查某种“改进”的 MVar。

像（即兴表演，抱歉，没有编译器方便！）：

import Control.Concurrent.MVar (newMVar, readMVar)
import Control.Parallel.Strategies (using, parList)
import GHC.IOBase (unsafeDupablePerformIO, unsafePerformIO)

diag x = (x,x)

parMax :: (Bounded a, Ord a) => [a] -> a
parMax xs = unsafePerformIO $ do
    threshold <- newMVar minBound
    let optimize x = unsafeDupablePerformIO $
        x `seq` modifyMVar threshold (return . diag . max x)
    return . maximum $ map optimize xs `using` parList

当然，它应该能够被重写以支持任何幂等可交换幺半群，而不仅仅是 max。

于 2010-02-05T22:24:48.597 回答