Memoization в Haskell?
Любые указатели о том, как решить эффективно следующую функцию в Haskell для больших количеств (n > 108)
f(n) = max(n, f(n/2) + f(n/3) + f(n/4))
Я видел примеры memoization в Haskell для решения чисел Фибоначчи, которые включили вычисления (лениво) все числа Фибоначчи до необходимого n. Но в этом случае, для данного n, мы только должны вычислить очень немного промежуточных результатов.
Спасибо
2 ответа
Мы можем сделать это очень эффективно, создав структуру, которую мы можем индексировать за сублинейное время.
Но сначала,
{-# LANGUAGE BangPatterns #-}
import Data.Function (fix)
Давайте определим f , но заставим его использовать «открытую рекурсию», а не вызывать себя напрямую.
f :: (Int -> Int) -> Int -> Int
f mf 0 = 0
f mf n = max n $ mf (n `div` 2) +
mf (n `div` 3) +
mf (n `div` 4)
Вы можете получить незапоминанный f , используя fix f
Это позволит вам проверить, что f делает то, что вы имеете в виду для малых значений f , вызвав, например: fix f 123 = 144
Мы могли бы запомнить это, определив:
f_list :: [Int]
f_list = map (f faster_f) [0..]
faster_f :: Int -> Int
faster_f n = f_list !! n
Это работает достаточно хорошо и заменяет то, что должно было занять O (n ^ 3 ) время с чем-то, что запоминает промежуточные результаты.
Но чтобы найти мемоизированный ответ для mf , требуется линейное время. Это означает, что такие результаты, как:
*Main Data.List> faster_f 123801
248604
, допустимы, но результат не намного лучше масштабируется. Мы можем лучше!
Сначала давайте определим бесконечное дерево:
data Tree a = Tree (Tree a) a (Tree a)
instance Functor Tree where
fmap f (Tree l m r) = Tree (fmap f l) (f m) (fmap f r)
А затем мы определим способ индексирования в нем, чтобы мы могли найти узел с индексом n в O (log n ) вместо этого:
index :: Tree a -> Int -> a
index (Tree _ m _) 0 = m
index (Tree l _ r) n = case (n - 1) `divMod` 2 of
(q,0) -> index l q
(q,1) -> index r q
... и мы можем найти дерево, полное натуральных чисел, которое будет удобным, так что нам не придется возиться с этими индексами:
nats :: Tree Int
nats = go 0 1
where
go !n !s = Tree (go l s') n (go r s')
where
l = n + s
r = l + s
s' = s * 2
Поскольку мы можем индексировать, вы можете просто преобразовать дерево в список:
toList :: Tree a -> [a]
toList as = map (index as) [0..]
Вы можете проверить работу на данный момент, убедившись, что toList nats дает вам [0 ..]
Теперь
f_tree :: Tree Int
f_tree = fmap (f fastest_f) nats
fastest_f :: Int -> Int
fastest_f = index f_tree
работает так же, как с в приведенном выше списке, но вместо того, чтобы искать каждый узел за линейное время, можно отследить его за логарифмическое время.
Результат значительно быстрее:
*Main> fastest_f 12380192300
67652175206
*Main> fastest_f 12793129379123
120695231674999
На самом деле он настолько быстрее, что вы можете пройти и заменить Int на Integer выше и получить смехотворно большие ответы почти мгновенно
*Main> fastest_f' 1230891823091823018203123
93721573993600178112200489
*Main> fastest_f' 12308918230918230182031231231293810923
11097012733777002208302545289166620866358
Не самый эффективный способ, но мемоизирует:
f = 0 : [ g n | n <- [1..] ]
where g n = max n $ f!!(n `div` 2) + f!!(n `div` 3) + f!!(n `div` 4)
при запросе f !! 144 , проверяется, что f !! 143 существует, но его точное значение не вычислено. Он по-прежнему установлен как неизвестный результат вычислений. Вычисляются только точные значения.
Итак, изначально программа ничего не знает о том, сколько было вычислено.
f = ....
Когда мы делаем запрос f !! 12 , он начинает выполнять некоторое сопоставление с образцом:
f = 0 : g 1 : g 2 : g 3 : g 4 : g 5 : g 6 : g 7 : g 8 : g 9 : g 10 : g 11 : g 12 : ...
Теперь он начинает вычисление
f !! 12 = g 12 = max 12 $ f!!6 + f!!4 + f!!3
Это рекурсивно требует от f, поэтому мы вычисляем
f !! 6 = g 6 = max 6 $ f !! 3 + f !! 2 + f !! 1
f !! 3 = g 3 = max 3 $ f !! 1 + f !! 1 + f !! 0
f !! 1 = g 1 = max 1 $ f !! 0 + f !! 0 + f !! 0
f !! 0 = 0
Теперь мы можем скопировать некоторые
f !! 1 = g 1 = max 1 $ 0 + 0 + 0 = 1
Что означает, что программа теперь знает:
f = 0 : 1 : g 2 : g 3 : g 4 : g 5 : g 6 : g 7 : g 8 : g 9 : g 10 : g 11 : g 12 : ...
Продолжая просачиваться:
f !! 3 = g 3 = max 3 $ 1 + 1 + 0 = 3
Это означает, что программа теперь знает:
f = 0 : 1 : g 2 : 3 : g 4 : g 5 : g 6 : g 7 : g 8 : g 9 : g 10 : g 11 : g 12 : ...
Теперь мы продолжаем вычисление f !! 6 :
f !! 6 = g 6 = max 6 $ 3 + f !! 2 + 1
f !! 2 = g 2 = max 2 $ f !! 1 + f !! 0 + f !! 0 = max 2 $ 1 + 0 + 0 = 2
f !! 6 = g 6 = max 6 $ 3 + 2 + 1 = 6
Что означает, что программа сейчас знает:
f = 0 : 1 : 2 : 3 : g 4 : g 5 : 6 : g 7 : g 8 : g 9 : g 10 : g 11 : g 12 : ...
Теперь мы продолжаем вычисление f !! 12 :
f !! 12 = g 12 = max 12 $ 6 + f!!4 + 3
f !! 4 = g 4 = max 4 $ f !! 2 + f !! 1 + f !! 1 = max 4 $ 2 + 1 + 1 = 4
f !! 12 = g 12 = max 12 $ 6 + 4 + 3 = 13
Это означает, что теперь программа знает:
f = 0 : 1 : 2 : 3 : 4 : g 5 : 6 : g 7 : g 8 : g 9 : g 10 : g 11 : 13 : ...
Таким образом, вычисления выполняются довольно лениво. Программа знает какое-то значение для f !! 8 существует, что равно g 8 , но он не знает, что такое g 8 .