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

Раньше я задавал подобный вопрос один раз . Теперь я буду более конкретным. Цель состоит в том, чтобы выучить идиому Haskell для написания итерационных алгоритмов с монадическими результатами. В частности, это может быть полезно для реализации всех видов рандомизированных алгоритмов, таких как генетические алгоритмы и тому подобное.

Я написал пример программы, которая демонстрирует мою проблему с такими алгоритмами в Haskell. Его полный источник находится на hpaste .

Ключевым моментом является случайное обновление элемента (таким образом, результат находится в State StdGen или некоторой другой монаде):

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)

А затем необходимо обновить множество элементов и повторить процесс много , много раз. И здесь есть проблема. Поскольку каждый шаг является действием монады (:: a -> m a), повторяющимся много раз, важно эффективно составлять такие действия (быстро забывая предыдущий шаг). Из того, что я узнал из моего предыдущего вопроса (Составление монадных действий со складками) , seq и deepseq, очень помогли составить монадические действия. Итак, я делаю:

-- 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) по количеству итераций (распределение памяти кажется приемлемым). Этот профиль должен быть плоским и постоянным для линейной асимптотики:

quadratic time per update

И вот так выглядит профиль кучи:

heap profile with -hc

Я предполагаю, что такая программа должна работать с очень скромными требованиями к памяти, и это должно занять время, пропорциональное количеству итераций. Как мне добиться этого в Хаскеле?

Полный работающий источник примера - здесь .

13
задан Glorfindel 2 August 2019 в 11:06
поделиться