我曾经问过类似的问题once。现在我将更具体。目的是学习Haskell惯用法来编写具有单子(monad)结果的迭代算法。特别地,这对于实现各种随机算法(例如遗传算法等)可能是有用的。
我编写了一个示例程序,用Haskell证明了此类算法的问题。它的完整来源在hpaste上。
关键是随机更新元素(因此结果以State 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
),已重复了很多次,因此有效地编写此类操作(迅速忘记上一步)非常重要。从我以前的问题(Composing monad actions with folds)中学到的知识中,seq
和deepseq
对组成单子(monad)动作很有帮助。所以我做:-- 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)(似乎可以接受内存分配)。对于线性渐近,此轮廓应平坦且恒定:
这是堆概要文件的外观:
我认为这样的程序应该在内存需求非常小的情况下运行,并且所花费的时间与迭代次数成正比。如何在Haskell中实现这一目标?
该示例的完整可运行源是here。
最佳答案
要考虑的一些事情:
为了获得全面的原始性能,请编写一个自定义State 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模式,现在您的程序变为:
我进行的另一项更改是对worker / wrapper转换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
也就是说,快 220倍。
既然iterateM取消装箱,堆也将变得更好。
关于performance - 在固定空间和线性时间内迭代随机算法,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/3236442/