Why memoization can speed up factorial in Python even if there is no repeated computing?

Question

Here's my code.

import timeit

fac_mem = {}

def fac(k):
  if k < 2: return 1
  if k not in fac_mem:
    fac_mem[k] = k*fac(k-1)
return fac_mem[k]

def fact(k):
  if k < 2: return 1
  return k*fact(k-1)

if __name__ == "__main__": 
  print timeit.timeit("fac(7)","from __main__ import fac")
  print timeit.timeit("fact(7)","from __main__ import fact")
  print timeit.timeit("fac(70)","from __main__ import fac")
  print timeit.timeit("fact(70)","from __main__ import fact")

Here's output

0.236774399224
0.897065011572
0.217623144304
14.1952226578

Well, before the program run, the dict is empty, why memoization still sped up factorial? I mean, the number of invocation is the same for these 2 version. Then I changed the code a bit, moved the dict into the function.

def fac(k):
  fac_mem = {}
  if k < 2: return 1
  if k not in fac_mem:
    fac_mem[k] = k*fac(k-1)
  return fac_mem[k]

The output changed

1.92900857225
0.910026658388
25.5475004875
14.2164999769

Why slower? Is that because the value generated inside the function is stored in stack temporarily? Variable outside is global, but what makes it so faster? Would somebody please be kind enough to clear it up for me? I'd be grateful.

Answer 1

When you run timeit.timeit without specifying an argument to the keyword number, it executes the code that you pass it 1000000 times. If you keep a global dictionary called fac_mem in the global scope for Python, it will save the results of the first execution in that dictionary.

Therefore your memoized factorial function will only be slow on the first execution where it actually has to do the computations. The rest of the 999999 times it will simply look up the answers in the dictionary and avoid doing computations.

If you keep the dictionary inside the function, it will be destroyed after every time Python leaves the scope within the function (since all references to the dictionary will be destroyed when the function returns). Thus the dictionary will not be able to save its answers and will still remain slow for future executions.

Check out the documentation for timeit.

Answer 2

1. The memoization you wrote hangs on the answer permanently. This means that asking for the same answer multiple times is really fast. Only the first call ever needs to compute anything.
2. The way timeit benchmarks a function is to run it hundreds of times and taking an average of all the calls. This helps it be more accurate

This means 1 normal speed call and 99 super fast ones, are averaged together. That makes the memoized function look faster.

If you want to measure actual speed you need to clear your memoization dictionary after each test invocation.