我曾经问过类似的问题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)中学到的知识中,seqdeepseq对组成单子(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)(似乎可以接受内存分配)。对于线性渐近,此轮廓应平坦且恒定:

performance - 在固定空间和线性时间内迭代随机算法-LMLPHP

这是堆概要文件的外观:

performance - 在固定空间和线性时间内迭代随机算法-LMLPHP

我认为这样的程序应该在内存需求非常小的情况下运行,并且所花费的时间与迭代次数成正比。如何在Haskell中实现这一目标?

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

最佳答案

要考虑的一些事情:

  • 使用mersenne-random生成器,它通常比StdGen
  • 快100倍以上

    为了获得全面的原始性能,请编写一个自定义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模式,现在您的程序变为:
  • Using monad-mersenne-random

  • 我进行的另一项更改是对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
  • 原始:62.0s
  • 新功能:0.28秒

  • 也就是说, 220倍。

    既然iterateM取消装箱,堆也将变得更好。

    关于performance - 在固定空间和线性时间内迭代随机算法,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/3236442/

    10-12 03:58
    查看更多