def fibo(n):
a,b=1,1
for _ in range(n-1): a,b = b,a+b
return a
from math import log
def rec2(n) :
return fibo(int(log(n,2)+3))
print(rec2(12345678987654321)) # 225851433717
Decorator to wrap a function with a memoizing callable that saves up to the maxsize most recent calls. It can save time when an expensive or I/O bound function is periodically called with the same arguments
如果将maxsize设置为None,则缓存将不受限制地增长。你知道吗
from functools import lru_cache
@lru_cache(maxsize = None)
def rec(n):
if n < 1:
return 1
return rec(n // 4) + rec(n // 2)
print(rec(12345678987654321))
时间度量:
times = timeit.timeit(setup = 'from __main__ import rec',
stmt = 'print(rec(12345678987654321))', number = 1)
函数返回第X个斐波那契数,其中X=log(n)+3。因为获得第X个Fibonacci数有一个O(X)性能,我们提供log(n)。这将提供O(log(n))性能,与记忆版本类似,但使用更简单的操作。所以函数应该运行得更快:
对于n=12345678987654321,它的执行速度大约是原始rec()函数的记忆版本的5倍。你知道吗
您还可以通过在每次迭代中不进行两次递归调用来获得性能增益。这将需要返回两个值,以便n//4(下一次迭代)可以被带到调用函数。你知道吗
这比斐波那契方法慢,但仍然比记忆的原始方法快。你知道吗
1000次运行的测试结果(2.9 GHz Intel Core i9笔记本电脑):
编辑 如果要使Fibonacci方法更快(2x),可以使用此非迭代
fastFibo()
函数获取第n个Fibonacci数:这将允许您将函数编写为纯数学公式,没有迭代/递归,性能为O(1):
注意
fastFibo()
是一个近似值(好到70),所以这个rec4()
解在n=2^67(147573952589676412928)您可以使用
lru_cache
模块中的functools
。https://docs.python.org/3/library/functools.html
如文件所述
如果将maxsize设置为
None
,则缓存将不受限制地增长。你知道吗时间度量:
与
lru_cache
没有
lru_cache
您可以研究如何扩展递归关系,也可以简单地使用memoization:
上面的步骤在我的电脑上大约需要30毫秒,包括启动Python解释器所需的时间。你知道吗
通过不多次计算
rec()
相同值的n
(原始版本反复重复相同的计算,浪费了大量CPU周期),memoization加快了速度。你知道吗相关问题 更多 >
编程相关推荐