Blogged by Ujihisa. Standard methods of programming and thoughts including Clojure, Vim, LLVM, Haskell, Ruby and Mathematics written by a Japanese programmer. github/ujihisa

Friday, November 12, 2010

Memoized recursive fibonacci in Python

A slow literal implementation of fibonacci function in Python is like the below:

def fib(n):
    return n if n < 2 else fib(n-2) + fib(n-1)

This is slow but you can make it faster with memoize technique, reducing the order.

__fib_cache = {}
def fib(n):
    if n in __fib_cache:
        return __fib_cache[n]
    else:
        __fib_cache[n] = n if n < 2 else fib(n-2) + fib(n-1)
        return __fib_cache[n]

This is fast, but obviously dirty. Fortunately Python has decorator feature that gives you much better way of writing.

def memoize(f):
    cache = {}
    def decorated_function(*args):
        if args in cache:
            return cache[args]
        else:
            cache[args] = f(*args)
            return cache[args]
    return decorated_function

@memoize
def fib(n):
    return n if n < 2 else fib(n-2) + fib(n-1)

The @memoize decorator is not only for this fib() function but also for general purpose. I referred this page. This is succinct and clean.

But I felt that the definition of memoize(), particularly decorated_function(), was too long. If the else clause consists of single return statement, you may re-write decorated_function() in 1 line.

Takeshi Abe taught me how to make the two lines into one single line.

cache[args] = f(*args)
return cache[args]

is equivalent to

cache.update({args: f(*args)}) or cache[args]

So let here is the final version of fib with memoize:

def memoize(f):
    cache = {}
    return lambda *args: cache[args] if args in cache else cache.update({args: f(*args)}) or cache[args]

@memoize
def fib(n):
    return n if n < 2 else fib(n-2) + fib(n-1)

It's fast, short, succinct, and cool.

Footnote

This approach may be against the Python golden way.

1 comment:

  1. Maybe a couple years too late, but I've noticed that the memoed function still runs into problems with Python's maximum recursion length. So, you cannot immediately call

    fib(10000)

    However, if you call fib(500), fib(1000), ... in sufficiently small increments, you can work up to calling

    fib(10000) = 33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875L.

    Is there way to convince python (against its better judgement) to exceed the maximum recursion length, since we know that its memoized and it will be ok?

    ReplyDelete

Followers