Мемоизация функции Аккермана
Я хотел бы вычислить A(3, 20) значение функции Аккермана (см. Википедия), которая должна быть 2^23 - 3 = 8388605 с помощью Data.MemoCombinators, Мой код:
{-# LANGUAGE BangPatterns #-}
import Data.MemoCombinators as Memo
ack = Memo.memo2 Memo.integral Memo.integral ack'
where
ack' 0 !n = n+1
ack' !m 0 = ack (m-1) 1
ack' !m !n = ack (m-1) $! (ack m (n-1))
main = print $ ack 3 20
Но это заканчивается ошибкой переполнения стека;-) Может ли она быть настроена или цепочка вычислений действительно такая длинная, и даже запоминание не может помочь?
3 ответа
Одна из точек функции Аккермана заключается в том, что ее рекурсивное вычисление приводит к очень глубокой рекурсии.
Глубина рекурсии примерно равна результату (в зависимости от того, как вы считаете, это несколько или более уровней) без меоизации. К сожалению, запоминание мало что дает, если вы заполняете таблицу напоминаний в соответствии с деревом вызовов.
Давайте следить за вычислением ack 3 2:
ack 3 2
ack 2 $ ack 3 1
ack 2 $ ack 2 $ ack 3 0
ack 2 $ ack 2 $ ack 2 1
ack 2 $ ack 2 $ ack 1 $ ack 2 0
ack 2 $ ack 2 $ ack 1 $ ack 1 1
ack 2 $ ack 2 $ ack 1 $ ack 0 $ ack 1 0
ack 2 $ ack 2 $ ack 1 $ ack 0 $ ack 0 1 -- here's the first value we can compute and put in the map
ack 2 $ ack 2 $ ack 1 $ ack 0 2 -- next three, (0,2) -> 3, (1,1)->3 and (2,0)->3
ack 2 $ ack 2 $ ack 1 3 -- need to unfold that
ack 2 $ ack 2 $ ack 0 $ ack 1 2
ack 2 $ ack 2 $ ack 0 $ ack 0 $ ack 1 1 -- we know that, it's 3
ack 2 $ ack 2 $ ack 0 $ ack 0 3 -- okay, easy (0,3)->4, (1,2)->4
ack 2 $ ack 2 $ ack 0 4 -- (0,4)->5, (1,3)->5, (2,1)->5
ack 2 $ ack 2 5 -- unfold
ack 2 $ ack 1 $ ack 2 4
ack 2 $ ack 1 $ ack 1 $ ack 2 3
ack 2 $ ack 1 $ ack 1 $ ack 1 $ ack 2 2
ack 2 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 2 1
ack 2 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 2 0 -- we know that one, 3
ack 2 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 3 -- that one too, it's 5
ack 2 $ ack 1 $ ack 1 $ ack 1 $ ack 1 5 -- but not that
ack 2 $ ack 1 $ ack 1 $ ack 1 $ ack 0 $ ack 1 4
ack 2 $ ack 1 $ ack 1 $ ack 1 $ ack 0 $ ack 0 $ ack 1 3 -- look up
ack 2 $ ack 1 $ ack 1 $ ack 1 $ ack 0 $ ack 0 5 -- easy (0,5)->6
ack 2 $ ack 1 $ ack 1 $ ack 1 $ ack 0 6 -- now (1,5)->7 is known too, and (2,2)->7
ack 2 $ ack 1 $ ack 1 $ ack 1 7
ack 2 $ ack 1 $ ack 1 $ ack 0 $ ack 1 6
ack 2 $ ack 1 $ ack 1 $ ack 0 $ ack 0 $ ack 1 5
ack 2 $ ack 1 $ ack 1 $ ack 0 $ ack 0 7 -- here (1,6)->8 becomes known
ack 2 $ ack 1 $ ack 1 $ ack 0 8 -- and here (1,7)->9, (2,3)->9
ack 2 $ ack 1 $ ack 1 9
ack 2 $ ack 1 $ ack 0 $ ack 1 8
ack 2 $ ack 1 $ ack 0 $ ack 0 $ ack 1 7 -- known
ack 2 $ ack 1 $ ack 0 $ ack 0 9 -- here we can add (1,8)->10
ack 2 $ ack 1 $ ack 0 10 -- and (1,9)->11, (2,4)->11
ack 2 $ ack 1 11
ack 2 $ ack 0 $ ack 1 10
ack 2 $ ack 0 $ ack 0 $ ack 1 9 -- known
ack 2 $ ack 0 $ ack 0 11 -- (1,10)->12
ack 2 $ ack 0 12 -- (1,11)->13, (2,5)->13
ack 2 13
ack 1 $ ack 2 12
ack 1 $ ack 1 $ ack 2 11
ack 1 $ ack 1 $ ack 1 $ ack 2 10
ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 2 9
ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 2 8
ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 2 7
ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 2 6
ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 2 5 -- uff
ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 13
ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 0 $ ack 1 12
ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 0 $ ack 0 $ ack 1 11 -- uff
ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 0 $ ack 0 13 -- (1,12)->14
ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 0 14 -- (1,13)->15, (2,6)->15
ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 15
ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 0 $ ack 1 14
ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 0 $ ack 0 $ ack 1 13
ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 0 $ ack 0 15 -- (1,14)->16
ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 0 16 -- (1,15)->17, (2,7)->17
ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 17
ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 0 $ ack 1 16
ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 0 $ ack 0 $ ack 1 15
ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 0 $ ack 0 17 -- (1,16)->18
ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 0 18 -- (1,17)->19, (2,8)->19
ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 19
ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 0 $ ack 1 18
ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 0 $ ack 0 $ ack 1 17
ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 0 $ ack 0 19 -- (1,18)->20
ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 0 20 -- (1,19)->21, (2,9)->21
ack 1 $ ack 1 $ ack 1 $ ack 1 21
ack 1 $ ack 1 $ ack 1 $ ack 0 $ ack 1 20
ack 1 $ ack 1 $ ack 1 $ ack 0 $ ack 0 $ ack 1 19 -- known
ack 1 $ ack 1 $ ack 1 $ ack 0 $ ack 0 21 -- (1,20)->22
ack 1 $ ack 1 $ ack 1 $ ack 0 22 -- (1,21)->23, (2,10)->23
ack 1 $ ack 1 $ ack 1 23
ack 1 $ ack 1 $ ack 0 $ ack 1 22
ack 1 $ ack 1 $ ack 0 $ ack 0 $ ack 1 21 -- known
ack 1 $ ack 1 $ ack 0 $ ack 0 23 -- (1,22)->24
ack 1 $ ack 1 $ ack 0 24 -- (1,23)->25, (2,11)->25
ack 1 $ ack 1 25
ack 1 $ ack 0 $ ack 1 24
ack 1 $ ack 0 $ ack 0 $ ack 1 23 -- known
ack 1 $ ack 0 $ ack 0 25 -- (1,24)->26
ack 1 $ ack 0 26 -- (1,25)->27, (2,12)-> 27
ack 1 27
ack 0 $ ack 1 26
ack 0 $ ack 0 $ ack 1 25
ack 0 $ ack 0 27
ack 0 28
29
Поэтому, когда вам нужно вычислить новое (пока не известно) ack 1 nнужно вычислить два новых ack 0 n, а когда вам нужен новый ack 2 nнужно два новых ack 1 nи, следовательно, 4 новых ack 0 nвот и все не слишком драматично.
Но когда вам нужен новый ack 3 n, тебе нужно ack 3 (n-1) - ack 3 (n-2) новый ack 2 k, Все сказано, после того, как вы вычислили ack 3 kнужно вычислить 2^(k+2) новые значения ack 2 nи по структуре вызова, это вложенные вызовы, так что вы получаете стек 2^(k+2) вложенные громоотводы.
Чтобы избежать этого вложения, вам необходимо реструктурировать вычисления, например, путем принудительного ack (m-1) k в порядке возрастания k,
ack' m 1 = ack (m-1) $! ack (m-1) 1
ack' m n = foldl1' max [ack (m-1) k | k <- [ack m (n-2) .. ack m (n-1)]]
что позволяет вычислениям (медленно) выполняться с небольшим стеком (но ему все еще требуется огромная куча, кажется, что нужна специально разработанная стратегия запоминания).
Хранение только ack m n за m >= 2и оценивая ack 1 n как будто это запомнилось, уменьшает необходимую память достаточно далеко, чтобы вычисление ack 3 20 заканчивается использование менее 1 ГБ кучи (с использованием Int вместо Integer заставляет его работать примерно вдвое быстрее):
{-# LANGUAGE BangPatterns #-}
module Main (main) where
import qualified Data.Map as M
import Control.Monad.State.Strict
import Control.Monad
type Table = M.Map (Integer,Integer) Integer
ack :: Integer -> Integer -> State Table Integer
ack 0 n = return (n+1)
ack 1 n = return (n+2)
ack m 0 = ack (m-1) 1
ack m 1 = do
!n <- ack (m-1) 1
ack (m-1) n
ack m n = do
mb <- gets (M.lookup (m,n))
case mb of
Just v -> return v
Nothing -> do
!s <- ack m (n-2)
!t <- ack m (n-1)
let foo a b = do
c <- ack (m-1) b
let d = max a c
return $! d
!v <- foldM foo 0 [s .. t]
mp <- get
put $! M.insert (m,n) v mp
return v
main :: IO ()
main = print $ evalState (ack 3 20) M.empty
Если у вас достаточно памяти, попробуйте увеличить размер стека:
$ ghc -O2 -rtsopts source.hs
$ ./source +RTS -K128M
Функция рекурсивная, и вы правильно ее реализовали. Я думаю, что вы просто попали на вершину стека. Это не удивительно, потому что количество рекурсий увеличивается экспоненциально, когда m=3, Это неизбежно, что вы исчерпаете стек. Увеличение общего объема памяти не поможет, если вы не сделаете другую реализацию, которая использует какой-либо метод, отличный от рекурсии.
Поэтому, чтобы ответить на ваш вопрос, вам понадобится другая форма памяти, чтобы продолжить. Или, по крайней мере, вам нужно использовать ОЗУ совсем по-другому.