CODEWITHSUNDEEP
pythondecorator
Chen A.
Chen A.

Reputation: 11280

Memoization decorator runs slower than original function

I'm doing memoized decorator exercise with fibonacci function. The memoized function should be much faster when the input gets large, because it returns the result from a dictionary instead of computing the result again.

I'm using timeit.timeit() to measure the execution time of the function with memoized on vs off. The result I get are exactly the opposite of what I expect. The execution without the decorator runs much faster.

# memorized decorator for fibonacci series
def mem_fib(f):
    def wrapper(n):
        wrapper.d = {}  # create the attr member of THIS wrapper
        if n in wrapper.d:
            return wrapper.d[n]
        wrapper.d[n] = f(n)  # save f() return in a dict
        return wrapper.d[n]
    return wrapper

@mem_fib
def fibonacci(n):
    assert n >= 0
    if n < 2:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

I'm running commands on PyCharm python's console.

@with decorator

>>> print(timeit.timeit('decorators.fibonacci(7)', setup='import decorators'))
19.6940833939
>>> print(timeit.timeit('decorators.fibonacci(10)', setup='import decorators'))
85.7157191166

without the decorator

>>> print(timeit.timeit('decorators.fibonacci(7)', setup='import decorators'))
5.10131571594
>>> print(timeit.timeit('decorators.fibonacci(10)', setup='import decorators'))
21.9784012801

I ran the timeit multiple times, I just put one output to sum it up. What am I missing?

Thanks

Update: Thanks to Daniel's answer, I found my mistake. I moved the dictionary creation outside of wrapper, and the results were much better.

>>> print(timeit.timeit('decorators.fibonacci(10)', setup='import decorators'))
0.248986574759

Upvotes: 0

Views: 401

Answers (1)

Daniel Roseman
Daniel Roseman

Reputation: 599610

You create a new dictionary every time the function is called, because your wrapper function always does wrapper.d = {}. Therefore the cache will never be populated, and your code has the additional overhead of creating the dictionary each time.

That line should go outside that function, before you return it from mem_fib.

Upvotes: 4

Related Questions