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

Question

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

algorithmhaskellcachingbig-otime-complexity

6

Haskell缓存纯函数调用的结果，这也是纯和非纯行为分离的原因之一。然而，下面这个函数应该在n为50时以O(n)运行，但实际上运行非常慢：

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"。

- TheEnvironmentalist

2

没有缓存 - 至少不是你期望的那种方式 - 这将与任何其他语言中的行为相同。 - Random Dev

3

这个行为的时间复杂度不是 O(n^2)，而是 O(2^n)。 - Willem Van Onsem

1

@WillemVanOnsem 哈哈哈，我看我有点太乐观了。 - TheEnvironmentalist

3

顺便说一下，你很自信地说“Haskell缓存纯函数调用的结果”。为什么？我们能找到可以更正的来源吗？似乎有很多人对此有误解... - Daniel Wagner

我相信它可能是在《学习 Haskell》中编写的。 - TheEnvironmentalist

显示剩余3条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Random Dev · Accepted Answer

您的版本运行缓慢的原因在于没有对和这两个部分进行记忆化处理 - 因此，这两个值将会被反复重新计算（递归），导致速度极慢。

解决方法是将计算后的值存储在某处：

使用列表惰性求值

以下是一个简单的版本，与您的代码片段执行相同的操作，但应该更快 - 它将在列表本身中保存已经计算过的部分：

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

first50 :: [Integer]
first50 = take 50 lucasNumbers

这样做更快的原因是，现在列表的惰性将帮助您记忆不同的部分。

如果你搜索 Haskell中的Fibonacci数列，你可以了解更多相关知识（它实际上和你的方法相同 ;)）

使用 `unfoldr`

另一种（也许看起来不那么神奇）的方法是使用 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版本。

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

使用列表惰性求值

使用 unfoldr

使用 `unfoldr`