问题标签 [memoization]

我在这个三角形中有大量从 0 到 4 的整数数组。我正在尝试使用 Ruby 学习动态编程，并希望在计算三角形中满足三个标准的路径数方面得到一些帮助：

1. 您必须从包含 70 个元素的行中的零点之一开始。
2. 您的路径可以在您正上方的一排（如果正上方有数字）或向左对角线的一排。这些选项之一始终可用
3. 在第一行达到零的路径总和必须为 140。

例如，从底行的第二个零开始。您可以直接向上移动到 4 的左侧或对角线。在任何一种情况下，您到达的数字都必须添加到您访问过的所有数字的运行计数中。您可以从 1 移动到正上方的 2（运行总和 = 3）或左侧对角线的 0（运行总和 = 1）。

2008 年 7 月中旬，Memoization 被添加到 Rails 核心中。用法演示在这里。

我还没有找到任何关于何时应该记住方法以及每个方法的性能影响的好例子。例如，这篇博文建议，通常根本不应该使用记忆。

对于可能对性能产生巨大影响的东西，似乎很少有资源可以提供简单的教程。

有没有人在他们自己的项目中看到过记忆化？哪些因素会让你考虑记忆一个方法？

在我自己做了一些更多的研究之后，我发现在 Rails 核心中使用了很多次记忆。

这是一个例子：http: //github.com/rails/rails/blob/1182658e767d2db4a46faed35f0b1075c5dd9a88/actionpack/lib/action_view/template.rb。

这种用法似乎与上述博客文章的发现背道而驰，即发现记忆化会损害性能。

我有一组从Class::DBI继承的相当复杂的 ORM 模块。由于数据很少更改，我正在考虑在此之上使用缓存/记忆层来加快速度。我找到了一个模块：Class::DBI::Cacheable但没有评级或对 RT 的任何评论。我希望收到使用过这个或任何其他 Class::DBI 缓存方案的人的来信。

万分感谢。

考虑以下：

我是新手，但我认为缓存可以分解为装饰器。只是我没有找到喜欢的;）

PS真正的计算不依赖于可变值

我有一个模型：

我想记住 balance 方法并将其存储在 memcached 中。当然，问题是缓存值需要在任何时候创建付款或购买时过期。我可以在付款和购买的 after_save 回调中插入代码，以使他们帐户的缓存余额过期，但在我看来，如果我可以这样说的话，会更容易理解/维护：

是否有现有的 gem/插件可以做到这一点？在我开始自己写之前，这是个好主意吗？我看到的缺点是，对于正在修改 Purchase 的 Dollar_amount 方法的人来说，他们需要考虑缓存问题可能不太明显（如果他们无意中引入了对另一个模型的依赖，比如 SubPurchase 或其他东西，它会搞砸的。）但是由于这无论如何都不是很明显，我认为拥有一个简洁的声明性语法是值得的 - 至少在它中断时，很清楚如何修复它。

想法？

编辑：为了响应语义艺术的回答，我将更明确地说明“只需将过期时间放在相关回调中”方法的问题 - 问题是你最终会在整个代码库中过期 - 它从 after_save 回调开始付款，但也许它在购买的单独观察者中，然后你有多态关联、继承树等。我提出的语法迫使开发人员将所有这些案例放在一个整齐的列表中。这样，当您收到诸如“用户余额有时不同步并且他们不太确定如何复制问题”之类的错误报告时，更容易弄清楚发生了什么。

我应该使用if defined?

或者||=

我注意到if defined?最近越来越多地使用这种方法。一个比另一个有什么优势吗？就个人而言，我更喜欢||=可读性。我还认为 Rails 可能有一个memoize宏可以透明地提供这种行为。是这样吗？

Pickle 是否总是为某个输入值产生相同的输出？我想在腌制具有相同内容但插入/删除历史不同的字典时可能会有一个问题。我的目标是使用 Pickle 和 SHA1 为 memoize 实现创建函数参数的“签名”。

我有一个我开始实施的缓存想法：

记忆 function并将返回值与函数签名的哈希一起存储在Velocity中。使用PostSharp，我想检查缓存并返回返回值的重新水化表示，而不是再次调用该函数。我想使用属性来控制这种行为。

不幸的是，这对我组织中的其他开发人员来说可能是危险的，如果他们爱上了性能提升并开始用缓存属性装饰每一个可见的方法，包括一些带有副作用的方法。当记忆库怀疑某个函数可能会导致副作用时，我想退出编译器警告。

使用 CodeDom 或 Reflection 如何判断代码可能会导致副作用？

我决定使用 PostSharp（与魔法无异）来读取属性和记忆函数。函数调用的哈希将是键，并且将返回缓存（在Velocity中）的结果，而不是再次调用该函数。简单的peasy，mac-and-cheesy。

我已经放弃了检测装饰函数中的副作用，这被证明是一个“难题”，即使对于专家来说也是如此，我当然不是。接下来，我必须弄清楚还有哪些其他函数可以用于记忆。

• 将复杂引用类型作为参数的方法呢？
• 依赖于调用它们的实例内部数据的方法呢？

最后一个是 ActiveRecord 式的数据对象。

我是否将不得不重构一周前的代码以支持记忆？

我正在尝试创建一个向泛型类添加功能的类，而不直接与包装类交互。一个很好的例子就是智能指针。具体来说，我想创建一个包装器，它为通过包装器调用的一个（或任何？）方法缓存所有 i/o。理想情况下，缓存包装器具有以下属性：

• 它不需要以任何方式更改包装类（即通用）
• 它不需要以任何方式更改包装类（即通用）
• 它不会显着改变使用对象的接口或语法

例如，像这样使用它会非常好：

虽然像这样愚蠢的事情是可以的：

我觉得这在 C++ 中应该是可能的，尽管可能在某个地方有一些语法体操。

有任何想法吗？