<h2>基本思路</h2>
<p>在计算机程序设计中,最基本和最常见的权衡是时间效率和空间效率之间的权衡。回忆录可能对时间有利,但对空间不利,这里就是这样。你的程序崩溃了,因为记忆字典保存了很多数据。马上你的递归关系意味着你永远不需要保存在<code>N - 3</code>点的数据,这样你就可以摆脱它了。这在一定程度上减轻了内存负担(但效果不大)。在</p>
<h2>代码问题/问题</h2>
<ol>
<li>不要记住你不需要的价值观(见上文)。在</li>
<li>Python对可变默认参数的处理意味着<code>memo</code>dict只创建一次。有关详细信息,请参见<a href="https://stackoverflow.com/questions/1132941/least-astonishment-and-the-mutable-default-argument">this SO post</a>。这也意味着字典在函数返回后(在内存中)处于空闲状态。。。不好的。一般不要使用可变的默认参数,除非有令人信服的理由。在</li>
<li><code>list</code>理解可以是<a href="https://stackoverflow.com/questions/22108488/are-list-comprehensions-and-functional-functions-faster-than-for-loops">a bit faster</a>,而不是显式for循环。更重要的是,在这种情况下,它们更具可读性。在</li>
<li>最后一个更像是一个时尚的东西。您正在将<code>1</code>或<code>2</code>添加到递归调用返回的项的尾部。通常,这些元素会添加到头部。在</li>
</ol>
<h2>解决方案</h2>
<h3>相同的算法,但内存和时间效率更高</h3>
<pre><code>def stepsdyn_new(N, memo):
try:
return memo[N]
except KeyError:
l1 = [(1,) + items for items in stepsdyn_new(N - 1, memo)]
l2 = [(2,) + items for items in stepsdyn_new(N - 2, memo)]
memo.pop(N - 2)
memo[N] = l1 + l2
return memo[N]
</code></pre>
<p><strong>注意</strong>:我将基本情况作为参数传入,但是如果需要,您可以添加原始的<code>if</code>/<code>else</code>。在</p>
<h3>返回字符串</h3>
^{pr2}$
<p>这将返回一个字符串列表(例如['111','12','21']),而不是元组列表。因为python字符串中的每个字符只使用1个字节(而不是列表/元组中每个元素的8个字节),因此可以节省大量内存。结果可以用以下代码转换回元组列表(尽管这会导致额外的速度/内存损失):</p>
<pre><code>[tuple(map(int, tuple(x))) for x in stepsdyn_str(N, {0: [''], 1: ['1']})]
</code></pre>
<h2>效率</h2>
<p><strong>注意</strong>:函数<code>steps</code>是一个非记忆化的解决方案(为了完整起见,下面包含了这个函数)。在</p>
<h3>速度</h3>
<pre><code>| | | |
| | N = 20 | N = 33 |
| | | |
| steps | 47 ms ± 7.34 ms per loop | 41.2 s ± 1.6 s per loop |
| | | |
| stepsdyn | 10.1 ms ± 1.23 ms per loop | 9.46 s ± 691 ms per loop |
| | | |
| stepsdyn_new | 6.74 ms ± 1.03 ms per loop | 7.41 s ± 396 ms per loop |
| | | |
| stepsdyn_str | 3.28 ms ± 68.8 µs per loop | 3.67 s ± 121 ms per loop |
| | | |
</code></pre>
<p>使用以下方法获得:</p>
<pre><code>%timeit steps(N)
%timeit stepsdyn(N, memo={})
%timeit stepsdyn_new(N, {0: [()], 1: [(1,)]})
%timeit stepsdyn_str(N, {0: [''], 1: ['1']})
</code></pre>
<h3>内存</h3>
<p>在计算<code>N=33</code>的函数时,这些估计值特定于我的16GB内存MBP:</p>
<ul>
<li>^{cd8>最大内存</li>
<li><code>stepsdyn</code>:最大内存22.0%</li>
<li><code>stepsdyn_new</code>:最大内存15.7%</li>
<li><code>stepsdyn_str</code>:最大内存3.6%</li>
</ul>
<h2>非记忆解决方案</h2>
<pre><code>def steps(N):
if N == 0:
return [()]
elif N == 1:
return [(1,)]
else:
l1 = [(1,) + items for items in steps(N - 1)]
l2 = [(2,) + items for items in steps(N - 2)]
return l1 + l2
</code></pre>