17

我的目标是使用并行包parMap并行计算，但我还想为我的采样函数添加一些随机性。

如果没有随机性，我的计算只是一些数字运算，所以它是纯粹的，我可以使用parMap. 为了得到好的结果，我需要在每一步都取多个样本并对结果进行平均。抽样需要随机化。

一种解决方案可能是使用random 包，调用randoms然后在计算期间使用该列表（通过将纯惰性列表传递给计算，我将保持它的纯净）。不幸的是，这是一个非常慢的随机数生成器，我需要很多随机数，所以我更喜欢使用mwc-random或mersenne-random（尽管我不认为 mersenne-random 仍然保持不变）。

unsafePerformIO使用mwc-random 之类的东西来编写类似的函数是否安全randoms？像这样的东西：

randomsMWC :: Variate a => GenST s -> [a]
randomsMWC g = unsafePerformIO $ unsafeSTToIO $ randomsMWC' g
  where
  randomsMWC' g = do
    a  <- uniform g
    as <- unsafeInterleaveST $ randomsMWC' g
    return (a : as)

我是否需要转而使用并行数字生成器？或者我是否需要硬着头皮承认如果不使用慢速随机包我的算法根本不纯？

建议？谢谢！

4

4 回答 4

7

我hsrandom123在Github上有一个尚未完全准备好发布的软件包，这可能对这里有所帮助。我已经开始实现这个包，以便为并行计算提供合适的 RNG。它重新实现了random123C 库中的 Philox 和 Threefry RNG （那里也有一篇描述这些想法的论文）。

不过，我的库未发布是有原因的：虽然实际的 RNG 实现已经完成，并且似乎产生了与 C 版本相同的结果，但我一直未决定使用什么 Haskell 接口，并且该库几乎没有文档记录。如果您需要更多信息或帮助使用它，请随时与我联系。

于 2013-04-27T12:10:30.600 回答
7

如果具有单线程随机源对性能来说不是问题，您可以获得 mwc-random 的纯包装器

import Control.Monad.ST.Lazy
import Control.Monad
import System.Random.MWC

rList :: Variate a => Seed -> [a]
rList s = runST $ do
  g <- strictToLazyST $ restore s
  advance g

advance :: Variate a => Gen s -> ST s [a]
advance g = do
  x <- strictToLazyST $ uniform g
  xs <- x `seq` advance g
  return (x:xs)

这里rList取一个种子，然后确定性地懒惰地产生无限的懒惰数字流。我不确定这strictToLazyST是否真的安全，但似乎没有人反对。我没有做任何基准测试，但我怀疑这相当快。我认为这mwc-random是线程安全的，因为使用生成器编码的 explit 数据流，并且它可以在STmonad 中使用。邀请某人使用上面的 hack。我不认为这seq是必要的，但这让我不那么怀疑strictToLazyST我知道我有确定性的评估顺序（而且它仍然懒得工作）。

您仍然需要随机性（即IO）在某处生成真正的随机种子，但这应该可以让您保持大部分代码纯净，并让您将种子存储到文件中或在必要时重用它。

GHCI：

λ: gen <- create
λ: x <- save gen
λ: drop 1 $ take 10 $ rList x :: [Int]
[4443157817804305558,-6283633474236987377,3602072957429409483,
 -5035101780705339502,-925260411398682800,423158235494603307,
 -6981326876987356147,490540715145304360,-8184987036354194323]
于 2013-04-27T08:34:39.697 回答
5

我的猜测是mersenne-random不是线程安全的，因此使用 anyunsafe...和并行化会导致您从多个线程调用它时遇到问题。（另见GHC 手册第 8.2.4.1 节。）

需要随机性的函数不是纯粹的，它们需要一些随机性来源，它要么是外部的（硬件- 像设备采样噪声），因此绑定到IO，要么是伪随机的，它需要在计算过程中保持某种状态。无论哪种方式，它们都不能是纯 Haskell 函数。

我首先将您的要求分离到特定的单子类型类，例如

class Monad m => MonadParRand m where
    random      :: MTRandom a => m a
    parSequence :: [m a] -> m [a]

这将允许您编写主要代码而不受特定实现的约束。或者，如果你觉得大胆，你可以使用monad-parallel并定义类似的东西

class MonadParallel m => MonadParRand m where
    random      :: MTRandom a => m a

现在棘手的部分是如何定义randomand parSequence（或MonadParallel's bindM2）并使其快速。由于您可以控制bindM2，因此您可以管理线程的生成方式以及它们保持的状态。因此，您可以将缓冲区绑定到它从中抽取随机数的每个线程。如果缓冲区为空，它会同步调用 mersenne-random（或另一个IO基于数字的生成器），填充缓冲区并继续。

（如果你实现了类似的东西，那么从中创建一个独立的库会非常好。）

请注意，randomsfrom mersenne-random 已经用于unsafeInterleaveIO生成惰性列表，但我想说该列表只能从单个线程中使用。它也有改进的空间。如评论中所述，它使用unsafeInterleaveIO并且有一些开销：

这里有真正的开销。考虑急切地填充块并分段提取元素。

于 2013-04-27T08:12:17.763 回答
0

为了答案的完整性，让我解释一下我目前正在做什么来解决这个问题。

我没有尝试使计算变得纯粹，而是选择使用async包而不是parallel。

如果我决定将我当前的解决方案修改为纯粹的，我将首先尝试 Philip JF 建议的解决方案，因此我将他的答案标记为接受的答案。

我的下一个挑战是弄清楚如何近似优化工作分块，以便线程减少时间而不是让它花费更长的时间:)

于 2013-04-30T03:33:31.000 回答