17

私の目標はparMap、parallel パッケージを使用して計算を並列化することですが、サンプリング関数にランダム性を少し追加したいと思います。

ランダム性がなければ、私の計算は単純に数を計算するだけなので、それは純粋であり、 を使用できますparMap。良い結果を得るには、各ステップで複数のサンプルを取得し、結果を平均化する必要があります。サンプリングはランダム化する必要があります。

1 つの解決策は、ランダム パッケージを使用し、呼び出しrandomsてから、計算中にそのリストを使用することです (純粋な遅延リストを計算に渡すことで、純粋に保ちます)。残念ながら、これは非常に遅い乱数ジェネレーターであり、大量の乱数が必要なので、mwc-randomまたはmersenne- random のいずれかを使用することをお勧めします(ただし、me​​rsenne-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

シングル スレッド ソースのランダム性がパフォーマンスの問題にならない場合は、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で使用できると思います。ST上記のハックを使用するように誰かを招待する。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

randomここで注意が必要なのは、 and parSequence(またはMonadParallel's bindM2)の両方を定義して高速化する方法です。を制御しているbindM2ため、スレッドがどのように生成され、どのような状態を維持するかを管理できます。したがって、乱数を引き出す各スレッドにバッファをバインドできます。バッファーが空の場合、mersenne-random (または別のIOに基づく数値ジェネレーター) への同期呼び出しを行い、バッファーを埋めて続行します。

（そのようなものを実装する場合、それからスタンドアロンのライブラリを作成すると非常に便利です。）

randomsfrom mersenne-random はすでに遅延リストを生成するために使用されていることに注意してください。ただしunsafeInterleaveIO、リストは単一のスレッドからのみ消費されることを意図していると思います。また、改善の余地もあります。コメントに記載されているように、使用しunsafeInterleaveIO、オーバーヘッドがあります。

ここには実際のオーバーヘッドがあります。チャンクを熱心に埋め、要素を断片的に抽出することを検討してください。

于 2013-04-27T08:12:17.763 に答える