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 (3)
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í .
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
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.
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:
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.