27

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

fib 0 = 0
fib 1 = 1
fib n = fib (n-2) + fib (n-1)

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

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

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

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

谢谢，阿尔伯特

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

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

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

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

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

4

6 回答 6

9

我在评论中说您的要求听起来像垃圾收集。我认为这是因为您有兴趣管理有限的内存池，不时清除它，以免它溢出。

现在想来，它更像是一种虚拟内存页面替换算法。您可以阅读该 Wikipedia 页面，了解用于解决此类问题的各种方法，例如“最近未使用”、“老化”、“时钟”、“第二次机会”等。

然而，记忆化通常不是通过限制保留的结果来完成的。上述算法所需的突变通常是不成熟的。不过，不要让这让你灰心。你有一些有趣的想法，这些想法可能是对迄今为止在 Haskell 中探索记忆可能性的有价值的补充。

有时，特定的记忆问题很适合有限的记忆。例如，可以使用带有二维记忆表的动态编程（参见维基百科的动态编程#序列比对）来比对两个基因序列。但是由于给定单元格的 DP 解决方案仅取决于前一行的结果，因此您可以从底部开始，丢弃距离当前行超过 1 的行。斐波那契数是相同的：您只需要序列中的前两个数来计算下一个数。如果您只对第n个数字感兴趣，您可以提前丢弃任何东西。

大多数记忆是为了加速存在共享子问题的递归算法。许多此类问题没有简单的方法来排序评估，以便丢弃不再需要的结果。那时，您只是在猜测，使用启发式方法（如使用频率）来确定谁可以获得对有限资源的多少访问权限。

于 2011-04-22T03:29:12.870 回答
7

不，Haskell 不会自动记忆功能。它的作用是存储值，所以如果你有

x = somethingVeryLong

在您拥有的相同范围内的其他地方

y = f x
z = g x

那么 x 将只计算一次。

这个包展示了如何使用各种键和查找表来存储记忆值。记忆通常在一个更大的函数的单次调用中使用，这样记忆的值就不会永远存在（正如你所说的那样，这将是一个问题）。如果您想要一个也使用 LRU 或其他东西忘记旧值的记忆器，那么我认为您可能需要将它放在状态单子或其他东西中；使用传统的记忆方法，你不能让 Haskell 表现得像那样。

于 2011-04-21T20:02:12.170 回答
7

Haskell 似乎没有自动记忆。还是我理解错了？

不，Haskell 没有。但是，共享表达式只计算一次。在 Paul Johnson 给出的示例x中，作为thunk存储在堆中。两者都可以在范围内引用，y并且它们引用相同的位置。一旦必须被评估，它将只被评估一次，并且只会保留评估的结果。所以这并不是真正的记忆，而是实施的结果。zxxx

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

我在一些 python 源代码中看到了装饰器@memoized 。您当然可以为它完全创建自己的装饰器/实现。完成 LRU 和您要使用的其他策略。

实现memoization的常用方法有哪些？

没有真正的common方法来实现记忆。对于类似 fib 的模式（只有一个参数，它是一个数字），在 fib-example 中使用的记忆可以设计一个通用解决方案（哈希图之一）并且它会起作用，但它也可能不是您的特定问题的最佳选择.

使用 memoisation 你有副作用，所以你可能希望缓存存在于 State monad 中。然而，一般来说，你希望你的算法尽可能纯净，所以如果它有递归，你已经陷入了一些混乱。这是因为您将递归调用函数的记忆版本，但这需要在 State monad 中运行，所以现在您的整个函数必须在 State monad 中运行。这也会影响惰性，但您可以尝试惰性状态 monad。

牢记这一点：很难实现良好的自动记忆。但你可以轻松地走很长一段路。自动记忆功能可能涉及程序转换，在固定点中编写东西可能会有很长的路要走。

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

一旦你有了记忆的基本机制，你就可以为记忆表调整查找和存储功能，以实现 LRU 或其他一些保持内存消耗小的机制。也许您可以从这个 C++ 示例中获得 LRU 的想法。

于 2011-04-22T06:48:43.120 回答
4

例如实现自动记忆，您可以查看Factor 编程语言及其记忆词汇。例如，简单的斐波那契数生成器：

: fib ( n -- n )
    dup 1 > [
        [ 1 - fib ]
        [ 2 - fib ]
        bi +
    ] when ;

可以通过用“MEMO:”替换“:”单词来记忆

MEMO: fib ( n -- n )
    dup 1 > [
        [ 1 - fib ]
        [ 2 - fib ]
        bi +
    ] when ;

在这种情况下，fib 输入和相应的输出将透明地存储在内存字典中。

因子语言语法可能令人困惑:)。我建议您观看Google Tech Talks about Factor 的视频演示，以了解如何以这种方式实现记忆化。

于 2011-04-28T08:01:33.677 回答
1

没有确切的答案，但是这个页面：http ://www.haskell.org/haskellwiki/Memoization提供了有关 Haskell 中记忆化的想法，还显示了可能感兴趣的斐波那契数列的基于列表的实现。

于 2011-04-21T20:30:14.803 回答
0

在 Maple 中，您可以使用该选项remember

F := proc(n) option remember;
    if n<2 then n else F(n-1)+F(n-2)
    end if
end proc;
于 2020-01-24T14:22:10.930 回答