Итерация рандомизированного алгоритма в фиксированном пространстве и линейном времени
f(n) принадлежит O(n), если существует положительный k, поскольку f(n)<=k*n
f(n) принадлежит Θ(n), если существует положительный k1, k2 как k1*n<=f(n)<=k2*n
3 ответа
Некоторые вещи, которые следует рассмотреть:
- Используйте mersenne-random генератор, он часто >100x быстрее, чем StdGen
Для сырой тотальной производительности напишите пользовательскую монаду State, например, так:
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 раз быстрее, чем ваша оригинальная.
Использование специализированной монады состояний с локальным определением также значительно превосходит Control.Monad.Strict.
Вот как выглядит куча с теми же параметрами, что и у вас:
Обратите внимание, что она примерно в 10 раз быстрее и использует 1/5 часть пространства. Большая красная штука - это ваш список выделяемых двойников.
Вдохновленный вашим вопросом, я запечатлел паттерн PureMT в новом пакете: monad-mersenne-random, и теперь ваша программа выглядит так:
Другим изменением, которое я сделал, было рабочее/оберточное преобразование 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
То есть, 220x быстрее.
Куча тоже немного лучше, теперь, когда iterateM распаковывается.
Это, вероятно, мелочь по сравнению с другими ответами, но верна ли ваша функция ($ !!)?
Вы определяете
($!!) :: (NFData a) => (a -> b) -> a -> b
f $!! x = x `deepseq` f x
Это полностью оценит аргумент, однако результат функции не обязательно будет оцениваться вообще. Если вы хотите $ !! , чтобы применить функцию и полностью оценить результат, я думаю, он должен быть таким:
($!!) :: (NFData b) => (a -> b) -> a -> b
f $!! x = let y = f x in y `deepseq` y
Импорт Control.Monad.State.Strict вместо Control.Monad.State дает значительное улучшение производительности. Не уверен, что вы ищете асимптотику, но это может помочь вам.
Кроме того, вы получите прирост производительности, поменяв местами iterateM и mapM, чтобы не обходить список, не держаться за голову списка и не углубляться в список, а просто принудительно обрабатывать отдельные результаты. Т.е.:
let end = flip evalState rnd $ mapM (iterateM iters randStep) start
Если вы сделаете так, то вы сможете изменить iterateM так, чтобы он стал гораздо более идиоматичным:
iterateM 0 _ x = return x
iterateM n f !x = f x >>= iterateM (n-1) f
Это, конечно, требует расширения языка bang patterns.