python - Memoization: Making change with coins -

i working on classic making change coins problem python. implementation.

def memo(fn):     def helper(*args): # here, * indicate fn take arbitrary number of argumetns         d = {}         if args in d:             return d[args] # args tuple, immutable, hashable         else:             res = fn(*args) # here * expand tuple arguments             d[args] = res             return res     return helper  @memo def change(options, n):     if n < 0 or options ==():         return 0     elif n == 0:         return 1     else:         return change(options, n- options[0]) + change(options[1:], n) 

and turns out, memoized version slower original version! why? going wrong in implementation?

this without memoization:

in [172]: %timeit change((50, 25, 10, 5, 1), 100) 100 loops, best of 3: 7.12 ms per loop 

this memoization:

in [170]: %timeit change((50, 25, 10, 5, 1), 100) 10 loops, best of 3: 21.2 ms per loop 

in current code:

def memo(fn):     def helper(*args):         d = {} 

you create new "cache" dictionary d every time decorated function called. it's no wonder it's slower! minimal fix is:

def memo(fn):     d = {}     def helper(*args): 

but neater generally. use:

def memo(func):     def wrapper(*args):         if args not in wrapper.cache:             wrapper.cache[args] = func(*args)         return wrapper.cache[args]     wrapper.cache = {}     return wrapper 

this makes easier access decorated function's cache bug fixing etc.