Итерация рандомизированного алгоритма в фиксированном пространстве и линейное время

Ответ 1

Некоторые вещи, которые следует учитывать:

• Используйте генератор mersenne-random, он часто > 100x быстрее, чем StdGen

Для сырой тотальной производительности напишите пользовательскую монаду штата, например:

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, и теперь ваша программа станет следующей:

• Использование monad-mersenne-random

Другое изменение, которое я сделал, это преобразование work/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.28s

Итак, быстрее 220 раз.

Куча тоже немного лучше, теперь iterateM unboxes.

Ответ 2

Импортировать 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

Для этого, конечно, требуется расширение языка шаблонов.

Ответ 3

Это, вероятно, небольшая точка по сравнению с другими ответами, но верно ли ваша функция ($!!)?

Вы определяете

($!!) :: (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