为什么记忆不是语言功能? [英] why memoization is not a language feature?

问题描述

我在想...为什么我所了解的任何语言都没有以本机作为一种语言功能来提供备忘录?

I was wondering... why memoization is not provided natively as a language feature by any language I know about?

编辑:澄清一下，我的意思是该语言提供了一个关键字，用于将给定功能指定为可记忆性，而不是除非另有指定，否则并非每个功能都会默认情况下"自动记忆.例如，fortran提供关键字PURE来指定这样的特定功能.我想编译器可以利用这些信息来记住调用，但是如果您将PURE声明为具有副作用的函数，我将忽略发生的情况.

Edit: to clarify, what I mean is that the language provides a keyword to specify a given function as memoizable, not that every function is automatically memoized "by default", unless specified otherwise. For example, fortran provides the keyword PURE to specify a specific function as such. I guess that the compiler can take advantage of this information to memoize the call, but I ignore what happens if you declare PURE a function with side effects.

推荐答案

从备忘录中获取的内容可能与编译器备忘录选项所提供的内容不同.

What YOU want from memoization may not be the same as what the compiler memoization option would provide.

您可能知道只记住最近计算的10个左右的不同值是有利可图的，因为您知道该函数的使用方式.

You may know that it is only profitable to memoize the last 10 or so distinct values computed, because you know how the function will be used.

您可能知道只记住最后2个或3个值是有意义的，因为您永远都不会使用早于此的值. (斐波那契的序列浮现在脑海.)

You may know that it only makes sense to memoize the last 2 or 3 values, because you will never use values older than that. (Fibonacci's Sequence comes to mind.)

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

You may be generating a LOT of values on some runs, and just a few on others.

您可能要扔掉"一些已记忆的值并重新开始. (我以这种方式记住了一个随机数生成器，因此我可以重播建立某种结构的随机数序列，而该结构的其他一些参数已被更改.)

You may want to "throw away" some of the memoized values and start over. (I memoized a random number generator this way, so I could replay the sequence of random numbers that built a certain structure, while some other parameters of the structure had been changed.)

作为最佳化的记忆取决于要搜索的记忆值比重新计算该值便宜得多.这又取决于输入请求的顺序.这对记忆数据库有影响:它是否使用堆栈，所有可能的输入值(可能非常大)的数组，存储桶哈希或b树?

Memoization as an optimization depends on the search for the memoized value being a lot cheaper than recomputation of the value. This in turn depends on the ordering of the input requests. This has implications for the memoization database: Does it use a stack, an array of all possible input values (which may be very large), a bucket hash, or a b-tree?

备忘编译器必须提供一刀切"的备忘，或者必须提供许多可能的替代方案以及控制替代方案的参数.在某个时候，每个人都要求用户提供自己的备忘录变得更加容易.

The memoizing compiler has to either provide a "one size fits all" memoization, or it has to provide lots of possible alternatives, and parameters to control the alternatives. At some point, it becomes easier for everyone to require the user to provide his own memoization.

这篇关于为什么记忆不是语言功能?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！