python

Question

我写了下面两段代码来计算斐波那契数列的一个元素。

def fib(n):
    zero, one = 0, 1
    k = 1
    while k < n:
        zero, one = one, zero + one
        k = k + 1
    return one, ls

def fib2(n, memo=None):
    if memo is None:
        memo = {}
    if n == 1 or n == 2:
        return 1
    if n in memo:
        return memo[n]
    else:
        memo[n-1] = fib2(n-1, memo)
        memo[n-2] = fib2(n-2, memo)
        return memo[n-1] + memo[n-2]


##import timeit
##
##print('Fibonacci 1:', timeit.timeit('fib(10000)', '''def fib(n):
##    zero, one = 0, 1
##    k = 1
##    while k < n:
##        zero, one = one, zero + one
##        k = k + 1
##    return one''', number=100))
##
##print('Fibonacci 2:', timeit.timeit('fib2(10000)', '''import sys; sys.setrecursionlimit(10001);
##def fib2(n, memo=None):
##    if memo is None:
##        memo = {}
##    if n == 0 or n == 1:
##        return 1
##    if n in memo:
##        return memo[n]
##    else:
##        memo[n-1] = fib2(n-1, memo)
##        memo[n-2] = fib2(n-2, memo)
##        return memo[n-1] + memo[n-2]''', number=100))

我在 fib 中使用了一个简单的 while 循环，fib2 是相同循环的递归实现。但事实证明 fib2 异常慢。我想知道这是为什么。是因为 fib2 创建了很多帧吗？我是否正确实施了 fib2？

谢谢。

Answer 1

根据您的原始迭代解决方案对这个简化的递归版本进行计时——首先将递归限制提高约 1% 到 10%：

def fib2(n, memo={0: None, 1: 1, 2: 1}):
    if n in memo:
        return memo[n]

    previous = fib2(n - 1)  # implicitly computes fib2(n - 2)

    result = memo[n] = previous + memo[n - 2]

    return result

我没有将 memo 作为递归的参数传递，因为当默认参数设置为可以修改的结构时，我正在利用 "problem"。

第一次调用时，上述解决方案比我机器上的原始迭代解决方案慢 4.5 倍——之后，记忆化接管了。我们可以通过将 "memory" 从字典更改为列表来改进 space 和时间，因为所有键都是连续整数：

def fib3(n, memo=[None, 1, 1]):
    if n < len(memo):
        return memo[n]

    previous = fib3(n - 1)  # implicitly computes fib3(n - 2)

    result = previous + memo[-2]

    memo.append(result)

    return result

在我的机器上，第一次调用的超时时间比迭代解决方案慢 3 倍。但是，我们可以使用递归在速度方面做得更好：

def fib4(n, res=0, nxt=1):
    if n == 0:
        return res
    return fib4(n - 1, nxt, res + nxt)

这仅比没有记忆的迭代解决方案慢 2 倍 and/but。在具有尾调用优化的语言中（即不是 Python），这可能会 become/tie 迭代。

python - 斐波那契计算时差

python - Fibonacci Computing Time Difference

recursion

fibonacci

python-3.x