是什么导致这些方法调用时间的巨大差异？

Question

从这里使用Memoized装饰器的接受答案(带有doctests): 可以做些什么来加速这个memoization装饰器？

和以下代码(fib.py):

class O(object):

  def nfib(self,n): # non-memoized fib fn

     if n in (0, 1):
        return n
     return self.nfib(n-1) + self.nfib(n-2)

  @Memoized
  def fib(self,n): # memoized fib fn

     if n in (0, 1):
        return n
     return self.fib(n-1) + self.fib(n-2)


if __name__ == '__main__':
  import time
  o = O()

  stime = time.time()
  print "starting non-memoized"
  for i in range(10):
    print o.nfib(32)
  print "finished non-memoized - elapsed secs =", time.time() - stime

  stime = time.time()
  print "starting memoized"
  for i in range(10):
    print o.fib(32)
  print "finished memoized - elapsed secs =", time.time() - stime

  stime = time.time()
  print "starting memoized with reset"
  for i in range(10):
    Memoized.reset()
    print o.fib(32)
  print "finished memoized with reset - elapsed secs =", time.time() - stime

我得到以下输出:

C:\TEMP>python fib.py
starting non-memoized
2178309
2178309
2178309
2178309
2178309
2178309
2178309
2178309
2178309
2178309
finished non-memoized - elapsed secs = 16.4189999104
starting memoized
2178309
2178309
2178309
2178309
2178309
2178309
2178309
2178309
2178309
2178309
finished memoized - elapsed secs = 0.00100016593933
starting memoized with reset
2178309
2178309
2178309
2178309
2178309
2178309
2178309
2178309
2178309
2178309
finished memoized with reset - elapsed secs = 0.00299978256226

C:\TEMP>

我希望第三个循环可以和第一个循环一样长,因为它每次都通过循环重置它的缓存.将调试语句插入到fib方法中会显示它没有被缓存,并且确实在第三个循环中计算结果,但它比第一个循环大得多.为什么？？？

我希望我忽略了一些令人尴尬的事情,但我的好奇心目前超过了我的骄傲.(顺便说一句,如果重要,我在Windows 7专业机器上使用64位python 2.7)

谢谢.

Answer 1

天真斐波那契函数的调用树不是线性或三角形,而是多维金字塔形.通过memoizing甚至一个单一的时间你修剪广大金额从树上电话,把金字塔变成一个极具线性结构.