概述
<div class="markdown-here-wrapper" data-md-url="https://i.cnblogs.com/EditPosts.aspx?opt=1">
<h1 id="-" style="margin: 20px 0px 10px; padding: 0px; font-weight: bold; color: black; font-size: 24px; border-bottom: 2px solid #aaaaaa;">一.递归函数的弊端
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">递归函数虽然编写时用很少的代码完成了庞大的功能,但是它的弊端确实非常明显的,那就是时间与空间的消耗。
time
<span class="hljs-comment" style="color: #7285b7;">#@lru_cache(20)
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def <span class="hljs-title" style="color: #7285b7;">fibonacci<span class="hljs-params" style="color: #ffc58f;">(n):
<span class="hljs-keyword" style="color: #ebbbff;">if n < <span class="hljs-number" style="color: #ffc58f;">2:
<span class="hljs-keyword" style="color: #ebbbff;">return <span class="hljs-number" style="color: #ffc58f;">1
<span class="hljs-keyword" style="color: #ebbbff;">else:
<span class="hljs-keyword" style="color: #ebbbff;">return fibonacci(n - <span class="hljs-number" style="color: #ffc58f;">1) + fibonacci(n - <span class="hljs-number" style="color: #ffc58f;">2)
t1 = time.time()
print(fibonacci(<span class="hljs-number" style="color: #ffc58f;">35))
t2 = time.time()
print(t2 - t1) <span class="hljs-comment" style="color: #7285b7;"># 4.007285118103027
t1 = time.time()
print(fibonacci(<span class="hljs-number" style="color: #ffc58f;">36))
t2 = time.time()
print(t2 - t1) <span class="hljs-comment" style="color: #7285b7;"># 6.479698419570923
<span class="hljs-comment" style="color: #7285b7;">#@lru_cache(20)
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def <span class="hljs-title" style="color: #7285b7;">fibonacci<span class="hljs-params" style="color: #ffc58f;">(n):
<span class="hljs-keyword" style="color: #ebbbff;">if n < <span class="hljs-number" style="color: #ffc58f;">2:
<span class="hljs-keyword" style="color: #ebbbff;">return <span class="hljs-number" style="color: #ffc58f;">1
<span class="hljs-keyword" style="color: #ebbbff;">else:
<span class="hljs-keyword" style="color: #ebbbff;">return fibonacci(n - <span class="hljs-number" style="color: #ffc58f;">1) + fibonacci(n - <span class="hljs-number" style="color: #ffc58f;">2)
t1 = time.time()
print(fibonacci(<span class="hljs-number" style="color: #ffc58f;">35))
t2 = time.time()
print(t2 - t1) <span class="hljs-comment" style="color: #7285b7;"># 4.007285118103027
t1 = time.time()
print(fibonacci(<span class="hljs-number" style="color: #ffc58f;">36))
t2 = time.time()
print(t2 - t1) <span class="hljs-comment" style="color: #7285b7;"># 6.479698419570923
<span class="hljs-comment" style="color: #7285b7;">#@lru_cache(20)
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def <span class="hljs-title" style="color: #7285b7;">fibonacci<span class="hljs-params" style="color: #ffc58f;">(n):
<span class="hljs-keyword" style="color: #ebbbff;">if n < <span class="hljs-number" style="color: #ffc58f;">2:
<span class="hljs-keyword" style="color: #ebbbff;">return <span class="hljs-number" style="color: #ffc58f;">1
<span class="hljs-keyword" style="color: #ebbbff;">else:
<span class="hljs-keyword" style="color: #ebbbff;">return fibonacci(n - <span class="hljs-number" style="color: #ffc58f;">1) + fibonacci(n - <span class="hljs-number" style="color: #ffc58f;">2)
t1 = time.time()
print(fibonacci(<span class="hljs-number" style="color: #ffc58f;">35))
t2 = time.time()
print(t2 - t1) <span class="hljs-comment" style="color: #7285b7;"># 4.007285118103027
t1 = time.time()
print(fibonacci(<span class="hljs-number" style="color: #ffc58f;">36))
t2 = time.time()
print(t2 - t1) <span class="hljs-comment" style="color: #7285b7;"># 6.479698419570923
<img src="https://www.jb51.cc/res/2019/02-05/23/7c0bf81e6a1333ecc48b26f9c9151fa7.png" alt="" width="478" height="257">
time
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def <span class="hljs-title" style="color: #7285b7;">cache_decorator<span class="hljs-params" style="color: #ffc58f;">(func):
cache_dict = {}<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;">decorator</span><span class="hljs-params" style="color: #ffc58f;">(arg)</span>:</span> <span class="hljs-keyword" style="color: #ebbbff;">try</span>: <span class="hljs-keyword" style="color: #ebbbff;">return</span> cache_dict[arg] <span class="hljs-keyword" style="color: #ebbbff;">except</span> KeyError: <span class="hljs-keyword" style="color: #ebbbff;">return</span> cache_dict.setdefault(arg,func(arg)) <span class="hljs-keyword" style="color: #ebbbff;">return</span> decorator
<span class="hljs-decorator">@cache_decorator
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def <span class="hljs-title" style="color: #7285b7;">fibonacci<span class="hljs-params" style="color: #ffc58f;">(n):
<span class="hljs-keyword" style="color: #ebbbff;">if n < <span class="hljs-number" style="color: #ffc58f;">2:
<span class="hljs-keyword" style="color: #ebbbff;">return <span class="hljs-number" style="color: #ffc58f;">1
<span class="hljs-keyword" style="color: #ebbbff;">else:
<span class="hljs-keyword" style="color: #ebbbff;">return fibonacci(n - <span class="hljs-number" style="color: #ffc58f;">1) + fibonacci(n - <span class="hljs-number" style="color: #ffc58f;">2)
t1 = time.time()
print(fibonacci(<span class="hljs-number" style="color: #ffc58f;">35))
t2 = time.time()
print(t2 - t1) <span class="hljs-comment" style="color: #7285b7;"># 0
t1 = time.time()
print(fibonacci(<span class="hljs-number" style="color: #ffc58f;">36))
t2 = time.time()
print(t2 - t1) <span class="hljs-comment" style="color: #7285b7;"># 0
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;">decorator</span><span class="hljs-params" style="color: #ffc58f;">(arg)</span>:</span>
<span class="hljs-keyword" style="color: #ebbbff;">try</span>:
<span class="hljs-keyword" style="color: #ebbbff;">return</span> cache_dict[arg]
<span class="hljs-keyword" style="color: #ebbbff;">except</span> KeyError:
<span class="hljs-keyword" style="color: #ebbbff;">return</span> cache_dict.setdefault(arg,func(arg))
<span class="hljs-keyword" style="color: #ebbbff;">return</span> decorator
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def <span class="hljs-title" style="color: #7285b7;">cache_decorator<span class="hljs-params" style="color: #ffc58f;">(func):
cache_dict = {}
<span class="hljs-decorator">@cache_decorator
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def <span class="hljs-title" style="color: #7285b7;">fibonacci<span class="hljs-params" style="color: #ffc58f;">(n):
<span class="hljs-keyword" style="color: #ebbbff;">if n < <span class="hljs-number" style="color: #ffc58f;">2:
<span class="hljs-keyword" style="color: #ebbbff;">return <span class="hljs-number" style="color: #ffc58f;">1
<span class="hljs-keyword" style="color: #ebbbff;">else:
<span class="hljs-keyword" style="color: #ebbbff;">return fibonacci(n - <span class="hljs-number" style="color: #ffc58f;">1) + fibonacci(n - <span class="hljs-number" style="color: #ffc58f;">2)
t1 = time.time()
print(fibonacci(<span class="hljs-number" style="color: #ffc58f;">35))
t2 = time.time()
print(t2 - t1) <span class="hljs-comment" style="color: #7285b7;"># 0
t1 = time.time()
print(fibonacci(<span class="hljs-number" style="color: #ffc58f;">36))
t2 = time.time()
print(t2 - t1) <span class="hljs-comment" style="color: #7285b7;"># 0
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def <span class="hljs-title" style="color: #7285b7;">cache_decorator<span class="hljs-params" style="color: #ffc58f;">(func):
cache_dict = {}
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;">decorator</span><span class="hljs-params" style="color: #ffc58f;">(arg)</span>:</span>
<span class="hljs-keyword" style="color: #ebbbff;">try</span>:
<span class="hljs-keyword" style="color: #ebbbff;">return</span> cache_dict[arg]
<span class="hljs-keyword" style="color: #ebbbff;">except</span> KeyError:
<span class="hljs-keyword" style="color: #ebbbff;">return</span> cache_dict.setdefault(arg,func(arg))
<span class="hljs-keyword" style="color: #ebbbff;">return</span> decorator
<span class="hljs-decorator">@cache_decorator
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def <span class="hljs-title" style="color: #7285b7;">fibonacci<span class="hljs-params" style="color: #ffc58f;">(n):
<span class="hljs-keyword" style="color: #ebbbff;">if n < <span class="hljs-number" style="color: #ffc58f;">2:
<span class="hljs-keyword" style="color: #ebbbff;">return <span class="hljs-number" style="color: #ffc58f;">1
<span class="hljs-keyword" style="color: #ebbbff;">else:
<span class="hljs-keyword" style="color: #ebbbff;">return fibonacci(n - <span class="hljs-number" style="color: #ffc58f;">1) + fibonacci(n - <span class="hljs-number" style="color: #ffc58f;">2)
t1 = time.time()
print(fibonacci(<span class="hljs-number" style="color: #ffc58f;">35))
t2 = time.time()
print(t2 - t1) <span class="hljs-comment" style="color: #7285b7;"># 0
t1 = time.time()
print(fibonacci(<span class="hljs-number" style="color: #ffc58f;">36))
t2 = time.time()
print(t2 - t1) <span class="hljs-comment" style="color: #7285b7;"># 0
))
t2 = time.time()
print(t2 - t1)
t1 = time.time()
print(fibonacci(301))
t2 = time.time()
print(t2 - t1)
301)可直接从缓存中拿fibonacci(300)和fibonacci(299),我们用图来更清晰的解释
函数,比如有多个参数的函数,但是python标准库为我们提供了一个非常方便的装饰器来进行缓存
functools模块中的lru_cache(maxsize,typed)
内容的淘汰,
调用是否分别缓存,这个参数的意思是如果设置为True,那么fibonacci(5)和fibonacci(5.0)将分别缓存,不存为一个。
自定义的装饰器替换为 lru_cache(None,False)即可。
如果您也喜欢它,动动您的小指点个赞吧