Python

Question

好吧，这个问题有点难运行ge，但我想知道我是否可以这样做。

我正在研究一个简单的斐波那契数生成器，因为我对它编程很感兴趣。所以我写了这个：

def f(n):
    if n == 1: return 1
    if n == 2: return 2
    else:
        return f(n-1) + f(n-2)

而且运行非常慢，在我的电脑上 f(30) 需要 15 秒。然后我写了这个：

def f(n):
    global a
    if n == 1: return 1
    if n == 2: return 1
    else:
        if "fib(%s)" % n in a:
            return a["fib(%s)" % n]
        else:
            z =  f(n-1) + f(n-2)
            a["fib(%s)" % n] = z
            return z

基本上将以前的结果存储在字典中，如下所示：

{'f(1)':1,'f(2)':2,'f(3)':3,'f(4)':5} 等等。在函数中，它会检查该结果是否在该字典中，然后只需使用它，而不必重做所有计算。

这使它变得更快。我可以做 f(100)，它会立即出现。以 500 为间隔，我到达 f(4000) 并且它仍然是瞬时的。唯一的问题是字典越来越大。

所以我在函数的末尾添加了a = {}，但没有用；它仍然 a 作为一个巨大的 dict。

这样做：

def f(n):
    global a
    if n == 1: return 1
    if n == 2: return 1
    else:
        if "fib(%s)" % n in a:
            return a["fib(%s)" % n]
        else:
            z =  f(n-1) + f(n-2)
            a["fib(%s)" % n] = z
            return z
    a = {}

没用。但如果我这样做：

def f(n):
    global a
    if n == 1: return 1
    if n == 2: return 1
    else:
        if "fib(%s)" % n in a:
            return a["fib(%s)" % n]
        else:
            z =  f(n-1) + f(n-2)
            a["fib(%s)" % n] = z
            return z
# now run the function
f(100)
a = {}

a 被重置为空字典。为什么会发生这种情况，我该如何解决？

Answer 1

您在函数内的 a = {} 语句从未被执行；在此之前，每条可能的执行路径都会达到 return。如果它被执行了，你不会喜欢这个结果——它会在对函数的每一次递归调用中执行，这意味着你的字典永远不会包含超过一个项目！您将不得不以某种方式检测最外层的调用，并且只清除那里的 dict，或者（更简单）像第二个示例那样在递归之外清除它。

请注意，您字典的大部分大小来自使用长字符串键的奇怪决定。用数字本身键入它（如 a[n] = z）会使它更紧凑。

（供将来参考：您在此处提出的保存先前函数调用结果的技术称为 "memoization"。）

Answer 2

尽管你有疑问，但你真正想要的是一种计算斐波那契数列的更快方法，对吧？您原来的方法的问题在于，尽管非常优雅且编码速度很快，但重复的速度非常慢。斐波那契数列有一个封闭形式的解决方案。你应该直接做这个数学来加速你的代码。按照惯例，将斐波那契数列 F(i) 视为：F(0) = 0, F(1) = 1, F(k) = F(k-1) + F(k-2) k = 2, 3 , ... 这个序列的解是（我不会在这里演示，因为不是那个地方） F(k) = (1/sqrt(5))*(a^k - b^k),其中 a = (1 + sqrt(5))/2 和 b = (1 - sqrt(5))/2。因此，您的代码可以这样实现：

def f(n):

    a = (1 + 5**.5)/2
    b = (1 - 5**.5)/2
    F = (a**n - b**n)/5**.5
    F = int(round(F)) #necessary to get an integer without the decimal part of the approximation. Afterall, you are working with irrational numbers.
    return F

对于较大的 n 值，此代码可以很好地缩放。

Python - 从函数修改字典

Python - Modify dictionary from function

dictionary

fibonacci

python-2.7