gpt4 book ai didi

algorithm - 为什么这个简单的 O(n) Haskell 算法表现得更像 O(2^n)?

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:40:10 26 4
gpt4 key购买 nike

<分区>

Haskell 缓存纯函数调用的结果,这是区分纯行为和不纯行为的众多原因之一。然而,这个本应在 O(n) 中运行的函数(其中 n 为 50 下面)运行得非常慢:

lucas 1 = 1
lucas 2 = 3
lucas n = lucas (n-1) + lucas (n-2)
map (lucas) [1..50]

前三十项左​​右一起计算不到一秒,然后 31 需要半秒左右,32 需要一整秒,33 需要几秒,34 需要 6 秒,35 需要 11 秒,36 需要 17秒...

为什么这个函数这么慢?如果 GHC 交互式运行时正在缓存结果,那么每次调用 lucas 应该只涉及前两个缓存项的总和。一次加法运算找到第 3 项,一次额外的加法运算找到第 4 项,一次额外的加法运算找到第 5 项,因此考虑到缓存,总共只有 48 次加法就达到了第 50 项。该函数应该不会花费接近一秒的时间来查找至少前几千个词,为什么性能如此糟糕?

lucas 500 的计算,我已经等了半个多小时了。

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