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

我曾经问过类似的问题 once.现在我会更具体一些.目的是学习一个Haskell成语来编写具有单体结果的迭代算法.特别地,这对于实现诸如遗传算法等的各种随机算法可能是有用的.

我写了一个示例程序,表明我在Haskell中使用这样的算法的问题.其完整来源于hpaste.

关键是随机更新一个元素(因此结果是在StdGen或其他monad中):

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)

然后需要更新许多元素,并重复该过程很多次.这里有一个问题.每一步都是一个monad动作(:: a – > m a),重复多次,重要的是有效地组合这样的操作(快速忘记上一步).从我从以前的quition (Composing monad actions with folds)中学到的东西,seq和deepseq帮助编写单体动作.所以我做:

-- 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

当我测量完成这个程序所需的时间时,看起来它相对于迭代次数(内存分配似乎是可以接受的)类似于O(N ^ 2).对于线性渐近,该轮廓应该是平坦的和恒定的:

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

这是一个堆配置文件的外观:

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

我假设这样一个程序应该运行着非常适中的内存要求,它应该需要与迭代次数成比例的时间.如何在Haskell中实现?

该示例的完整可运行源是here.

有些事情要考虑:

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

对于原始的全面表现,写一个自定义状态monad,像这样:

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'

像这样:http://hpaste.org/fastcgi/hpaste.fcgi/view?id=27414#a27414

它运行在恒定空间(模数[Double]你建立),并且比您的原始速度快8倍.

使用具有本地定义的特殊状态monad也显着优于Control.Monad.Strict.

这是堆看起来像,与你相同的参数:

请注意,它的速度约为10倍,并使用1/5的空间.大红色是你分配的双打列表.

灵感来自于您的问题,我在一个新的软件包:monad-mersenne-random中捕获了PureMT模式,现在您的程序成为:

> Using monad-mersenne-random

我所做的另一个改变是对worker / wrapper transform iterateM,使其能够被内联:

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

总的来说,这样可以让你的代码从K = 500,N = 30k

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

那就是220倍快.

堆也好一点了,现在这个iterateM是unboxes了.

相关文章
相关标签/搜索