Alb*_*ert 23 haskell functional-programming memoization
我一直认为Haskell会做一些自动智能记忆.例如,天真的斐波那契实施
fib 0 = 0
fib 1 = 1
fib n = fib (n-2) + fib (n-1)
因此会很快.现在我读了这个,似乎我错了--Haskell似乎没有做自动记忆.或者我理解错了什么？
还有其他语言可以自动(即隐式,非显式)进行记忆吗？
实施备忘录的常用方法有哪些？在我看到的所有示例实现中,它们都使用了散列映射,但其大小没有任何限制.显然,这在实践中不起作用,因为你需要某种限制.鉴于此,它变得更加复杂,因为当你达到极限时,你必须扔掉一些数据.并且它变得复杂:如果限制可能是动态的并且经常使用的功能应该比不常使用的功能具有更高的限制吗？当你达到极限时,你扔掉了什么条目？只是最新使用的一个？在这种情况下,您还需要对数据进行排序.您可以使用链接列表和哈希映射的某种组合来实现这一点.这是常见的方式吗？
你可以链接(或参考)一些常见的实际实现吗？
谢谢,艾伯特
编辑:我最感兴趣的是我描述的问题,即如何实现这样的限制.对任何解决这个问题的论文的任何引用都会非常好.
编辑:可以在此处找到一些示例实现(具有限制)的想法.
编辑:我不是试图解决特定应用程序中的特定问题.我正在寻找用于memoization的通用解决方案,它可以全局应用于(纯功能)程序的所有功能(因此不实现内存限制的算法不是解决方案).当然,(可能)没有最佳/最佳解决方案.但这使我的问题不那么有趣.
为了尝试这样的解决方案,我考虑将其添加到Haskell作为优化.我真的很想知道这会有多好.
我想知道是否有人已经这样做了.
我在评论中说,你的要求听起来像垃圾收集.我之所以这么想是因为你有兴趣管理一个有限的内存池,偶尔清除它以便它不会过去.
现在我考虑一下,它更像是一个虚拟内存页面替换算法.您可以阅读维基百科页面,了解用于解决此类问题的各种方法,例如"最近未使用","老化","时钟","第二次机会"等.
但是,通常不会通过限制保留的结果来进行记忆; 上述算法所需的突变通常是不合时宜的.但是,不要让那些气馁.你有一些有趣的想法,可以成为探索Haskell中的记忆可能性的有价值的补充.
有时,特定的记忆问题很适合有限的记忆.例如,对齐两个基因序列可以使用动态编程(参见维基百科的动态编程#序列比对)和二维记忆表来完成.但由于给定单元的DP解决方案仅取决于前一行的结果,因此您可以从底部开始并丢弃距离当前行大于1的行.斐波那契数字是相同的:你只需要序列中的前两个数字来计算下一个数字.如果你感兴趣的是第n 个数字,你可以提前丢弃任何东西.
大多数记忆都是为了加速存在共享子问题的递归算法.许多此类问题没有简单的方法对评估进行排序,以便丢弃您不再需要的结果.那时,您只是猜测,使用启发式(如使用频率)来确定谁获得了对有限资源的访问权限.
不,Haskell不会对函数进行自动记忆.它的作用是存储值,所以如果你有
x = somethingVeryLong
和你在同一范围内的其他地方
y = f x
z = g x
那么x只会被计算一次.
该软件包显示了如何使用各种密钥和查找表存储记忆值.记忆通常在较大函数的单个调用中使用,因此记忆值不会永远停留(正如您所说的那样是一个问题).如果你想要一个也使用LRU忘记旧值的备忘录,那么我认为你可能需要把它放在状态monad或者其他东西中; 你不能让Haskell使用传统的memoising方法表现得那样.
Haskell似乎没有自动记忆.或者我理解错了什么？
不,哈斯克尔没有.但是,共享表达式只计算一次.在Paul Johnson给出的示例中x,它作为thunk存储在堆中.二者y并z可以参考x如x在范围,并且它们是指相同的位置.一旦x必须进行评估,它将仅评估一次,并且仅保留评估结果.所以这不是真正的记忆,而是实施的结果.
还有其他语言可以自动(即隐式,非显式)进行记忆吗？
我已经看到装饰器@memoized出现在一些python源代码中.你当然可以完全为它创建自己的装饰器/实现.完成LRU和您要使用的其他策略.
实施备忘录的常用方法有哪些？
没有真正的common方法来实现备忘录.对于类似于fib的模式(只有一个参数,这是一个数字),在fib-example中使用的memoisation可以设计一个通用解决方案(hashmaps one)并且它可以工作,但它也可能对你的特定问题不是最理想的.
通过memoisation你有副作用,所以你可能希望缓存存在于State monad中.但是,一般来说,您希望尽可能保持算法的纯度,因此如果它有递归,那么您已经陷入了一些混乱.这是因为你将以递归方式调用函数的memoised版本,但是需要在State monad中运行,所以现在你的整个函数必须在State monad中运行.这也会影响懒惰,但你可以尝试懒惰状态monad.
记住这一点:很难实现良好的自动记忆.但是你可以很容易地走很长的路.自动记忆功能可能涉及程序转换,在修复点中编写内容可能会有很长的路要走.
编辑:我最感兴趣的是我描述的问题,即如何实现这样的限制.对任何解决这个问题的论文的任何引用都会非常好.
一旦你有了记忆的基本机制,你就可以为你的记忆表调整查找和存储函数,以实现LRU或其他一些保持内存消耗较小的机制.也许你可以从这个C++示例中了解LRU的想法.