问题标签 [memoization]

我有一个尚未实施的想法，因为我担心我可能会找错树……主要是因为谷歌搜索该主题返回的结果太少。

基本上我有一些很慢的 SQL 查询，很大程度上是因为它们的子查询很耗时。例如，他们可能会做一些事情，比如“给我数一下所有 10-15 岁男孩骑过的红色自行车”。这很昂贵，因为它会在所有自行车中晃动，但最终结果是一个数字。而且，就我而言，我真的不需要这个数字是 100% 最新的。

此类问题的最终解决方案似乎是应用基于 OLAP 的引擎来预缓存这些排列。但是，在我的情况下，我并没有真正尝试围绕大量指标对数据进行切片和切块，而且我不想让我的架构复杂化，因为另一个进程/数据存储正在运行。

所以......我的想法基本上是在数据库中记住这些子查询。我可能有一个名为“BicycleStatistics”的表，它可能会将上面那个子查询的输出存储为它的输入和输出的名称值对。

前名称：“c_red_g_male_a_10-15”值：235

并且有一种机制可以在查询运行时将这些值存储到该表中。

有没有人遇到过这种情况并尝试过类似的事情？我认为这样的解决方案比“在数据库中投入大量 RAM 并让数据库处理”更有价值的原因是（A）我的数据库大于我可以方便地投入它的 RAM 量，并且（ B）数据库将确保我获得这些统计数据的准确数字，而我的最大胜利是，我可以接受这些数字已经过时一两天。

感谢您的任何想法/反馈。

汤姆

当前流行的函数式语言中是否有任何一种对记忆化有很好的支持？如果我要根据记忆化的强度来选择一种，你会推荐它吗？为什么？

更新：我正在寻找优化有向图（其中节点可以是函数或数据）。当图中的节点更新时，我希望仅当其他节点的值依赖于更改的节点时才重新计算它们。

Update2：需要免费或开源语言/运行时。

我正在使用 Ruby on Rails，我需要存储通过连接到另一台服务器获得的搜索结果集。问题是我不想将结果集存储在会话中，我想要一些可以在多个请求中存储结果集对象的东西。

查询需要时间，所以我不想重复。有没有办法可以存储对象或缓存对象，这样我就不必一次又一次地查询它？

可以使用某种对象存储吗？

任何帮助都会很棒。

如果记忆是一种选择，我如何记忆对象？连接仍然需要时间，所以如何存储结果集。

使用此处介绍的方法：http: //cslibrary.stanford.edu/110/BinaryTrees.html#java

我有一种感觉，它可能是 n(n-1)(n-2)...1，即 n！

如果使用记忆器，复杂度是 O(n) 吗？

我正在寻找一种算法来计算pow()尾递归并使用记忆来加速重复计算。

性能不是问题；这主要是一项智力练习——我花了一趟火车，pow()想出了我能想到的所有不同的实现，但无法想出一个我满意的具有这两个属性的实现。

我最好的镜头如下：

它可以工作，但它不会记住所有计算的结果 - 只有那些具有指数1..exp/2和exp.

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

众所周知，System.Transactions 将涉及到同一数据库的多个连接的事务升级到 DTC。下面的模块和帮助程序类ConnectionContext旨在通过确保对同一数据库的多个连接请求返回相同的连接对象来防止这种情况。从某种意义上说，这就是记忆，尽管有很多东西被记忆，第二个依赖于第一个。有没有办法在这个模块中隐藏同步和/或可变状态（可能使用记忆），或者可能以更实用的风格重写它？

（通过连接字符串获取连接时没有锁定可能一文不值，因为 Transaction.Current 是ThreadStatic。）

我正在尝试为具有任意数量参数的函数创建一个记忆接口，但我失败了，我觉得我的解决方案不是很灵活。我试图为一个函数定义一个接口，该接口在执行时会自动记忆，每个函数都必须实现这个接口。这是一个带有两个参数的指数移动平均函数的示例：

这是我对该功能的测试：

更新：
感谢您指出我的 n00bish 错误...我总是忘记在秒表上调用 Reset！

我也看到了另一种记忆方法......它不提供 n 参数记忆，但我使用接口的方法并没有多大优势，因为我必须为每个函数编写一个类。有没有一种合理的方法可以将这些想法合并成更强大的东西？我想让记住一个函数更容易，而不是让用户为他们打算使用的每个函数编写一个类。

如何在 Scheme 中使用数组？

特别是，我正在尝试使用 memoization 实现递归斐波那契过程。数组甚至存在于 Scheme 中吗？

如果没有，我该如何实现记忆？

作为一名 clojurian 新手，有人建议我通过Project Euler问题作为学习语言的一种方式。这绝对是提高技能和获得信心的好方法。我刚刚完成了对问题 #14的回答。它工作得很好，但为了让它有效地运行，我必须实现一些记忆。由于我的代码的结构方式，我无法使用预打包的memoize功能，而且我认为无论如何推出自己的代码是一种很好的体验。我的问题是是否有一种很好的方法可以将我的缓存封装在函数本身中，或者我是否必须像我所做的那样定义一个外部缓存。此外，任何使我的代码更惯用的提示将不胜感激。