<p>代码运行缓慢的原因是,您会一次又一次地访问(并重新计算)相同的组合。你可以用一种叫做记忆的技术来缩短重新计算的部分。你知道吗</p>
<p>记忆化很容易添加,但是让我们重新设计递归函数,以便调用函数进行累加,而不是函数本身。换句话说,不要传递总计,只返回此子路径的组合:</p>
<pre><code>def recAnswer(current, y, z, count):
if count == z and current == y:
return 1
count += 1
if count > z:
return 0
total = 0
for i in dict.get(current):
total += recAnswer(memo, i, y, z, count)
return total
</code></pre>
<p>这种变化不会改变计算本身;结果仍然是一样的。你知道吗</p>
<p>现在让我们把对同一个参数的所有重复调用都缩短。我们将字典<code>memo</code>传递给函数。这个dict的键是函数参数的元组。作为递归函数的第一步,检查计算是否已经完成。作为初始计算的最后一步,将解决方案添加到dict中:</p>
<pre><code>def recAnswer(memo, current, y, z, count):
# dict key is the tuple of arguments
key = (current, y, z, count)
# Have we been here before? If so, return memoized answer
if key in memo:
return memo[key]
if count == z and current == y:
return 1
count += 1
if count > z:
return 0
total = 0
for i in dict.get(current):
total += recAnswer(memo, i, y, z, count)
# Store answer for later use
memo[key] = total
return total
</code></pre>
<p>用一个空的dict开始计算,当然:</p>
<pre><code>total = recAnswer({}, x, y, z, 1)
</code></pre>
<p><strong>附录:</strong>现在我已经了解了<code>@decorator</code>的内容,我将用memoization来修饰函数,这样就不会改变原来的函数。好吧,我还要做一个修改,正如Janne在评论中提到的:我将把target cound和current count合并成一个变量,这个计数从目标值开始,倒计时到零,而不是倒计时到目标值。你知道吗</p>
<p>首先是memoization decorator,它将是一个包含修饰函数<code>func</code>和memoization字典的类。此类必须使用所需数量的参数实现函数<code>__call__</code>:</p>
<pre><code>class memoized(object):
"""Decorator function that adds the memoization"""
def __init__(self, func):
self.func = func
self.memo = {}
def __call__(self, current, target, count):
key = (current, target, count)
if key not in self.memo:
self.memo[key] = self.func(current, target, count)
return self.memo[key]
</code></pre>
<p>现在是在<code>def</code>初始化之前使用decorator的简化函数:</p>
<pre><code>@memoized
def recAnswer(current, target, count):
"""Unmemoized original function"""
if count == 0:
return int(current == target) # False: 0, True: 1
total = 0
for next in dict[current]:
total += recAnswer(next, target, count - 1)
return total
</code></pre>
<p><code>@memoized</code>修饰符通过<code>memoized.__call__</code>调用函数<code>recAnswer</code>,该函数处理记忆化。按如下方式调用递归函数:</p>
<pre><code>total = recAnswer(x, y, z - 1)
</code></pre>
<p>(这里的-1考虑到在原始代码中,计数从1开始。)</p>
<p>可能还有改进的余地。例如,可以使用splat语法设置<code>memoized</code>decorator类变量的参数数,以便可以将memoizer重新用于其他函数:</p>
<pre><code>def __call__(self, *args):
if args not in self.memo:
self.memo[args] = self.func(*args)
return self.memo[args]
</code></pre>
<p>所有这一切的结果是,如果你有一个问题,你重新评估同一组参数一次又一次,简单地跟踪以前计算的结果可以给你一个巨大的速度,而不必摆弄基本的实现。你知道吗</p>