问题标签 [memoization]

我正在学习“中级 Perl”，这很酷。我刚刚完成了关于“施瓦茨变换”的部分，在它沉入其中之后，我开始想知道为什么变换不使用缓存。在具有多个重复值的列表中，转换会重新计算每个值的值，所以我想为什么不使用哈希来缓存结果。这是一些代码：

我错过了什么吗？为什么书籍中没有列出 Schwartzian 变换的缓存版本，并且通常只是更好地传播，因为乍一看我认为缓存版本应该更有效？

编辑：daxim 在评论中指出这被称为兽人策略。所以我并没有发疯，虽然我不太明白这个名字。

Python多线程记忆，有可能吗？如果是这样，怎么做？

我有一个通用方法，用于将数据库中的字符串值转换为实际转换值。

问题是在初始化期间我不知道数据库中的数据是什么类型，只有在第一次调用时我才能做出这个决定。

有没有办法以不强制拆箱缓存的值类型的方式构造它？（不改变包含类的签名）

我想要的是一个记忆装饰器：

• 可以使用参数和关键字参数来记忆实例方法
• 有一个可以通过一次调用（全局）清除的缓存（与使用每个函数缓存的这个相比：python resettable instance method memoization decorator）
• 相当有效

我已经调整了我看到的一个例子，并提出了以下内容：

我的问题是缓存部分似乎涉及很多开销（例如，对于递归函数）。以下面的函数为例，我可以用非记忆版本调用 fib(30) 十次，比记忆版本更短。

谁能建议一个更好的方法来编写这个装饰器？（或将我指向一个更好（即更快）的装饰器，它可以满足我的需求）。我对保留方法签名或帮助自省工具“了解”有关装饰函数的任何内容不感兴趣。

谢谢。

PS使用python 2.7

我一直在寻找Data.MemoCombinators的来源，但我真的看不出它的核心在哪里。

请向我解释所有这些组合器背后的逻辑以及它们如何实际工作以在现实世界编程中加速您的程序的机制。

我正在寻找此实现的细节，并可选择与其他 Haskell 记忆方法进行比较/对比。我了解什么是记忆化，而不是在寻找关于它一般如何工作的描述。

下面的代码是一个流行的 topcoder 问题FourBlocks的答案（您需要登录）。该解决方案使用位掩码记忆来使用大小为 1 的块和大小为 4 的正方形块在网格中找到最大总和。有人可以帮助我理解它是如何工作的吗？这是做什么的

另外，函数 rec() 如何适合正方形？它只比较 2 位。

我正在编写一个手动计算记忆系统（呃，在 Matlab 中）。简单的部分很简单：

• 一种在执行计算后将数据放入记忆系统的方法。
• 一种从记忆中查询和获取数据的方法。
• 一种向系统查询所有“键”的方法。

这些部分并没有太大的疑问。问题是我的计算机内存有限，所以有时“放置”操作必须将一些对象转储出内存。我担心“缓存未命中”，所以我想要一些相对简单的系统来删除不经常使用和/或重新计算成本不高的记忆对象。我该如何设计那个系统？我可以想象它具有的部分：

• 一种告诉“放置”操作的计算成本（相对而言）的方法。
• 一种可选地提示“放置”操作的方法，可能需要多长时间进行一次计算（未来）。
• 'get' 操作需要注意查询给定对象的频率。
• 一种告诉整个系统要使用的最大内存量的方法（好吧，这很简单）。

当你达到内存限制并且它必须根据它们的内存占用、它们的成本和它们的有用性来剔除一些对象时，它的真正胆量将是在“放置”操作中。我怎么做？

抱歉，如果这太模糊或偏离主题。

如果你是一名 ruby​​ 程序员，那么你可能会遇到哈希块记忆模式。举一个简单的例子，我向您展示斐波那契数列的记忆版本：

当然，这不是创建斐波那契数列的记忆版本的唯一方法。您还可以执行以下操作：

希望您看到哈希块记忆模式如何映射到在许多其他语言中更为常见的第二个版本。我想知道的是这两个版本之间是否有任何区别？我无法摆脱散列块版本更有效的感觉，但我无法真正证明原因。

缓存实例变量的技术有一个特定的“学术”名称，但我不记得了。请帮帮我。

编组称为编组。
延迟加载称为延迟加载。
所描述的技术称为...？

我已经在 Haskell 中编写了0-1 背包问题。我对迄今为止所取得的懒惰和普遍性水平感到相当自豪。

我首先提供用于创建和处理惰性二维矩阵的函数。

然后我为给定的背包问题制作一个特定的表

最后用几个辅助函数来查看表格

这很容易。但我想更进一步。

我想要一个更好的表数据结构。理想情况下，它应该是

• 未装箱（不可变） [编辑] 没关系
• 懒惰的
• 无界
• O(1)建设时间
• O(1)查找给定条目的时间复杂度，
  （更实际地，在最坏的情况O(log n)下，其中 ni*j用于查找第 i 行第 j 列的条目）

如果您能解释您的解决方案为什么/如何满足这些理想，则可以加分。

如果您可以进一步概括knapsackTable，也可以加分，并证明它是有效的。

在改进数据结构时，您应该尝试满足以下目标：

• 如果我要求最大权重为 10 的解决方案（在我当前的代码中，即indexTable knapsackTable 5 105 意味着包括项目 1-5），则只应执行最少的工作量。理想情况下，这意味着无需O(i*j)将表格的每一行的脊椎强制为必要的列长度。如果您认为 DP 意味着评估整个表格，您可以说这不是“真正的”DP。
• 如果我要求打印整个表格（类似于printTable knapsackTable 5 10），则每个条目的值应计算一次且仅计算一次。给定单元格的值应取决于其他单元格的值（DP 风格：想法是，永远不要重新计算相同的子问题两次）

想法：

• Data.Array有界:(
• UArray严格:(
• 记忆技术（关于Haskell中DP的问题）这可能有效

对我陈述的理想做出一些妥协的答案将被赞成（无论如何，由我），只要它们提供信息。妥协最少的答案可能是“接受”的答案。