在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屋!