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

Question

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,所以术语50达到考虑缓存只有48个加法.该功能不应该花费近一秒钟才能找到至少前几千个术语,为什么表现如此可怕？

我现在已经等了半个多小时lucas 500才能计算出来.

Answer 1

原因你的版本是非常缓慢的,没有记忆化的lucas (n-1)和lucas (n-2)部分-所以这两个值将会被重新计算(递归)一遍又一遍-这是痛苦的缓慢.

解决方案是将计算值保持在某个位置:

使用list-lazyness

这是一个简单的版本,它将与您的代码片段相同,但应该更快 - 它将保留已经计算的部分在列表中:

lucasNumbers :: [Integer]
lucasNumbers = 1:3:zipWith (+) lucasNumbers (tail lucasNumbers)

first50 :: [Integer]
first50 = take 50 lucasNumbers

这个更快的原因是,现在列表的懒惰会帮助你记住不同的部分

如果你在Haskell中寻找Fibonacci序列,你可以学到很多东西(它真的和你的一样;))

另一种(可能不那么神奇似乎)这样做的方法是使用Data.List.unfoldr- 这里已经计算过的部分(或那些重要的部分 - 最后和倒数第二个元素)将处于你为展开操作传递的状态:

lucasNumbers :: [Integer]
lucasNumbers = unfoldr (\ (n,n') -> Just (n, (n',n+n'))) (1,3)

发表评论/问题:

假设你在谈论x(n) = x(n-1)^2-2那么你可以这样做:

lucasLehmer :: [Integer]
lucasLehmer = 4 : map (\ x -> x^2-2) lucasLehmer

这将产生这样的东西:

?> take 5 lucasLehmer
[4,14,194,37634,1416317954]

也许你应该unfoldr自己试试这个版本