问题标签 [memoization]

我正在尝试记住以下功能：

看着这个我想出了以下解决方案：

然后我可以这样称呼：

是否有一种更简单、更简洁和通用的方法（注意我必须如何在gwlist函数中硬编码最大网格尺寸以便从 2D 转换为 1D 空间，以便我可以访问记忆列表）在 Haskell 中记忆具有多个参数的函数？

我一直认为 Haskell 会做某种自动智能记忆。例如，朴素的斐波那契实现

因此会很快。现在我读了这篇文章，似乎我错了——Haskell 似乎没有自动记忆。还是我理解错了？

是否有其他语言可以进行自动（即隐式，非显式）记忆？

实现memoization的常用方法有哪些？在我见过的所有示例实现中，它们都使用哈希图，但它的大小没有任何限制。显然，这在实践中是行不通的，因为您需要某种限制。鉴于此，它变得更加复杂，因为当您达到极限时，您必须丢弃一些数据。那里变得复杂了：限制是否应该是动态的并且经常使用的功能应该比不经常使用的功能具有更高的限制？当你达到极限时你会扔掉什么条目？只是最近用过的吗？在这种情况下，您还需要另外对数据进行排序。您可以使用链表和哈希映射的某种组合来实现这一点。这是常见的方式吗？

您能否链接（或参考）一些常见的现实世界实现？

谢谢，阿尔伯特

编辑：我最感兴趣的是我描述的那个问题，即如何实现这样的限制。对解决此问题的任何论文的任何引用都会非常好。

编辑：可以在这里找到一些自己的想法和示例实现（有限制） 。

编辑：我不是要解决特定应用程序中的特定问题。我正在寻找可以全局应用于（纯功能）程序的所有功能的记忆通用解决方案（因此不实现内存限制的算法不是解决方案）。当然，（可能）没有最佳/最佳解决方案。但这使我的问题不那么有趣。

为了尝试这样的解决方案，我考虑将其添加到 Haskell 作为优化。我真的很想知道它的表现会有多好。

我想知道是否有人已经这样做了。

我刚开始学习 Haskell，并作为练习进入了一个欧拉计划问题，其中斐波那契数相加。我当前的方法是这个函数，它创建一个包含下一个元素的新列表：

我找到了iterate在结果上重新应用函数的函数。但是，结果是一个列表列表，[[2,1],[3,2,1],[5,3,2,1],..]. iterate当我对中间结果不感兴趣时​​，有什么替代方法？我想对takeWhile最后生成的数字做一个条件。这是完全错误的思考方式吗？

（我已经看到了生成斐波那契数列的更好/更短/更好的方法，所以我并不是真的在寻找有关该fib函数的反馈 - 但我想让它工作，无论是否是次优方法）

在具有惰性语义的纯函数式语言（例如 Haskell）中，计算结果被记忆化，因此对具有相同输入的函数的进一步评估不会重新计算值，而是直接从记忆值的缓存中获取。

我想知道这些记忆值是否会在某个时间点被回收？

1. 如果是这样，这意味着必须在以后重新计算记忆值，并且记忆化的好处并不是那么退出恕我直言。
2. 如果不是，那么好吧，这很聪明，可以缓存所有内容......但这是否意味着程序 - 如果运行足够长的时间 - 总是会消耗越来越多的内存？

想象一个程序执行密集的数值分析：例如，使用二分法算法查找数十万个数学函数列表的根。

每次程序评估具有特定实数的数学函数时，结果都会被记忆。但是在算法过程中再次出现完全相同的实数的可能性很小，从而导致内存泄漏（或者至少是非常糟糕的使用）。

我的想法是，记忆值可能只是“限定”到程序中的某些内容（例如，当前延续、调用堆栈等），但我无法找到关于该主题的实用内容。

我承认我没有深入研究 Haskell 编译器的实现（懒惰？），但是请有人向我解释一下它在实践中是如何工作的？

编辑：好的，我从前几个答案中理解了我的错误：纯语义意味着参照透明，这反过来并不意味着自动记忆，但只是保证不会有问题。

我认为网络上的一些文章对此具有误导性，因为从初学者的角度来看，Referential Transparency 属性似乎很酷，因为它允许隐式记忆。

我有这样的课：

我想知道

1）这是否违反了静态类不应该有状态的短语？

2）我怎样才能修改函数，使它们可以接受任何函数（而不是我上面只适用于F(TResult)and的情况F(T, TResult)。我的意思是我可以创建另一个函数，即：

等等，但显然它根本不能很好地扩展。

我将如何编写这样的装饰器。我希望能够在调用装饰器时指定 max_hits 的值（或者可以选择将其省略）。

例如，期望的用途是

或者

（使用第一个示例给出了关于不正确参数的错误。）

装饰师：

对于我正在从事的项目，有许多州可以依靠计算来返回相同的结果（并且没有副作用）。显而易见的解决方案是对所有昂贵的功能使用记忆。

我需要有处理多个状态的记忆（这样我就可以使一个缓存集无效而不使另一个无效）。有人知道这类事情的好 C 库吗？（请注意，它不能是 C++，我们说的是 C。）

我在 Python 中使用过一些很好的实现，它们使用装饰器能够灵活地记忆一堆不同的函数。我有点想知道是否有一个通用库可以用 C 做类似的事情（尽管可能使用显式函数包装而不是方便的语法）。我只是认为，当这是一个足够普遍的问题时，必须为每个函数单独添加缓存是愚蠢的，必须有一些现成的解决方案。

我要寻找的特征如下：

1. 可以缓存具有各种输入和输出类型的函数
2. 管理多个不同的缓存（因此您可以拥有短期和长期缓存）
3. 具有很好的使缓存失效的功能
4. 旨在通过包装函数使用，而不是更改现有函数

有人知道可以处理所有或大部分这些要求的 C 实现吗？

不知道这个问题到底要谷歌什么，所以我将它直接发布到 SO：

1. Haskell 中的变量是不可变的
2. 纯函数应该为相同的参数产生相同的值

从这两点可以推断，如果您somePureFunc somevar1 somevar2在代码中调用两次，那么只有在第一次调用期间计算值才有意义。结果值可以存储在某种巨大的哈希表（或类似的东西）中，并在随后调用该函数时进行查找。我有两个问题：

1. GHC真的会做这种优化吗？
2. 如果是这样，在重复计算实际上比查找结果更便宜的情况下，行为是什么？

谢谢。

在阅读了几次之后，我仍然不明白这个来自Stoyan Stefanov 的“JavaScript 模式”第 76 页的示例代码是如何工作的。我还不是忍者。但对我来说，它读起来就像只存储一个空对象：

除非将看不见的“昂贵操作”存储回result，否则我看不到任何保留。

结果存储在哪里？

PS：我已经阅读了 John Resig 的 Learning Advanced JavaScript 中的 Caching the return results of a function，这是一个类似的练习，我得到了那个。但是这里的代码不同。

The bottom-up approach (to dynamic programming) consists in first looking at the "smaller" subproblems, and then solve the larger subproblems using the solution to the smaller problems.

The top-down consists in solving the problem in a "natural manner" and check if you have calculated the solution to the subproblem before.

I'm a little confused. What is the difference between these two?