This question already has an answer here:
Haskell and memoization of pure function results [duplicate]
(1个答案)
5年前关闭。
Haskell缓存纯函数调用的结果，纯函数调用的结果是纯行为与不纯行为之间分离的众多原因之一。然而，该函数应该在O(n)中运行，其中n是下面的
前三十个左右的项在不到一秒的时间内一起计算，然后31花费半秒左右，32花费了一整秒，33花费了几秒钟，34花费了6秒，35花费了11秒，36花费了17秒。 。
为什么这个功能这么慢？如果GHC交互式运行时正在缓存结果，则对
我已经等待了半个多小时，以便计算
之所以更快，是因为现在列表的懒惰将帮助您记住不同的部分
如果您寻找Fibonacci sequences in Haskell，您可以学到很多(它实际上与您的相同；))
使用
另一种(也许看起来不太魔术)的方法是使用
对您的评论/问题:
假设您正在谈论
这将产生如下内容:
也许您应该自己尝试
(1个答案)
5年前关闭。
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。 最佳答案
您的版本很慢的原因是没有lucas (n-1)和lucas (n-2)部分的内存-因此将一次又一次地(递归)重新计算两个值-这很慢。
解决方案是将计算出的值保留在某个位置:
使用列表懒惰
这是一个简单的版本，其功能与您的代码段相同，但应该更快一些-它会将已经计算出的部分保留在列表本身中:
lucasNumbers :: [Integer]
lucasNumbers = 1:3:zipWith (+) lucasNumbers (tail lucasNumbers)
first50 :: [Integer]
first50 = take 50 lucasNumbers
之所以更快，是因为现在列表的懒惰将帮助您记住不同的部分
如果您寻找Fibonacci sequences in Haskell，您可以学到很多(它实际上与您的相同；))
使用
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版本09-27 15:00