问题标签 [memoization]

我有一个计算图（带有软值），用于缓存昂贵计算的结果。

现在我有一种情况，我知道可能会在接下来的几秒钟内查找特定的键。该密钥的计算成本也比大多数密钥高。

我想在最低优先级线程中提前计算该值，以便当最终请求该值时，它已经被缓存，从而提高了响应时间。

这样做的好方法是什么：

1. 我可以控制执行计算的线程（特别是它的优先级）。
2. 避免了重复工作，即计算只进行一次。如果计算任务已经在运行，则调用线程等待该任务而不是再次计算值（FutureTask实现这一点。使用 Guava 的计算映射，如果你只调用get，但如果你将它与调用混合，则不是这样put。）
3. “预先计算值”方法是异步的和幂等的。如果计算已经在进行中，它应该立即返回，而无需等待该计算完成。
4. 避免优先级倒置，例如，如果一个高优先级线程请求该值，而一个中等优先级线程正在做一些不相关的事情，但计算任务在一个低优先级线程上排队，那么高优先级线程不能被饿死。也许这可以通过临时提高计算线程的优先级和/或在调用线程上运行计算来实现。

这如何在所有涉及的线程之间进行协调？

附加信息
我的应用程序中的计算是图像过滤操作，这意味着它们都受 CPU 限制。这些操作包括仿射变换（范围从 50µs 到 1ms）和卷积（最长 10ms）。当然，不同线程优先级的有效性取决于操作系统抢占较大任务的能力。

关于如何在 Haskell 中有效解决以下函数的任何指针，用于大量(n > 108)

我已经在 Haskell 中看到了解决斐波那契数的记忆示例，其中涉及（懒惰地）计算所有斐波那契数，直到所需的 n。但是在这种情况下，对于给定的 n，我们只需要计算很少的中间结果。

谢谢

在发现difflib.SequenceMatcherPython 标准库中的类不适合我的需要后，编写了一个通用的“差异”模块来解决问题空间。在有几个月的时间来思考它在做什么之后，递归算法似乎比需要的搜索更多，它通过在一个单独的“搜索线程”可能也检查过的序列中重新搜索相同的区域。

该diff模块的目的是计算一对序列（列表、元组、字符串、字节、字节数组等）之间的差异和相似性。初始版本比代码的当前形式慢得多，速度提高了十倍。如何将 memoization 应用于以下代码？重写算法以进一步提高任何可能的速度的最佳方法是什么？

参考： 如何优化递归算法使其不重复？

互联网上有一些用于各种不同语言的自动记忆库；但如果不知道它们的用途、使用地点以及它们的工作原理，就很难看到它们的价值。使用记忆化有哪些令人信服的论据，记忆化在哪些问题领域特别突出？不知情的信息将在这里特别感激。

假设我在 Ruby 中有一个类：

我想记住它的结果。因此，出于调试目的，我修改了这样的类：

并编写了一个使用相同参数调用该方法的测试，以查看输出了什么……而且该方法没有被记忆。这样做的正确方法是什么？

创建一个像下面这样可以为您处理记忆过程的类是“好习惯”吗？memoization 的好处是如此之大（在某些情况下，比如这个，它在我的计算机上从 501003 到 1507 个函数调用以及从 1.409 到 0.006 秒的 CPU 时间），看起来像这样的一个类会很有用。

但是，我只阅读了关于eval(). 考虑到这种方法提供的灵活性，这种用法是否可以原谅？

这可以以失去副作用为代价自动保存任何返回值。谢谢。

我一直在学习一些 Haskell，并且边做边做项目 Euler 问题。我并不真正关心欧拉问题的答案（我可以很高兴地使用蛮力，或者用其他语言来解决），而是方法。

我坚持在合理的时间内完成第 15 题。它要求从 20x20 网格的左上角到右下角的非回溯路线的数量。链接在这里

我会说这个想法是记忆（sp？）函数的想法是相当明显的，但我不确定该怎么做。我用谷歌搜索，在 Haskell Cafe 上发现了这个，我天真地试图适应，但最终得到：

这看起来很糟糕，并且执行得非常糟糕（比天真的版本慢很多）。问题是我并不真正了解 Haskell 记忆是如何工作的。

以我的代码为例，是否有人愿意解释a）为什么我的代码这么慢
b）应该如何完成（不使用可变变量，这是我遇到的一个解决方案）
c）在这种情况下memoization如何工作？

是否有可能以某种方式结合记忆和尾递归？我目前正在学习 F# 并理解这两个概念，但似乎无法将它们结合起来。

假设我有以下memoize功能（来自Real-World Functional Programming）：

和以下factorial功能：

记忆factorial并不太难，使其尾递归也不是：

但是你能把记忆和尾递归结合起来吗？我做了一些尝试，但似乎无法让它工作。或者这根本不可能？

我只是想学习一些 Lisp，所以我正在解决项目欧拉问题。我发现问题没有。14 有趣（所以如果你打算解决这个问题现在停止阅读，因为我在底部粘贴了我的解决方案）。使用我的算法时速度非常慢，但是在使用记忆化之后（我从 Paul Graham 的“on Lisp”书中复制了该函数），它的速度要快得多（大约 4 到 8 秒）。

我的问题是关于我收到的一堆警告：我做错了吗？我可以改善我的风格吗？

这是代码：

非常感谢，并原谅可能的错误，我刚刚开始使用 Lisp。溴

更新： 我想分享我写的最终代码。使用自定义外部哈希表进行记忆并改进最终循环。

我有一个动态生成图像的 CherryPy 应用程序，这些图像被多次重复使用，但每次都会生成。图像是从包含变量的查询字符串生成的，因此相同的查询字符串将始终返回相同的图像（直到我重写生成代码）并且图像不是用户特定的。

我突然想到我应该积极缓存这些图像，但我不知道该怎么做。我应该在 CherryPy 中记忆吗？我应该为 Apache做这样的事情吗？完全是另一层？