# 性能 – 在固定空间和线性时间内迭代随机算法

```type RMonad = State StdGen

-- An example of random iteration step: one-dimensional random walk.
randStep :: (Num a) => a -> RMonad a
randStep x = do
rnd <- get
let (goRight,rnd') = random rnd :: (Bool, StdGen)
put rnd'
if goRight
then return (x+1)
else return (x-1)```

```-- Strict (?) iteration.
iterateM' :: (NFData a, Monad m) => Int -> (a -> m a) -> a -> m a
iterateM' 0 _ x = return \$!! x
iterateM' n f x = (f \$!! x) >>= iterateM' (n-1) f

-- Deeply stict function application.
(\$!!) :: (NFData a) => (a -> b) -> a -> b
f \$!! x = x `deepseq` f x```

```-- main seems to run in O(size*iters^2) time...
main :: IO ()
main = do
(size:iters:_) <- liftM (map read) getArgs
let start = take size \$repeat 0
rnd <- getStdGen
let end = flip evalState rnd \$iterateM' iters (mapM randStep) start
putStr . unlines \$histogram "%.2g" end 13```

quadratic time per update http://i29.tinypic.com/i59blv.png

heap profile with -hc http://i30.tinypic.com/124a8fc.png

>使用mersenne-random发电机,通常比StdGen快100倍

```import System.Random.Mersenne.Pure64

data R a = R !a {-# UNPACK #-}!PureMT

-- | The RMonad is just a specific instance of the State monad where the
--   state is just the PureMT PRNG state.
--
-- * Specialized to a known state type
--
newtype RMonad a = S { runState :: PureMT -> R a }

instance Monad RMonad where
{-# INLINE return #-}
return a = S \$\s -> R a s

{-# INLINE (>>=) #-}
m >>= k  = S \$\s -> case runState m s of
R a s' -> runState (k a) s'

{-# INLINE (>>) #-}
m >>  k  = S \$\s -> case runState m s of
R _ s' -> runState k s'

-- | Run function for the Rmonad.
runRmonad :: RMonad a -> PureMT -> R a
runRmonad (S m) s = m s

evalRmonad :: RMonad a -> PureMT -> a
evalRmonad r s = case runRmonad r s of R x _ -> x

-- An example of random iteration step: one-dimensional random walk.
randStep :: (Num a) => a -> RMonad a
randStep x = S \$\s -> case randomInt s of
(n, s') | n < 0     -> R (x+1) s'
| otherwise -> R (x-1) s'```

```{-# INLINE iterateM #-}
iterateM n f x = go n x
where
go 0 !x = return x
go n !x = f x >>= go (n-1)```

>原文：62.0s
>新增：0.28s