斐波那契数列/数动态规划
我正在努力提高我的编程逻辑技能，我正在看一个关于如何接近斐波那契数的videos。
在查看了6:34上的伪代码后，我编写了以下代码：
In [14]: def my_fib(x, memo=dict()):
...: if memo.get(x):
...: return memo[x]
...: if x == 1 or x == 2:
...: result = 1
...: else:
...: result = my_fib(x - 1, memo) + my_fib(x -2, memo)
...: memo[x] = result
...: return result然而，当我看完这个视频时，我发现它和我的略有不同。
CS Dojo代码：
In [68]: def fib_dyn_2(x, memo):
...: if memo[x] is not None:
...: return memo[x]
...: if x == 1 or x == 2:
...: result = 1
...: else:
...: result = fib_dyn_2(x-1, memo) + fib_dyn_2(x-2, memo)
...: memo[x] = result
...: return result
...:
...: def fib_memo(x):
...: memo = [None] * (x + 1)
...: return fib_dyn_2(x, memo)有“细微”的区别，我使用字典缓存，他使用列表。
让我着迷的是，我的代码看起来要快一点。当获得序列X >= 100中的数字时，以及当运行相同的数字时，该序列不止一次。
即我的代码：
In [4]: %time my_fib(100)
CPU times: user 70 µs, sys: 44 µs, total: 114 µs
Wall time: 92 µs
Out[4]: 354224848179261915075LCS Dojo代码：
In [5]: %time fib_memo(100)
CPU times: user 99 µs, sys: 128 µs, total: 227 µs
Wall time: 187 µs
Out[5]: 354224848179261915075L问题是，哪一个是“更好”的答案，还是更受欢迎的答案？
回答 4
Stack Overflow用户
发布于 2019-06-15 19:05:30
虽然记忆版本的斐波那契数计算比朴素的递归方法要好得多，但我鼓励您检查基于斐波那契数的Matrix Form的解决方案：
Stack Overflow用户
发布于 2019-06-16 07:44:12
直观地说，基于列表的记忆应该比基于字典的略快一些。我发现调用的算法和顺序对结果有很大的影响，所以公平的比较需要一些注意(例如，使用预分配与追加)
我做了几个对比测试，似乎证实了这一点。您还可以根据算法中使用的操作/逻辑类型获得显着的性能差异。
以下是测试结果( 100次重复获取第900个斐波那契数)：
my_fib(N) 0.0578 Original
fibo(N) 0.0089 Iterative algorithm
simpleFibo(N) 0.0248 Single recursion algorithm
dynaFibo(N) 0.0463 Double recursion with dictionary based memoization
dynaFibo2(N) 0.0440 Double recursion with list based memoization
binFibo(N) 0.0012 Iterative exponential algorithm
(this one responds in O(log(N)) time)下面是函数的实现：
def my_fib(x, memo=dict()):
if memo.get(x):
return memo[x]
if x == 1 or x == 2:
result = 1
else:
result = my_fib(x - 1, memo) + my_fib(x -2, memo)
memo[x] = result
return result
def fibo(N):
a = b = 1
for _ in range(2,N): a,b = b,a+b
return b
def simpleFibo(N,a=0,b=1):
if N < 3: return a+b
return simpleFibo(N-1,b,a+b)
def dynaFibo(N,memo={1:1,2:1}):
if N not in memo:
memo[N] = dynaFibo(N-1,memo) + dynaFibo(N-2,memo)
return memo[N]
def dynaFibo2(N,memo=None):
if not memo: memo = [0,1,1]+[0]*N
if not memo[N]: memo[N] = dynaFibo2(N-1,memo) + dynaFibo2(N-2,memo)
return memo[N]log EDIT添加了一个指数算法，响应时间为O((N))
def binFibo(N):
a,b = 0,1
f0,f1 = 1,1
r,s = (1,1) if N&1 else (0,1)
N //=2
while N > 0:
a,b = f0*a+f1*b, f0*b+f1*(a+b)
f0,f1 = b-a,a
if N&1: r,s = f0*r+f1*s, f0*s+f1*(r+s)
N //= 2
return r以及测试过程
from timeit import timeit
count = 100
N = 990
t= timeit(lambda:my_fib(N,dict()), number=count) # providing dict() to avoid reuse between repetitions
print("my_fib(N)",t)
t= timeit(lambda:fibo(N), number=count)
print("fibo(N)",t)
t= timeit(lambda:simpleFibo(N), number=count)
print("simpleFibo(N)",t)
t= timeit(lambda:dynaFibo(N,{1:1,2:1}), number=count) # providing dict() to avoid reuse between repetitions
print("dynaFibo(N)",t)
t= timeit(lambda:dynaFibo2(N), number=count)
print("dynaFibo2(N)",t)
t= timeit(lambda:binFibo(N), number=count)
print("binFibo(N)",t)顺便说一句，我假设你的目标是探索动态编程。否则，对fibonacci函数使用双重递归肯定是最糟糕的方法。
Stack Overflow用户
发布于 2019-06-15 19:02:13
我只是尝试验证在dict和list版本之间是否存在显著的性能差异。看起来这两种方法之间只有很小的区别。顺便说一句。注意，我还测量了cache-list的创建。如果我比较"unix“time命令打印的时间，我会发现根本没有区别，但当然这也测量了操作系统加载python解释器所需的时间，因此不太可靠。
from datetime import datetime
def fib_cached(n, cache=None):
if n <= 2:
return 1
if cache[n] is None:
fib_n= fib_cached(n-1, cache) + fib_cached(n-2, cache)
cache[n]= fib_n
else:
fib_n= cache[n]
return fib_n
n= 950
before= datetime.now()
print(fib_cached(n, cache=[None]*(n+1)))
print(datetime.now() - before)https://stackoverflow.com/questions/56609325
复制相似问题
腾讯云开发者
