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

发布时间：2020-12-17 00:17:52 所属栏目：Python 来源：网络整理

导读：div class="markdown-here-wrapper" data-md-url="https://i.cnblogs.com/EditPosts.aspx?opt=1"gt; h1 id="-" style="margin: 20px 0px 10px; padding: 0px; font-weight: bold; color: black; font-size: 24px; border-bottom: 2px solid #aaaaaa;"一.递归

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

<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

<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">前面输入的数较小，所以算的还算很快，但输入到35、36来测试时已经要花上好几秒来计算了，而且36比35计算时间多了两秒多，可想而知数据再增大后消耗的时间增加的是越来越大的，因为这个递归函数的复杂性是O(2**n)

<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">我们想一下这个函数递归的原理，流程，发现一个问题，计算fibonacci(35)的时候，是计算fibonacci(34)+fibonacci(33)的和，计算fibonacci(34)时，是计算的fibonacci(33)+fibonacci(32)的和，问题出现了，fibonacci(33)需要计算两次，那不是重复了嘛，我们继续递归向下拆分发现，几乎所有的递归函数拆分为两个函数的和时都会有重复计算，就想下面这个图：

<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">以fibonacci(5)举例，这个图里面有一大部分的数字是重复的，也就是说执行了很多的重复的函数，这使我们产生了一个想法，既然重复执行了，那我让它直接返回之前执行时的返回值不就行了，至于之前执行时的返回值，给他存起来不就好了吗，这就用到了我们下面要说的缓存思想

<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-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

<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">当使用了缓存的方式后，发现计算所用的时间已经接近0，我们把数再改大一点

))
t2 = time.time()
print(t2 - t1)  
t1 = time.time()
print(fibonacci())
t2 = time.time()
print(t2 - t1)

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!

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

（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!