我有以下代码:
memoize f = (map f [0 ..] !!)
fib' 0 = 1
fib' 1 = 1
fib' n = fib' (n - 1) + fib' (n - 2)
fibMemo n = memoize fib' n
fibMemo' = memoize fib'
(我知道斐波那契实现具有指数时间复杂度并且不使用缓存)
第一次执行 fibmemo' 30
需要 3 秒,第二次大约需要 0 秒,因为结果被缓存了。但第一个版本fibmemo
并没有缓存结果,它总是需要3秒才能执行。唯一的区别是定义(据我所知是等效的)。
所以我的问题是,Haskell 中缓存了哪些函数?
我已经读过https://wiki.haskell.org/Memoization并没有解决我的问题。
最佳答案
本质上,您定义的函数的行为如下:
fibMemo n = let m = map fib' [0..] in m !! n
fibMemo' = let m = map fib' [0..] in (m !!)
为什么fibMmemo'
效率更高?好吧,我们可以将其重写为
fibMemo' = let m = map fib' [0..] in \n -> m !! n
这使得更清楚的是,单个列表m
是在n
作为输入之前创建的。这意味着对 fibMemo'
的所有调用都将使用相同的 m
。第一个调用缓慢地计算 m
的一部分,后续调用将重用该缓存结果(当然,假设调用命中缓存,否则 m
的另一部分是评估并缓存)。
相反,fibMemo
相当于
fibMemo = \n -> let m = map fib' [0..] in m !! n
在创建列表m
之前接受输入n
。因此,每次调用都会获得一个新的缓存,这是毫无意义的,因为缓存的全部目的是稍后重用它。
lambda \n ->
与 let m = ..
的顺序对于性能而言非常重要。由于 m = ..
不使用 n
,从技术上讲,let m = ..
可以向外 float ,本质上是把 fibMemo
转换成 fibMemo'
,而不影响语义。然而,正如您所发现的,这通常不会保留性能!
这确实是 GHC 可以执行的优化,但实际上却没有,因为它很容易使性能显着变差。
关于haskell - Haskell 中缓存了哪些函数?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53030497/