Testing out various versions of nested & unnested of fibonacci

test_fib

fibonacci_memo
0.268512010574

fibonacci_memo_nested
11.6659519672

Diff: 11.3974399567
Ratio:  43.4466672172
---------------------------------------- 

fibonacci_gen
6.90226602554

fibonacci_gen_nested
6.89019012451

Diff: -0.0120759010315
Ratio:  0.998250443987
---------------------------------------- 

fibonacci_rec_acc
3.93663787842

fibonacci_rec_acc_nested
4.59940218925

Diff: 0.662764310837
Ratio:  1.16835795705
---------------------------------------- 

test_fib.py

#!/usr/bin/env python


memo = {0: 0, 1: 1}


# Contract: [int > 0] -> [int > 0]
def fibonacci_memo(n):
    """ Return the `x`th number in the fibonacci series. """
    if not n in memo:
        memo[n] = fibonacci_memo(n - 1) + fibonacci_memo(n - 2)
    return memo[n]

#-------------#


# Contract: [int > 0] -> [int > 0]
def fibonacci_memo_nested(n):
    memo = {0: 0, 1: 1}

    def fib(n):
        """ Return the `x`th number in the fibonacci series. """
        if not n in memo:
            memo[n] = fib(n - 1) + fib(n - 2)
        return memo[n]

    return fib(n)

#--------------------------#


def fib_num_rec_acc_in(n, x0, x1):
    if n == 0:
        return x0
    return fib_num_rec_acc_in(n - 1, x1, x0 + x1)


# Contract: [int > 0] -> [int > 0]
def fibonacci_rec_acc(n):
    """ Return the `x`th number in the fibonacci series. """
    return fib_num_rec_acc_in(n, 0, 1)

#-------------#


def fibonacci_rec_acc_nested(n):
    def fib_num_rec_acc_in(n, x0, x1):
        if n == 0:
            return x0
        return fib_num_rec_acc_in(n - 1, x1, x0 + x1)
    return fib_num_rec_acc_in(n, 0, 1)

#--------------------------#


def fib_gen_in():
    a, b = 0, 1
    while 1:
        yield a
        a, b = b, a + b


# Contract: [int > 0] -> [int > 0]
def fibonacci_gen(n):
    """ Return the `x`th number in the fibonacci series. """
    g = fib_gen_in()
    count = 0

    while count < n:
        count += 1
        g.next()

    return g.next()

#-------------#


def fibonacci_gen_nested(n):
    """ Return the `x`th number in the fibonacci series. """
    def fib_gen_in():
        a, b = 0, 1
        while 1:
            yield a
            a, b = b, a + b

    g = fib_gen_in()
    count = 0

    while count < n:
        count += 1
        g.next()

    return g.next()

#--------------------------#

import timeit
stmt = "assert fib(20) == 6765"
setup = "from __main__ import {0} as fib"


def time_test(f):
    print "{0}".format(f)
    time = timeit.timeit(stmt, setup=setup.format(f))
    print time
    print
    return time


for x in ['fibonacci_memo', 'fibonacci_gen', 'fibonacci_rec_acc']:
    unnested_time = time_test(x)
    nested_time = time_test(x + "_nested")
    print "Diff:", (nested_time - unnested_time)
    print "Ratio: ", (nested_time / unnested_time)
    print '-' * 40, '\n'