在Haskell中记忆递归函数的最快方法是什么？在Haskell中记忆最有效的方法是什么？

背景：最近我一直在解决Haskell中的项目欧拉问题。许多计算需要递归定义的组合或数理论函数，例如斐波那契数。如果这样的函数被记忆，性能会显着提高，也就是说，函数的结果被缓存供以后使用。

我见过这个问题的很多解决方案。最优雅的似乎是this.一个使用Data.IntMap（或哈希表）和状态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.

编辑

一些评论说，这个问题太宽而不能回答，并在反思我同意。因此，让我举两个具体的memoize函数示例：递归计算第n个斐波那契数的函数，以及递归计算加泰罗尼亚数的函数。我想多次为大n计算这些函数。

我知道有这些明确的公式，但让我们忽略它，因为这里的真正意义在于使用它们来测试记忆技术。

来源

2017-01-27 Potato

二叉搜索树[像'IntMap'（https://github.com/haskell/containers/blob/master/Data/IntMap/Internal.hs#L347-L352）是是的，对于_asymptotic_表现来说，它比散列映射慢。渐近线不是一切，但。 'IntMap'还有其他一些理想的属性，例如避免哈希的开销，以持久方式使用时表现良好等。对于正常用法，IntMap的性能与哈希表相竞争。 –

这取决于问题。如果数组是合适的，例如当你最终必须评估一个范围内每个值的函数时，那么它们可能是最有效的选择。 –

作为附注，您链接到的最后一个堆栈溢出答案由Jon Harrop编写。 [这里]（https://www.reddit.com/r/haskell/comments/4ogle3/post_about_the_disadvantages_of_functional/d4clabv/）是@sclv写的一段评论，我认为是相关的。 – Alec

当试图找到第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个Fibonacci数我们计算M '= M ^（N-1）
E11元件' 是第n个Fibonacci数

现在什么是伟大这里是为了获得17 Fibonacci数我们可以做

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)

来源

2017-01-29 11:57:57

“我知道这些都有明确的公式，但我们忽略它，因为这里的真正意义在于使用它们来对记忆技术进行基准测试。” – Alec

斐波那契数列的显式公式实际上评估起来较慢，因为您必须以符号而非数字的方式对其进行评估。我实现了一次，看到了，我认为它最终成为O（n^2）或左右。 – OmnipotentEntity

在Haskell中记忆最有效的方法是什么？

编辑

回答

相关问题