让fibo更快

Question

我需要编写一个代码来给出一个数字并打印出 F[number]。这段代码很漂亮 slow.Any 关于更快代码的想法？

 while True:
      n=input()
      if n=='END' or n=='end':
         break
      class Fibonacci:
            def fibo(self, n):
                if int(n) == 0:
                   return 0
                elif int(n) == 1:
                   return 1
                else:
                  return self.fibo(int(n)-1) + self.fibo(int(n)-2)
      f=Fibonacci()
      print(f.fibo(n))

Answer 1

我在这个 post 中写了一些关于更快的斐波那契的内容，也许其中一个对您有用？ https://sloperium.github.io/calculating-the-last-digits-of-large-fibonacci-numbers.html

无论如何。您的代码非常慢，因为您得到指数运行一遍又一遍地调用相同子树的时间。

您可以尝试线性解决方案：

def fib3(n):
    if n == 0:
        return 0
    f1 = 0
    f2 = 1

    for i in range(n-1):
        f1,f2 = f2, f1+f2
    return f2

Answer 2

您可以使用字典来记忆函数：

class Fibonacci:
    memo = {}
    def fibo(self, n):
        if n in self.memo:
            return self.memo[n]
        if int(n) == 0:
            value = 0
        elif int(n) == 1:
            value = 1
        else:
            value = self.fibo(int(n) - 1) + self.fibo(int(n) - 2)
        self.memo[n] = value
        return value

Answer 3

使用动态规划：这可以防止它每次都计算到 0 和 1：

memory = {0:0, 1:1}
def fibo(n):
    if n in memory:
        return memory[n]
    else:
        ans = fibo(int(n)-1) + fibo(int(n)-2)
        memory[n] = ans
        return ans

测试：

>>> fibo(1000)
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

这几乎是瞬时的。

Answer 4

您可以使用 functools memoize 使其存储以前的值，这样就不必递归调用斐波那契函数。他们列出的例子实际上是斐波那契

Answer 5

不要使用 class；你没有从中得到任何东西
不要不必要地重新定义您的 class 每个循环
从 str 转换为 int 一次，而不是一遍又一遍
（如果赋值不需要）使用迭代求解，不递归

只有#1-3，你会得到：

def fibo(n):   # Using plain function, defined once outside loop
    if n < 2:
        return n
    return fib(n - 1) + fibo(n - 2)

while True:
    n = input()
    if n.lower() == 'end':
        break
    print(fibo(int(n)))  # Convert to int only once

如果您不需要使用递归解决方案，请不要；斐波那契生成实际上是一个非常糟糕的递归用法，因此将函数重新定义为：

def fibo(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, a + b
    return a

执行 O(n) 工作而不是 O(2**n) 工作。记忆可以加速递归解决方案（通过用 @functools.lru_cache(maxsize=None) 装饰 fibo），但是当迭代解决方案快得多并且首先不需要缓存时，这几乎不值得麻烦。

让fibo更快

Make fibo faster

python

fibonacci