Implementation

Python decorators are generic and very powerful. You can find many examples of how they can be used at the decorator library of python.org [j.mp/pydeclib]. In this section, we will see how we can implement a memoization decorator [j.mp/memoi]. All recursive functions can benefit from memoization, so let's pick the popular Fibonacci sequence example. Implementing the recursive algorithm of Fibonacci is straight forward, but it has major performance issues, even for small values. First, let's see the naive implementation (file fibonacci_naive.py).

def fibonacci(n): assert(n >= 0), 'n must be >= 0' return n if n in (0, 1) else fibonacci(n-1) + fibonacci(n-2) if __name__ == '__main__': from timeit import Timer t = Timer('fibonacci(8)', ...

Get Python: Master the Art of Design Patterns now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.