1

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

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。

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

这个过程是否有合适的名称，或者我们可以声称记忆不仅可以延伸到运行时完成的计算，还可以延伸到编译时完成的计算，甚至可以追溯到我开始编写代码之前在我脑海中完成的计算？

4

4 回答 4

4

我称之为预计算而不是记忆。您并没有真正记住在计算给定输入的最终答案的过程中所做的任何计算，而是预先计算了特定输入的一些固定数量的答案。据我了解，记忆化实际上更类似于“缓存”一组结果，因为您计算它们以供以后重用。如果您要存储计算出的每个值，以便以后不需要再次重新计算，那就是记忆化。您的解决方案不同之处在于您从不存储程序中的任何“计算”结果，只存储已预先计算的固定点。使用记忆功能，如果您使用不同于预先计算的输入之一重新运行函数，则不必重新计算结果，

于 2011-03-22T03:09:31.520 回答
1

无论您是否对结果进行硬编码，这仍然是记忆，因为您已经计算了希望再次计算的结果。现在这可能以运行时或编译时的形式出现。但无论哪种方式，它都是记忆。

于 2011-03-22T03:04:34.980 回答
1

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

例如参见...维基百科

或者 ...

  1. 记忆化记忆化一词由唐纳德·米奇（Donald Michie，1968 年）创造，指的是使函数 自动 记住先前计算结果的过程。近年来，随着函数式语言的兴起，这个想法变得越来越流行。Field 和 Harrison (1988) 用了一整章的篇幅来讨论它。基本思想只是保留一个先前计算的输入/结果对的表格。

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

关联

于 2011-03-22T03:06:09.120 回答
0 
def memoisation(f):
    dct = {}
    def myfunction(x):
        if x not in dct:            
            dct[x] = f(x)
        return dct[x]
    return myfunction

@memoisation
def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

def nb_appels(n):
    if n==0 or n==1:
        return 0
    else:
        return  1 + nb_appels(n-1) + 1 + nb_appels(n-2)


print(fibonacci(13))
print ('nbappel',nb_appels(13))
于 2020-04-19T20:20:23.320 回答