问题标签 [memoization]

您通常如何在初始化期间从数据库加载和存储全局常量中的内容以进行缓存？全局常量以后不会再改变。您只是在加载期间进行数据库查询并将其放入常量中，还是使用某种延迟加载机制？

我想到的是全局范围内的代码，如下所示：

我在使用空测试数据库运行测试时遇到了问题。一种选择是将所有需要的数据放在夹具中，但我想避免将每个单独的测试与他们不需要的不相关数据耦合。

以下会被认为是好的风格吗？

还是首选通用的可重用机制？

是否有一种 Pythonic 方式来封装惰性函数调用，即在第一次使用该函数f()时，它会调用先前绑定的函数g(Z)并在连续调用f()时返回一个缓存值？

请注意，记忆化可能并不完美。

我有：

该代码有效，但我想对其进行重组，以便g(Z)仅在使用该值时才调用它。我不想改变 , 的定义g(...)，而且Z缓存有点大。

编辑：我认为这f必须是一个函数，但情况可能并非如此。

我找到了一篇包含此代码的文章：

你能解释一下吗？我在这里看不懂很多东西，但最奇怪的是缓存是本地的而不是静态的，但也许我错了......

我发现了这个不错的记忆装饰器：

http://wiki.python.org/moin/PythonDecoratorLibrary#Memoize

特定的应用程序是在人工智能中，它将存在于一个不可变的状态类中。问题是我通过返回父状态的副本来执行运算符的应用，并应用了请求的运算符。copy.copy 节省了大量原本会被浪费的时间，因为大部分状态与其父状态相同。

现在，这是我的问题。如果我要在类中使用上面的 memoization 类，是否会传递 memoize 到潜在无效值的函数的 memoized 副本？我想我需要以某种方式使记忆副本无效。

我正在研究一些处理 numpy 矩阵和 ndarray 的计算密集型计算，并且通过一些挖掘，有大约十几种不实现记忆的方法，通常充满冲突，以及 ndarray 是可变对象的问题。

有没有人遇到过可以处理 numpy 对象的相当通用的 memoisation 装饰器？

最近在优化一些代码时，我们最终执行了我认为是一种“类型”的记忆，但我不确定我们应该这样称呼它。下面的伪代码不是实际的算法（因为我们的应用程序中几乎不需要阶乘，并且发布所述代码是一种攻击行为），但它应该足以解释我的问题。这是原来的：

很简单，但我们添加了固定点，这样就可以避免大量计算，例如：

当然，这意味着它12!被计算为12 * 11 * 3628800而不是效率较低的12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1。

但我想知道我们是否应该称之为记忆，因为这似乎被定义为记住过去的计算结果并使用它们。这更多是关于硬编码计算（不记住）和使用该信息。

这个过程是否有合适的名称，或者我们可以声称记忆不仅可以延伸到运行时完成的计算，还可以延伸到编译时完成的计算，甚至可以追溯到我开始编写代码之前在我脑海中完成的计算？

假设我想为Levensthein 距离（编辑距离）实现通常的动态规划算法。很容易想出递归：

这受到指数运行时间的影响，因此有必要记住该函数。我想通过使用 Data.Memocombinators 来做到这一点，并且我尝试了几种方法。这是我目前的尝试：

然而，记忆化似乎没有任何效果，尽管我希望任何记忆化都能显着改善运行时间，因为它至少是多项式的。我的实施有什么问题？如何在尽可能多地保留编辑距离的高级定义的同时获得良好的运行时间？

假设我们有一个 IO 动作，例如

这可能是一些简单的事情，例如 DNS 查找，或者针对时不变数据的一些 Web 服务调用。

让我们假设：

1. 该操作从不抛出任何异常和/或从不发散

2. 如果不是IOmonad，则该函数将是纯函数，即相同输入参数的结果始终相同

3. 该操作是可重入的，即可以安全地同时从多个线程调用它。

4. 该lookupStuff操作非常（时间）昂贵。

我面临的问题是如何正确（并且不使用任何unsafe*IO*作弊）实现可重入缓存，该缓存可以从多个线程调用，并将针对相同输入参数的多个查询合并到一个请求中。

我想我在追求与 GHC 的纯计算黑洞概念类似的东西，但在 IO“计算”上下文中。

对于所述问题，惯用的 Haskell/GHC 解决方案是什么？

我发现这个答案和这个 wiki 页面是 Haskell 中记忆化的极好介绍。然而，他们确实给我留下了一个我希望得到回答的问题：

在我看来，所使用的技术要求您“打开”（如“访问内部”）用于存储记忆的数据结构。例如，1实现了一个表结构，2实现了第 3 节中的树。是否可以使用预制的数据结构做类似的事情？例如，假设您认为这Data.Map真的很棒，并且想将您的记忆值存储在这样的Map. 一种方法可以使用这样的预制数据结构进行记忆，其中一个人不实现结构本身，而是使用预制的结构？

希望有人能给我一个关于如何思考的提示，或者更有可能纠正我对功能性记忆的误解。

编辑：我可以想到一种方法，但它一点也不优雅：如果f :: a -> b，那么一个人可能很容易制作一个 memoized version f' :: Map a b -> a -> (Map a b, b)，其中第一个参数是 memoization 存储，输出对包含一个可能更新的存储和计算的值。这种状态传递当然不是我想要的（虽然我猜它可以被包裹在一个 monad 中，但它比1和2中的方法丑几个数量级）。

编辑2：也许尝试表达我目前的（不正确的）思维方式会有所帮助。目前，我似乎一再违背自己的意愿，将自己拉入无法解决的问题

我越看这个，我就越意识到我误解了一些基本的东西。你看，我觉得 mymemo [True, False]相当于1bool的memoizer 。

继续通过 Haskell 研究 CRC，我编写了以下代码来生成用于 CRC32 计算的表：

这会正确生成表格。我想频繁访问此表，但 1) 不想将结果硬编码为代码，并且 2) 不想每次引用该表时都重新计算它。

我将如何在 Haskell 中记住这个数组？Haskell 记忆页面没有给我任何线索。