什么原因导致这些方法调用的时间差异很大？

使用接受的答案（与文档测试）从这里Memoized装饰：What can be done to speed up this memoization decorator?什么原因导致这些方法调用的时间差异很大？

和下面的代码（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方法中显示它没有被缓存，并且确实在第三个循环中计算结果，但它比第一个循环快得多。为什么？？？

我希望我忽略了一些令人尴尬明显的事情，但是我的好奇心现在超过了我的自尊心。（b.t.w.我使用的是Windows 7专业版的64位Python 2.7，如果它很重要）

谢谢。

来源

2011-02-08 Gerrat

我在之前的评论中解释过这一点：高速缓存产生O（n^2）函数O（n）。 – 2011-02-08 01:00:10

@Glenn：...是的，你做了（你不清楚）......我只是没有“明白”。插入调试语句后，将每个（未记忆）的调用打印出来并以2 Gig文件结尾，并且每次看到所有的调用参数 - 我现在“明白了”！再次感谢装饰者。 – Gerrat 2011-02-08 01:14:12

天真斐波那契函数的调用树不是线性或三角形的，它是多维金字塔。通过记忆甚至一次，您修剪树木的大量呼叫，将金字塔变成大多数线性结构。

来源

2011-02-08 00:58:39

第三个循环在计算每个最终结果后重置 - 但是，它仍然受益于递归调用的记忆。

来源

2011-02-08 00:58:04

time.time（）不应该用于时间码，特别是在Windows上！使用timeit module。这是一个旧的intoduction。一个大问题是电脑不断地做数百件事情。如果在Outlook取电子邮件时某个部分碰巧运行，则Outlook在完成Outlook后可能会比其他功能稍长一些。重复这些任务，并采取最低限度往往会更好。这和其他许多事情都由timeit模块自动处理。

关于窗口，这部分非常重要：

在Windows上，time.clock（）具有微秒粒度但了time.time（）的粒度的第二

1/60

来源

2011-02-08 00:58:21 chmullig

1/60秒的测试是非常准确的。 – Falmarri 2011-02-08 01:01:35

什么原因导致这些方法调用的时间差异很大？

回答

相关问题