What is causing this massive discrepancy on the timing of these method calls?

Using the accepted answer (with the doctests) for the Memoized decorator from here: What can be done to speed up this memoization decorator?

and the following code (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 memoi开发者_高级运维zed with reset - elapsed secs =", time.time() - stime

I get the following output:

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>

I would have expected the third loop to take as long as the first loop, since it's resetting it's cache each time through the loop. Inserting debug statments into the fib method shows that it's not cached, and is indeed calculating the results in the third loop, but it's massively faster than the first loop. Why???

I expect I've overlooked something embarrassingly obvious, but my curiosity is currently outweighing my pride. (b.t.w. I'm using 64bit python 2.7 on a Windows 7 pro machine if it matters)

Thanks.

The call tree for a naive fibonacci function isn't linear or triangular, it's multidimensional pyramidal. By memoizing even a single time you trim vast amounts of calls from the tree, turning the pyramid into a mostly linear structure.

The third loop is resetting after calculating each final result - however, it still benefits from memoization of the recursive calls.

time.time() should not be used to time code, especially on windows! Use timeit module. Here's an old intoduction. One big issue is that computers are constantly doing hundreds of things. If one part happens to run while Outlook is fetching email it may take slightly longer than the other function after outlook has finished. Repeating the tasks and taking the minimum tends to be better. This, and many other things, are handled automatically by the timeit module.

Regarding windows, this part is pretty relevant:

On Windows, time.clock() has microsecond granularity but time.time()‘s granularity is 1/60th of a second