performance - qué - describa para que se utilizan los algoritmos aleatorios y ponga un 1 ejemplo

Iteración de un algoritmo aleatorizado en espacio fijo y tiempo lineal

Question

Solía ​​hacer una pregunta similar una vez . Ahora seré más específico. El objetivo es aprender un modismo Haskell para escribir algoritmos iterativos con resultados monádicos. En particular, esto podría ser útil para implementar todo tipo de algoritmos aleatorizados, como algoritmos genéticos y similares.

Escribí un programa de ejemplo que manifiesta mi problema con tales algoritmos en Haskell. Su fuente completa está en hpaste .

El punto clave es actualizar un elemento al azar (por lo tanto, el resultado es State StdGen o alguna otra mónada):

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)

Y luego uno necesita actualizar muchos elementos y repetir el proceso muchas, muchas veces. Y aquí hay un problema. Como cada paso es una acción de mónada ( :: a -> ma ), repetida muchas veces, es importante componer dichas acciones de manera efectiva (olvidando el paso anterior rápidamente). Por lo que aprendí de mi anterior quesion (Componer acciones de mónada con pliegues) , seq y deepseq ayudan mucho a componer acciones monádicas. Así que hago:

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

Sin duda es mejor que la composición perezosa. Desafortunadamente, no es suficiente.

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

Cuando medí el tiempo requerido para finalizar este programa, parece que es similar a O (N ^ 2) con respecto al número de iteraciones (la asignación de memoria parece aceptable). Este perfil debe ser plano y constante para asintóticos lineales:

tiempo cuadrático por actualización http://i29.tinypic.com/i59blv.png

Y así es como se ve un perfil de montón:

perfil de montón con -hc http://i30.tinypic.com/124a8fc.png

Supongo que dicho programa debería ejecutarse con requisitos de memoria muy modestos, y debería llevar un tiempo proporcional al número de iteraciones. ¿Cómo puedo lograr eso en Haskell?

La fuente completa ejecutable del ejemplo está aquí .

Answer 1

Este es probablemente un punto pequeño en comparación con las otras respuestas, pero ¿es correcta tu función ($ !!)?

Usted define

($!!) :: (NFData a) => (a -> b) -> a -> b
f $!! x = x `deepseq` f x

Esto evaluará completamente el argumento, sin embargo, el resultado de la función no necesariamente será evaluado en absoluto. Si quieres los $!! operador para aplicar la función y evaluar completamente el resultado, creo que debería ser:

($!!) :: (NFData b) => (a -> b) -> a -> b
f $!! x = let y = f x in y `deepseq` y

Answer 2

La importación de Control.Monad.State.Strict en lugar de Control.Monad.State produce una mejora significativa en el rendimiento. No estoy seguro de lo que está buscando en términos de asintonía, pero esto podría llevarlo allí.

Además, obtienes un aumento en el rendimiento al intercambiar el iterateM y el mapM para que no sigas atravesando la lista, no tienes que mantener el encabezado de la lista y no necesitas profundizar en el lista, pero solo fuerce los resultados individuales. Es decir:

let end = flip evalState rnd $ mapM (iterateM iters randStep) start

Si lo haces, entonces puedes cambiar iterateM para que sea mucho más idiomático también:

iterateM 0 _ x = return x
iterateM n f !x = f x >>= iterateM (n-1) f

Esto por supuesto requiere la extensión de lenguaje de patrones de explosión.

Answer 3

Algunas cosas a considerar:

• Utilice el generador mersenne-random , a menudo> 100 veces más rápido que StdGen

Para el rendimiento total sin procesar, escriba una mónada de estado personalizada, como esta:

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

Me gusta: http://hpaste.org/fastcgi/hpaste.fcgi/view?id=27414#a27414

Que se ejecuta en un espacio constante (modulo del [Double] que construyes), y es 8 veces más rápido que tu original.

El uso de una mónada de estado especializado con definición local también supera significativamente al Control.Monad.Strict.

Así es como se ve el montón, con los mismos parámetros que tú:

Tenga en cuenta que es aproximadamente 10 veces más rápido y utiliza 1/5 del espacio. La gran cosa roja es tu lista de dobles asignados.

Inspirado por su pregunta, capturé el patrón PureMT en un nuevo paquete: monad-mersenne-random , y ahora su programa se convierte en esto:

• Usando mónada-mersenne-al azar

El otro cambio que realicé fue para el trabajador / envoltura transformar iterateM, lo que permite que esté en línea:

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

En general, esto trae su código de, con K = 500, N = 30k

• Original: 62.0s
• Nuevo: 0.28s

Entonces eso es, 220 veces más rápido .

El montón también es un poco mejor, ahora iterateM unboxes.