Zenn
🎲

Haskellの最近の乱数生成事情について

2021/01/31に公開
Haskell
random
rng
tech

あらすじ

Haskellでの乱数生成ライブラリは長らく群雄割拠の時代が続いていました。
その理由は、公式のrandomパッケージの使い勝手がすこぶる悪かったため、
各々が独自のインターフェースでまともな乱数生成ライブラリを公開していました。

その時代は、random-1.2の登場により終わりを迎えました。
これからはrandomパッケージを使えば基本的に問題ないでしょう。

https://hackage.haskell.org/package/random-1.2.0

Before random-1.2

Haskellの公式の乱数生成ライブラリがrandomだったのですが、
このライブラリは System.Randomといういかにも標準的なモジュールを提供している割に使い物になりませんでした。

そのため、

などのライブラリが独自のインターフェースを提供していました。

randomの問題は以下のような物でした。

インターフェースがイケてない

RandomeGen gという型クラスが乱数生成器を抽象化していたのですが、
以下のような定義になっていました。

class RandomGen g where
  next :: g -> (Int, g)
  split :: g -> (g, g)
  genRange :: g -> (Int, Int)

この型クラスには以下のような問題点がありました。

  • 乱数をInt一個単位でしか生成できない
    • Intは32/64bitで値域が変わるデータ型である
  • nextが返すIntの値はgenRangeの間の一様分布であり、Int全体の一様分布ではない
    • このせいで一様分布の生成が極めて遅くなります。（後述）
  • 純粋な乱数生成器しかモデルできない

パフォーマンスが低い

このIssueによると乱数生成器のスループットは 5~8 MB/s程度だそうです。
これは極めて遅いスループットです。

いくつか原因が考えられるのですが、筆者の考えではこうです。

一様分布を生成する型クラスが Random型クラスなのですが、以下のような実装になっていました。

instance Random Integer where
  randomR ival g = randomIvalInteger ival g
  random g       = randomR (toInteger (minBound::Int), toInteger (maxBound::Int)) g

instance Random Int        where randomR = randomIvalIntegral; random = randomBounded
instance Random Int8       where randomR = randomIvalIntegral; random = randomBounded
instance Random Int16      where randomR = randomIvalIntegral; random = randomBounded
instance Random Int32      where randomR = randomIvalIntegral; random = randomBounded
instance Random Int64      where randomR = randomIvalIntegral; random = randomBounded

この実装でInt型の乱数を一個生成するのにどのような手順になっているかというと

(簡単のため(0, size-1)を乱数生成器の値域としましょう)

  1. Int型の値域 (minBound, maxBound)をInteger型に変換
  2. (0, maxBound - minBound + 1)を十分カバーできるよう、乱数をr1,...rkを生成する
  3. R = ((r1 * size + r2)* size + r3) ... + rkとして、 R % (maxBound - minBound + 1) + minBoundを乱数として返す

という手順になります。正気か？

Int一つ生成するのに回りくどいことをしすぎです。

大抵の乱数生成器は 2^{8k} の一様分布を簡単に生成できるように作られているはずなのに全くその利点を生かせない実装になっています。
これもRandomGen型クラスの抽象化がイケてないことが間接的な原因です。

Qualityが低い

これについては筆者はあまり詳しくないのですが、

  • 標準の乱数生成器が乱数テストに通らない 参照
  • splitで分割された乱数生成器が統計的に互いに独立にならない　参照

にならないという問題があったそうです。

splitmixの登場

そんな中、splitmixという乱数生成器が登場しました。

https://dl.acm.org/doi/10.1145/2660193.2660195

このライブラリは

  • 純粋である
  • splitが統計的に独立であり、品質もよい
  • 非常に高速である 比較記事

という非常に良い性質を持っていました。
そのため、　標準の乱数生成器をsplitmixに置き換えることになりました。

https://github.com/haskell/random/pull/62

After random-1.2

random-1.2で変わった点は大きく以下の4つです。

  • 標準の乱数生成器がsplitmixになった
  • RandomGen型クラスがまともになった
  • Statefulな乱数生成器を抽象化するStatefulGen型クラスが追加された。
  • Uniform UniformRangeクラスが追加された。

標準の乱数生成器がsplitmixになった

-- | The standard pseudo-random number generator.
newtype StdGen = StdGen { unStdGen :: SM.SMGen }
  deriving (Show, RandomGen, NFData)

RandomGen型クラスがまともになった

class RandomGen g where
  genWord8  :: g -> (Word8, g)
  genWord16 :: g -> (Word16, g)
  genWord32 :: g -> (Word32, g)
  genWord64 :: g -> (Word64, g)
  genWord32R :: Word32 -> g -> (Word32, g)
  genWord64R :: Word64 -> g -> (Word64, g)
  genShortByteString :: Int -> g -> (ShortByteString, g)
  -- deprecated
  next :: g -> (Int, g)
  genRange :: g -> (Int, Int)

このように、生成される乱数が2^{8k}上の一様分布となったため、扱いやすくなりました。

Statefulな乱数生成器を抽象化するStatefulGen型クラスが追加された

これからはmwc-randomなどのstatefulな乱数生成器もStatefulGen型クラスで
抽象化できるため乱数生成器の切り替えが簡単になるでしょう。

class Monad m => StatefulGen g m where
  uniformWord8 :: g -> Word8
  uniformWord16 :: g -> m Word16
  uniformWord32 :: g -> m Word32
  uniformWord64 :: g -> m Word64
  uniformWord32R :: Word32 -> g -> m Word32
  uniformWord64R :: Word64 -> g -> m Word64
  uniformShortByteString :: Int -> g -> m ShortByteString

Random型クラスをまともにしたUniform UniformRangeクラスが追加された。

Random型クラスはUniform, UniformRange型クラスに置き換わりました。

class Uniform a where
  uniformM :: StatefulGen g m => g -> m a
  
class UniformRange a where
  uniformRM :: (a, a) -> g -> m a

一様分布生成アルゴリズムもIntegerを経由する物ではなくて、
ビットマスクを用いたアルゴリズムに変わっています。

まとめ

random-1.2は

  • splitmixを採用したことで最速かつ品質も良くなった
  • インターフェースもまともになった

のでこれからはこのライブラリを使っておけば問題なさそうです！

Discussion