使用缓存方式优化递归函数与lru

概述

<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;">一.递归函数的弊端
递归函数虽然编写时用很少的代码完成了庞大的功能，但是它的弊端确实非常明显的，那就是时间与空间的消耗。

 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

#@lru_cache(20)
def fibonacci(n):
if n < 2:
return 1
else:
return fibonacci(n - 1) + fibonacci(n - 2)

t1 = time.time() print(fibonacci(35)) t2 = time.time() print(t2 - t1) # 4.007285118103027 t1 = time.time() print(fibonacci(36)) t2 = time.time() print(t2 - t1) # 6.479698419570923

 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;"&gt;<span class="hljs-keyword" style="color: #ebbbff;"&gt;def</span> <span class="hljs-title" style="color: #7285b7;"&gt;decorator</span><span class="hljs-params" style="color: #ffc58f;"&gt;(arg)</span>:</span>
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;try</span>:
        <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> cache_dict[arg]
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;except</span> KeyError:
        <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> cache_dict.setdefault(arg,func(arg))
<span class="hljs-keyword" style="color: #ebbbff;"&gt;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;"&gt;<span class="hljs-keyword" style="color: #ebbbff;"&gt;def</span> <span class="hljs-title" style="color: #7285b7;"&gt;decorator</span><span class="hljs-params" style="color: #ffc58f;"&gt;(arg)</span>:</span>
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;try</span>:
        <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> cache_dict[arg]
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;except</span> KeyError:
        <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> cache_dict.setdefault(arg,func(arg))
<span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> decorator

def cache_decorator(func):
cache_dict = {}

@cache_decorator
def fibonacci(n):
if n < 2:
return 1
else:
return fibonacci(n - 1) + fibonacci(n - 2)

t1 = time.time() print(fibonacci(35)) t2 = time.time() print(t2 - t1) # 0 t1 = time.time() print(fibonacci(36)) t2 = time.time() print(t2 - t1) # 0

<span class="hljs-function" style="color: #bbdaff;"&gt;<span class="hljs-keyword" style="color: #ebbbff;"&gt;def</span> <span class="hljs-title" style="color: #7285b7;"&gt;decorator</span><span class="hljs-params" style="color: #ffc58f;"&gt;(arg)</span>:</span>
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;try</span>:
        <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> cache_dict[arg]
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;except</span> KeyError:
        <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> cache_dict.setdefault(arg,func(arg))
<span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> decorator

t1 = time.time() print(fibonacci(35)) t2 = time.time() print(t2 - t1) # 0 t1 = time.time() print(fibonacci(36)) t2 = time.time() print(t2 - t1) # 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)即可。

如果您也喜欢它,动动您的小指点个赞吧

使用缓存方式优化递归函数与lru_cache

概述

分类汇总

您的鼓励是对我最大的支持