标签: memoization

我刚开始使用Python,我不知道什么是memoization以及如何使用它.另外,我可以有一个简化的例子吗？

memoization和动态编程有什么区别？我认为动态编程是memoization的一个子集.这样对吗？

我有一组整数.我想使用动态编程找到该集合中增长最长的子序列.

的自下而上的方法(动态编程)在于第一看"较小"的子问题,进而解决使用所述溶液到较小的问题较大子问题.

在自上而下的在于解决"自然地"的问题,并检查是否已计算出前解决的子问题.

我有点困惑.这两者有什么区别？

关于如何有效地解决Haskell中的以下函数的任何指针,对于大数 (n > 108)

f(n) = max(n, f(n/2) + f(n/3) + f(n/4))

我已经在Haskell中看到了用于解决斐波纳契数的例子,其中涉及计算(懒惰)所有斐波纳契数到所需的n.但在这种情况下,对于给定的n,我们只需要计算很少的中间结果.

谢谢

通过什么机制这个斐波那契函数被记忆了？

fib = (map fib' [0..] !!)                 
     where fib' 1 = 1                                                        
           fib' 2 = 1                                                        
           fib' n = fib (n-2) + fib (n-1)                    

在相关的说明中,为什么这个版本不是？

fib n = (map fib' [0..] !! n)                                               
     where fib' 1 = 1                                                        
           fib' 2 = 1                                                        
           fib' n = fib (n-2) + fib (n-1)                    

我无法弄清楚为什么m1显然被记忆,而m2不在下面:

m1      = ((filter odd [1..]) !!)

m2 n    = ((filter odd [1..]) !! n)

m1 10000000在第一次调用时大约需要1.5秒,而后续调用需要一小部分(大概是缓存列表),而m2 10000000总是花费相同的时间(每次调用重建列表).知道发生了什么事吗？关于GHC是否以及何时会记忆功能,是否有任何经验法则？谢谢.

我想知道缓存和memoization之间的实际区别是什么.正如我所看到的,两者都涉及通过存储来避免重复的函数调用来获取数据.

这两者有什么区别？

我试图找到一种简单的方法来使用像R中的Perl的散列函数(基本上是缓存),因为我打算进行Perl风格的散列并编写我自己的计算备忘录.然而,其他人已经打败了我,并有包装备忘.我越挖,越我发现,如memoise和R.cache,但差异不容易明确.另外,目前还不清楚如何使用Perl风格的哈希(或Python风格的词典)并编写一个自己的memoization,而不是使用hash包,这似乎不是两个memoization包的基础.

由于我无法找到有关CRAN或其他地方的信息来区分选项,或许这应该是关于SO的社区维基问题:R中的记忆和缓存有哪些选项,它们的区别是什么？

作为比较的基础,这里是我找到的选项列表.此外,在我看来,所有都依赖于散列,所以我也会注意到散列选项.密钥/值存储在某种程度上是相关的,但是会打开关于数据库系统的大量蠕虫(例如BerkeleyDB,Redis,MemcacheDB和其他许多人).

它看起来像是:

哈希

• 摘要 - 为任意R对象提供散列.

记忆化

• memoise - 用于记忆功能的非常简单的工具.
• R.cache - 为memoization提供了更多功能,虽然看起来有些功能缺少示例.

高速缓存

• hash - 提供类似于Perl的哈希和Python字典的缓存功能.

键/值存储

这些是R对象外部存储的基本选项.

• stashr
• filehash

检查点

• cacher - 这似乎更像是检查点.
• CodeDepends - 一个支持cacher并提供一些有用功能的OmegaHat项目.
• DMTCP(不是R包) - 似乎支持多种语言的检查点,并且开发人员最近在R中寻求协助测试DMTCP检查点.

其他

• Base R支持:命名向量和列表,数据框的行和列名称以及环境中项目的名称.在我看来,使用列表有点像kludge.(也有pairlist,但已被弃用.)
• 所述data.table包支持在一个数据表元素的快速查找.

用例

虽然我最感兴趣的是了解选项,但我有两个基本用例:

1. 缓存:简单计算字符串.[注意:这不适用于NLP,但一般用途,因此NLP库是过度的; 表格不合适,因为我不想等到整个字符串集加载到内存中.Perl风格的哈希处于适当的实用水平.]
2. 记忆怪异的计算.

这些真的出现了,因为我正在深入研究一些slooooow代码的分析,我真的只想计算简单的字符串,看看我是否可以通过memoization加速一些计算.能够散列输入值,即使我没有记忆,也会让我看看memoization是否有帮助.

注1:可重复研究的CRAN任务视图列出了几个软件包(cacher和R.cache),但没有详细说明使用选项.

注2:为了帮助其他人查找相关代码,这里有一些关于一些作者或包的注释.一些作者使用SO.:)

• Dirk Eddelbuettel: …

我看到python 3.2在functools库中有memoization作为装饰器. http://docs.python.org/py3k/library/functools.html#functools.lru_cache

不幸的是,它尚未向后移植到2.7.是否有任何具体原因导致它在2.7中不可用？是否有任何第三方图书馆提供相同的功能,还是应该自己编写？