在Haskell中记忆？ [英] Memoization in Haskell?
问题描述
关于如何在Haskell中有效地解决以下函数的任何指针，对于大数目（n> 108）
f（n）= max（n，f（n / 2）+ f（n / 3）+ f（n / 4））
我在Haskell中看到了用于解释斐波那契
数字的例子，其中涉及计算（懒惰地）所有斐波那契数字
达到要求的n。但在这种情况下，对于给定的n，我们只需要
就可以计算出非常少的中间结果。
谢谢
但首先，
{ - ＃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 通过使用修复f
这可以让您测试 f 通过调用来表达小于 f 的小值，例如：修复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
是可以忍受的，但结果并不比这个好得多。我们可以做得更好！
首先，我们定义一棵无限树：
<$ c $ （Tree a）a（Tree a）
实例Functor Tree其中
b
然后我们将定义一个索引的方法，所以我们可以找到一个索引<$ c
pre $ 在 O（log n）时间内：
index（Tree _ m _）0 = m
index（Tree l _ r）n = case（n - 1）`divMod` 2 of
（q，0） - > ; index 1 q
（q，1） - > index rq
...我们可能会发现一棵充满自然数的树很方便，所以我们不会这些指数必须摆弄：
nats :: Tree Int
nats = go 0 1
其中
go！n！s =树（go l s'）n（go r s'）
其中
l = n + s
r = l + s $ b因为我们可以索引，所以你可以把一棵树转换成一棵树list：
toList :: Tree a - > [a]
toList as = map（index as）[0 ..]
您可以通过验证 toList nats 给你 [0 ..]
$ b来检查工作。
$ b 现在，
f_tree :: Tree Int
f_tree = fmap（f fastest_f ）nats
faster_f :: Int - > Int
faster_f = index f_tree
的工作方式与上面的列表类似，但不是采用线性找到每个节点的时间可以在对数时间内追踪它。
结果相当快：
*主> latest_f 12380192300
67652175206
*主要>最快速度f 12793129379123
120695231674999
事实上，它可以更快速地完成并取代 Int with 整数上面，几乎是瞬间得到可笑的大答案
*主> 'fast_f'1230891823091823018203123
93721573993600178112200489
* Main> '最快的''12308918230918230182031231231293810923
11097012733777002208302545289166620866358
Any pointers on how to solve efficiently the following function in Haskell, for large numbers (n > 108)
f(n) = max(n, f(n/2) + f(n/3) + f(n/4))
I've seen examples of memoization in Haskell to solve fibonacci
numbers, which involved computing (lazily) all the fibonacci numbers
up to the required n. But in this case, for a given n, we only need to
compute very few intermediate results.
Thanks
解决方案 We can do this very efficiently by making a structure that we can index in sub-linear time.
But first,
{-# LANGUAGE BangPatterns #-}
import Data.Function (fix)
Let's define f, but make it use 'open recursion' rather than call itself directly.
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)
You can get an unmemoized f by using fix f
This will let you test that f does what you mean for small values of f by calling, for example: fix f 123 = 144
We could memoize this by defining:
f_list :: [Int]
f_list = map (f faster_f) [0..]
faster_f :: Int -> Int
faster_f n = f_list !! n
That performs passably well, and replaces what was going to take O(n^3) time with something that memoizes the intermediate results.
But it still takes linear time just to index to find the memoized answer for mf. This means that results like:
*Main Data.List> faster_f 123801
248604
are tolerable, but the result doesn't scale much better than that. We can do better!
First, let's define an infinite tree:
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)
And then we'll define a way to index into it, so we can find a node with index n in O(log n) time instead:
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
... and we may find a tree full of natural numbers to be convenient so we don't have to fiddle around with those indices:
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
Since we can index, you can just convert a tree into a list:
toList :: Tree a -> [a]
toList as = map (index as) [0..]
You can check the work so far by verifying that toList nats gives you [0..]
Now,
f_tree :: Tree Int
f_tree = fmap (f fastest_f) nats
fastest_f :: Int -> Int
fastest_f = index f_tree
works just like with list above, but instead of taking linear time to find each node, can chase it down in logarithmic time.
The result is considerably faster:
*Main> fastest_f 12380192300
67652175206
*Main> fastest_f 12793129379123
120695231674999
In fact it is so much faster that you can go through and replace Int with Integer above and get ridiculously large answers almost instantaneously
*Main> fastest_f' 1230891823091823018203123
93721573993600178112200489
*Main> fastest_f' 12308918230918230182031231231293810923
11097012733777002208302545289166620866358
这篇关于在Haskell中记忆？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
