gpt4 book ai didi

haskell - Haskell 中缓存了哪些函数?

转载 作者:行者123 更新时间:2023-12-02 16:44:02 25 4
gpt4 key购买 nike

我有以下代码:

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/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com