Ackermann函数的一个问题是使用递归计算会导致非常深的递归栈。
递归深度与结果大约相等(取决于如何计数,可能多几层或少几层),不使用记忆化。不幸的是,如果按照调用树来填充备忘录表,记忆化并不能带来太多好处。
让我们跟踪计算 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
ack 2 $ ack 2 $ ack 1 $ ack 0 2
ack 2 $ ack 2 $ ack 1 3
ack 2 $ ack 2 $ ack 0 $ ack 1 2
ack 2 $ ack 2 $ ack 0 $ ack 0 $ ack 1 1
ack 2 $ ack 2 $ ack 0 $ ack 0 3
ack 2 $ ack 2 $ ack 0 4
ack 2 $ ack 2 5
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
ack 2 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 3
ack 2 $ ack 1 $ ack 1 $ ack 1 $ ack 1 5
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
ack 2 $ ack 1 $ ack 1 $ ack 1 $ ack 0 $ ack 0 5
ack 2 $ ack 1 $ ack 1 $ ack 1 $ ack 0 6
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
ack 2 $ ack 1 $ ack 1 $ ack 0 8
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
ack 2 $ ack 1 $ ack 0 $ ack 0 9
ack 2 $ ack 1 $ ack 0 10
ack 2 $ ack 1 11
ack 2 $ ack 0 $ ack 1 10
ack 2 $ ack 0 $ ack 0 $ ack 1 9
ack 2 $ ack 0 $ ack 0 11
ack 2 $ ack 0 12
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
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
ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 0 $ ack 0 13
ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 0 14
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
ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 0 16
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
ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 0 18
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
ack 1 $ ack 1 $ ack 1 $ ack 1 $ ack 0 20
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
ack 1 $ ack 1 $ ack 1 $ ack 0 $ ack 0 21
ack 1 $ ack 1 $ ack 1 $ ack 0 22
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
ack 1 $ ack 1 $ ack 0 $ ack 0 23
ack 1 $ ack 1 $ ack 0 24
ack 1 $ ack 1 25
ack 1 $ ack 0 $ ack 1 24
ack 1 $ ack 0 $ ack 0 $ ack 1 23
ack 1 $ ack 0 $ ack 0 25
ack 1 $ ack 0 26
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
,因此需要四个新的
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)
个嵌套thunk的堆栈。
为避免嵌套,你需要重新组织计算,例如强制按递增顺序计算新需要的
ack (m-1) 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)]]
这使得计算可以使用较小的堆栈(但仍需要大量的堆),需要定制的备忘录策略。
仅存储m >= 2
的ack m n
,并将ack 1 n
评估为已备忘可减少必要的内存,以至于使用不到1GB的堆即可计算出ack 3 20
(使用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
A(3,16)
可以在几秒钟内计算完成。 - Cartesius00