在Python中的记忆化

我真的很喜欢你的帮助，了解这个使用Python中的Memoization。我是Python的新手，我不确定如何理解这种语法。在Python中的记忆化

def fib_mem(n): 
    return fib_mem_helper(n,[0,1]+[-1]*(n-1)) 

def fib_mem_helper(i,mem): 
    if mem[i] == -1: 
     mem[i]=fib_mem_helper(i-1,mem) + fib_mem_helper(i-2,mem) 
     return mem[i]

这是我看到了使用记忆化avaluating Fibonacci数代码，这是什么意思[0,1]+[-1]*(n-1)？你能向我解释一下这种类型的文字代表什么？

来源

2013-02-17 Joni

代码缩进在python中非常重要，所以请复制合适的缩进代码和“;”字符不在行尾使用。 – eLRuLL 2013-02-17 12:44:49

提供代码时请注意，它是正确的。如果不是，那么帮助就更难了。（对于这种情况，这意味着缩进正确，其他语法如'：'而不是';'用于'def'和'if'语句。） – 2013-02-17 12:46:54

[0, 1] + [-1] * (n - 1)表示“连接两个列表，一个是[0, 1]，另一个是-1重复n-1次”。

来源

2013-02-17 12:45:20

奇怪的编码，但。看起来像语法错误。但根据你的问题：

[0,1]是具有两个元素的列表，第一个是整数0和第二个是一个整数1

明智执行与记忆化这样的功能的在Python将是：

def fib(i): 
    try: 
     return fib._memory[i] 
    except KeyError: 
     pass 
    if i == 1 or i == 2: 
     return 1 
    else: 
     f = fib(i-1) + fib(i-2) 
     fib._memory[i] = f 
     return f 
fib._memory = {}

来源

2013-02-17 12:45:28

[-1] * 5将创建一个新的列表具有五个元件是-1，即[-1 -1 -1 -1 -1]

[0 1 ] + [ - 1] * 5会将两个列表追加为[0 1 -1 -1 -1 -1 -1]

来源

2013-02-17 12:47:27 Anil

首先，我不得不说，即使在编辑之后，你的代码仍然有一个错误的缩进：return mem[i]应该是缩进。

在列表操作中，“+”表示串联，“*”表示重复，所以[0,1]+[-1]*(n-1)意味着列表：[0,1，-1，...，-1]（总共（n-1）个负1 ）。

更多说明：

列表[0, 1, -1, ..., -1]存储计算斐波纳契序列（记忆化）。最初它只包含两个有效值：0和1，所有“-1”元素意味着该索引处的序列还没有被计算。此备忘录作为第二个参数传递至功能fib_mem_helper。如果没有计算出指定的索引（即i）的斐波那契数字（测试是否为mem[i] == -1），则fib_mem_helper将递归计算并将其存储到mem[i]。如果已经计算出来，只需从备忘录中返回而无需重新计算。

这就是整个故事。

一锤定音：

这个代码是没有足够有效的，但它需要使用记忆化的。实际上，每次调用fib_mem时，它会创建一个新的列表。例如，如果您拨打fib_mem(8)两次，第二个电话仍然需要重新创建列表并重新计算所有内容。原因是您将备注存储在的范围内fib_mem。要修复它，您可以将备忘录保存为fib_mem以外的字典。

来源

2013-02-17 13:04:55

记忆是一种避免重新计算相同问题的技术。我会回到你的问题，但这是一个更容易理解的解决方案。

mem = {0:0, 1:1} 

def fib(n): 
    global mem 
    if mem.get(n,-1) == -1: 
     mem[n] = fib(n-1) + fib(n-2) 
    return mem[n]

通过使mem一个全局变量，你可以利用记忆化的跨越调用fib()。行mem.get(n,-1) == -1检查mem是否已包含n的计算。如果是，则返回结果mem[n]。否则，它将递归调用fib()来计算fib(n)并将其存储在mem[n]中。

让我们来看看你的代码。第二个参数fib_mem_helper(n,[0,1]+[-1]*(n-1))传递格式为[0,1，-1，-1，...]的列表，长度为(n+1)。在fib_mem_helper函数中，该列表由变量mem引用。如果mem[i]结果为-1，则计算m[i];否则使用mem[i]的已计算结果。由于您不会在fib_mem()的呼叫范围内坚持mem，因此它的运行速度要慢一个数量级。

来源

2013-02-17 13:23:36 sidi

在某些功能上使用记忆时，python的加速可能会达到百万倍或更多。这是斐波那契系列的一个例子。传统的递归方式就是这样，需要永远。

def recursive_fibonacci(number): 
    if number==0 or number==1: 
     return 1 
    return recursive_fibonacci(number-1) + recursive_fibonacci(number-2) 

print recursive_fibonacci(50),

与memoization相同的算法需要几毫秒。自己试试！

def memoize(f): 
    memo={} 
    def helper(x): 
     if x not in memo: 
      memo[x]=f(x) 
     return memo[x] 
    return helper 

@memoize 
def recursive_fibonacci(number): 
    if number==0 or number==1: 
     return 1 
    return recursive_fibonacci(number-1) + recursive_fibonacci(number-2) 

print recursive_fibonacci(50),

来源

2014-11-08 23:30:33

在Python中的记忆化

回答

相关问题