0

我真的很喜欢你在理解 Python 中的 Memoization 使用方面的帮助。我是 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]

这是我看到的使用记忆化评估斐波那契数的代码，这是什么[0,1]+[-1]*(n-1)意思？你能解释一下这种类型的写作代表什么吗？

4

6 回答 6

1

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

于 2013-02-17T12:45:20.950 回答
1

[-1]*5 将创建一个包含五个元素为 -1 的新列表，即 [-1 -1 -1 -1 -1]

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

于 2013-02-17T12:47:27.037 回答
0

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

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]。由于您没有坚持mem对 的调用fib_mem()，因此它的运行速度会慢一个数量级。

于 2013-02-17T13:23:36.150 回答
0

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

[0,1] 是一个包含两个元素的列表，第一个是整数 0，第二个是整数 1。

在 Python 中使用 memoization 的这种函数的合理实现是：

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-17T12:45:28.493 回答
0

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

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

更多解释：

列表[0, 1, -1, ..., -1]存储计算的斐波那契序列（记忆）。最初它只包含两个有效值：0 和 1，所有“-1”元素表示该索引处的序列尚未计算。此备忘录作为第二个参数传递给 function fib_mem_helper。如果指定索引（即i）的斐波那契数尚未计算（测试是否mem[i] == -1），fib_mem_helper将递归计算它并将其存储到mem[i]. 如果已经计算过了，直接从备忘录中返回，无需重新计算。

这就是整个故事。

最后一句话：

这段代码效率不够高，尽管它使用了记忆。事实上，它每次调用时都会创建一个新列表。fib_mem例如，如果您调用fib_mem(8)两次，第二次调用仍然需要重新创建一个列表并重新计算所有内容。原因是您将备忘录存储在fib_mem. 要修复它，您可以将 memo 保存为外部的字典fib_mem。

于 2013-02-17T13:04:55.633 回答
0

当在某些函数上使用 memoization 时，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),

具有记忆化的相同算法需要几毫秒。自己试试吧！

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-08T23:30:33.203 回答