haskell - Haskell 中的记忆化？

Question

有关如何在 Haskell 中针对大数有效求解以下函数的任何指示 (n > 108)

f(n) = max(n, f(n/2) + f(n/3) + f(n/4))

我见过用 Haskell 记忆化来解决斐波那契数列的例子数字，涉及(惰性地)计算所有斐波那契数直到所需的n。但在这种情况下，对于给定的 n，我们只需要计算很少的中间结果。

谢谢

Answer 1

我们可以通过创建一个可以在亚线性时间内索引的结构来非常有效地做到这一点。

但首先，

{-# 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)

您可以使用fix f获得未内存的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)

然后我们将定义一种对其进行索引的方法，这样我们就可以在 O(log n) 时间内找到索引为 n 的节点: p>

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

对于实现基于树的记忆化的开箱即用库，请使用 MemoTrie :

$ stack repl --package MemoTrie

Prelude> import Data.MemoTrie
Prelude Data.MemoTrie> :set -XLambdaCase
Prelude Data.MemoTrie> :{
Prelude Data.MemoTrie| fastest_f' :: Integer -> Integer
Prelude Data.MemoTrie| fastest_f' = memo $ \case
Prelude Data.MemoTrie|   0 -> 0
Prelude Data.MemoTrie|   n -> max n (fastest_f'(n `div` 2) + fastest_f'(n `div` 3) + fastest_f'(n `div` 4))
Prelude Data.MemoTrie| :}
Prelude Data.MemoTrie> fastest_f' 12308918230918230182031231231293810923
11097012733777002208302545289166620866358