35

我想知道......为什么我所知道的任何语言都没有原生地提供记忆作为语言功能？

编辑：澄清一下，我的意思是语言提供了一个关键字来将给定的函数指定为可记忆的，而不是每个函数都“默认”自动记忆，除非另有说明。例如，fortran 提供关键字 PURE 来指定特定的函数。我猜编译器可以利用这些信息来记忆调用，但我忽略了如果你声明 PURE 一个具有副作用的函数会发生什么。

4

11 回答 11

47

您希望从记忆中获得的可能与编译器记忆选项提供的不同。

您可能知道仅记住最近 10 个左右不同的计算值是有利可图的，因为您知道如何使用该函数。

您可能知道只记住最后 2 或 3 个值才有意义，因为您永远不会使用比这更早的值。（我想到了斐波那契数列。）

您可能会在某些运行中生成很多值，而在其他运行中仅生成一些值。

您可能想“丢弃”一些记忆值并重新开始。（我以这种方式记忆了一个随机数生成器，因此我可以重播构建某个结构的随机数序列，而该结构的其他一些参数已被更改。）

作为优化的记忆化依赖于搜索记忆值比重新计算值便宜得多。这又取决于输入请求的顺序。这对记忆数据库有影响：它是使用堆栈、所有可能输入值的数组（可能非常大）、桶散列还是 b 树？

记忆编译器必须要么提供“一刀切”的记忆，要么必须提供许多可能的替代方案，以及控制替代方案的参数。在某些时候，每个人都更容易要求用户提供自己的备忘录。

于 2009-12-19T15:56:19.390 回答
22

因为编译器必须发出语义正确的程序。你不能在不改变程序语义的情况下记忆一个函数，除非它是引用透明的。在大多数编程语言中，并非所有函数都是引用透明的（纯函数式编程语言除外），因此您无法记住所有内容。但是需要一种机制来检测引用透明度，这太难了。

于 2009-12-19T14:51:39.757 回答
13

在 Haskell 中，对于您定义的不带参数的（纯）函数，记忆是自动的。Wiki 中的斐波那契示例实际上是我能想到的最简单的可演示示例。

Haskell 可以做到这一点，因为您的纯函数被定义为每次都产生相同的结果；当然，依赖副作用的一元函数不会被记忆。

我不确定上限是多少——显然，它不会记住比可用内存更多的东西。而且我也不确定记忆是否发生在编译时（如果值可以在编译时确定），或者它是否总是在第一次调用函数时发生。

于 2009-12-19T15:04:01.617 回答
12

Clojure 有一个 memoize 功能（http://richhickey.github.com/clojure/clojure.core-api.html#clojure.core/memoize）：

memoize
function

Usage: (memoize f)

Returns a memoized version of a referentially transparent function. The
memoized version of the function keeps a cache of the mapping from arguments
to results and, when calls with the same arguments are repeated often, has
higher performance at the expense of higher memory use.
于 2009-12-19T15:02:04.393 回答
6

因为当可以很容易地在语言本身中实现时，您不应该将其实现为语言特性。记忆功能属于库，这正是大多数语言所放置的地方。

于 2009-12-19T14:06:20.307 回答
6

A)记忆化以空间换时间。我想这可能会变成一个相当不受约束的属性，从某种意义上说，必须存储的数据程序或库的数量可能会很快消耗大部分内存。

对于几种语言，memoization 很容易实现并且很容易根据给定的要求进行定制。

以对大量文本进行自然语言处理为例，您不想一遍又一遍地计算文本的基本属性（字数、频率、共现……）。在这种情况下，与内存缓存相比，与对象序列化相结合的记忆化可能很有用，因为您可以在未更改的语料库上多次运行您的应用程序。

B）另一方面：对于相同的给定输入，所有函数或方法产生相同的输出是不正确的。无论如何，记忆化的一些关键字或语法是必要的，以及配置（内存限制，失效策略，......）......

于 2009-12-19T14:26:55.780 回答
1

并非所有语言本身都支持函数装饰器。我想这将是一种更通用的支持方法，而不仅仅是支持记忆。

于 2009-12-19T13:57:55.617 回答
1

您的问题也为您学习更多语言提供了解决方案。我认为 Lisp 支持记忆，我知道 Mathematica 支持。

于 2009-12-19T14:36:11.113 回答
1

把问题反过来。为什么应该？正如有人所说，它可以放在库中，因此无需向语言添加语法，它仅适用于难以自动识别的纯函数（除非您强制程序员对其进行注释）。也很难确定记忆化是否会加快速度。我不认为这是编程语言的理想功能。

于 2009-12-19T15:01:07.660 回答
1

我真的认为这样的选择应该是。

在数据处理任务中，有一个不可变的输入数据（例如，作为时间序列，对于给定的时间，只要一个值已知，它就永远不会改变）。考虑到今天 RAM 的可负担性，如果函数结果仅取决于此类不可变数据，则将其记忆而不是每次需要时都重新读取是合理的。目前我（在 Scala 和 C# 中）手动引入一个内存存储表并编写 3 个函数而不是一个 - 一个从文件/db/ws 读取值，一个将其存储到内存表中，一个用于包装它们并从内存中读取（如果可用）或调用原始函数（如果没有）。我认为这可以而且应该作为关键字实现并在幕后完成。

于 2010-09-04T04:14:06.017 回答
1

为了让记忆作为一种语言功能发挥作用，有几个要求。

  1. 编译器需要识别有效的记忆函数（例如，它们是引用透明的）。
  2. 运行时必须能够在不降低整体性能的情况下智能地选择候选记忆。

另一种语言有一些假设，但如果我们可以通过即时编译 Java VM 中的热点来提高性能，那么我们肯定可以编写一个自动化的记忆系统。

虽然这很重要，但我认为这在理论上都是有可能在一种语言（尤其是解释型语言）中获得性能提升，并且是一个值得研究的领域。

于 2013-07-04T13:30:48.137 回答