在 Haskell 中内存递归函数的最快方法是什么?
背景:最近我一直在用 Haskell 解决 Project Euler 问题。许多需要对递归定义的组合或数论函数进行多次计算,例如斐波那契数。如果这些函数被内存,性能会显着提高,也就是说,函数的结果被缓存以备后用。
我见过很多解决这个问题的方法。最优雅的似乎是this.一个使用 Data.IntMap(或哈希表)和 State monad。 this answer 中建议的基于树的解决方案,这样的解决方案似乎相当普遍。再举一个例子,参见 this blog post .我见过其他使用内置函数的解决方案。第 2 节中有一个 here使用 fix
,而且编译器有时似乎可以是 massaged into memoizing无需额外工作。还有几个 prebuilt solutions .
我想知道对于 Project Euler 中使用的各种函数,哪种内存方法在实践中最快。我的直觉说哈希表库是,因为哈希表似乎是命令式语言中首选的字典结构。纯功能树解决方案很酷,但我的谷歌搜索告诉我它们是 strictly worse than hash tables in terms of asymptotic performance.
编辑
一些评论说这个问题太宽泛,无法回答,经过深思熟虑我同意。因此,让我给出两个要内存的函数的具体示例:一个递归计算第 n 个斐波那契数的函数,以及一个递归计算加泰罗尼亚数的函数。对于大 n,我想多次计算这些函数。
我知道这些有明确的公式,但让我们忽略它,因为这里的真正目的是使用它们来基准内存技术。
最佳答案
当试图找到第 n 个斐波那契数时,您需要记住的唯一数字是前两个数字。你可以像 (f n-1, f n ) 这样的元组来做,并在每个循环中更新这个元组。请注意,更新元组是通过指针操作完成的,计算量并不大。
一个更简洁、更智能的替代方案是:
fibs :: [Integer]
fibs = fibcreator 0 1
where
fibcreator a b = a : fibcreator b (a+b)
nth = take n fibs
但我见过的最好的算法之一是:
- 让我们定义一个矩阵 m = [e11 = 1,e12 =1,e21 = 1,e22 = 0]
- 为了得到第 n 个斐波那契数,我们计算 m' = m ^ (n-1)
- 矩阵m'中的e11个元素为第n个斐波那契数
现在很棒的是,为了得到 17 个斐波那契数,我们可以做
m' = ((((m^2)^2)^2)^2) * m
这显着减少了计算时间,并在算法中被动地嵌入了内存。 重点是 Haskell 已经使用这个算法来计算幂函数,所以你不需要实现它。完整的实现是:
data Matrix = Matrix Integer Integer Integer Integer
instance Num Matrix where
(*) (Matrix a11 a12 a21 a22) (Matrix b11 b12 b21 b22)
= Matrix (a11*b11 + a12*b21) (a11*b12 + a12*b22) (a21*b11 + a22*b21) (a21*b12 + a22*b22)
fib4 :: Integer -> Integer
fib4 0 = 0
fib4 n = x
where
(Matrix x _ _ _) = Matrix 1 1 1 0 ^ (n-1)
关于algorithm - 在 Haskell 中内存最有效的方法是什么?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41890669/