这是否被认为是记忆？

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

def factorial (n): 
    if n == 1 return 1 
    return n * factorial (n-1)

很简单，但我们增加了固定点，这样可避免较大的数字大量的计算，是这样的：

def factorial (n): 
    if n == 1 return 1 
    if n == 10 return 3628800 
    if n == 20 return 2432902008176640000 
    if n == 30 return 265252859812191058636308480000000 
    if n == 40 return 815915283247897734345611269596115894272000000000 
    # And so on. 

    return n * factorial (n-1)

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

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

这个过程是否有一个合适的名称，或者我们可以声称memoisation不仅延伸到运行时所做的计算，还包括那些在编译时完成的计算，甚至在我开始之前回到我脑海中完成的计算编写代码？

来源

2011-03-22 paxdiablo

是的。这是一种记忆。你还需要知道什么？ – 2011-03-22 03:00:37

_这是我需要知道的。它不会与维基百科条目凝结在一起，它具体指出：“一个memoized函数”记住“与某些特定输入集相对应的结果。随后的记忆输入的调用返回记忆的结果，而不是重新计算它，......。我认为可能会有不同的术语，因为它不记得它，而是将其硬编码。 – paxdiablo 2011-03-22 03:03:01

好吧，到目前为止我有两个答案，是和否。这意味着可能需要引用权威来源。我会离开这个问题几个小时，看看会发生什么。 – paxdiablo 2011-03-22 03:08:40

我把它叫做预先计算，而不是记忆化。你并没有真正记得你在计算给定输入的最终答案的过程中所做的任何计算，而是预先计算特定输入的某些固定数量的答案。根据我的理解，Memoization实际上更类似于在计算它们以备后用时“缓存”一组结果。如果您要存储计算的每个值，以便以后不需要重新计算，那就是记忆。您的解决方案不同之处在于，您不会存储程序中的任何“计算”结果，只会存储预先计算的固定点。通过记忆，如果您重新输入与预先计算的输入不同的输入的函数，则不必重新计算结果，只需重新使用它即可。

来源

2011-03-22 03:09:31 tvanfosson

无论你是否对结果进行硬编码，这仍然是记忆，因为你已经计算出了期望再次计算的结果。现在这可能会以运行时或编译时间的形式出现..但无论如何，它都是memoization。

来源

2011-03-22 03:04:34

记忆在运行时完成。您正在编译时进行优化。所以，事实并非如此。

例如参见... Wikipedia

或者...

记忆化术语记忆化由Donald米基（1968）提出的，用以指过程，通过该函数是记得自动记得以前的计算结果。随着功能语言的兴起，这个想法近年来变得越来越流行;菲尔德和哈里森（1988）致力于整个篇章。基本思想就是保留一张先前计算的输入/结果对的表格。

彼得·诺维格 加州大学的（粗体是我的）

Link

来源

2011-03-22 03:06:09

这个神秘的“运行时间”是什么时候？我可以将以前运行的结果缓存在持久存储中吗？如果是这样，我可以缓存以前运行的结果在可执行代码本身吗？如果是这样，我可以缓存源代码中以前运行的结果吗？我不明白为什么有一个不包括“在源代码中缓存先前结果”的随机行。 – 2011-03-22 09:43:57

@ S.Lott与往常一样，单词只是单词，定义总是令人反感。我认为OP使用的概念与通常的memoization定义不一样，因为1）他被迫修改函数来存储新的/其他的结果，以及2）通常意义上的“函数会自动记住先前的计算结果“没有人为干预（因此_automatically_）。如果没有这样的协议，没有人会死。 – 2011-03-22 11:43:33

@belisarius：那么，通过memoization测试的方法是让函数重写它自己的源代码？ – 2011-03-22 12:07:09

这是否被认为是记忆？

回答

相关问题