Last active
June 7, 2017 05:49
-
-
Save pstoll/e155d4e3f6d584cdce07119a0c417e48 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# /usr/bin/env python | |
# Author: Perry A. Stoll <perry at pstoll dot com> | |
# Date: June 2017 | |
# Copyright Perry Stoll | |
# | |
# Generate the first N fibonnaci numbers. | |
# | |
# Note this is quite different from generating the Nth fibonnaci | |
# numbers in terms of storage and laying out the computation | |
# | |
# Fun with fibonnaci | |
# | |
# or... | |
# | |
# why generators are the right thing to create possibly large | |
# sequences in python | |
# | |
# and why I'll never actually use non-tail recursive functions in | |
# production code. or ever actually, since i'm not going to use a | |
# functional language, much to my detriment, i'm sure. | |
import sys, time | |
from contextlib import contextmanager | |
# thanks SO https://stackoverflow.com/questions/5478351/python-time-measure-function | |
@contextmanager | |
def timeit_context(name): | |
startTime = time.time() | |
yield | |
elapsedTime = time.time() - startTime | |
print('[{}] finished in {} ms'.format(name, int(elapsedTime * 1000))) | |
# Return a generator to return a sequence of fibonnaci numbers | |
# note this means the entire list is never actually in memory. | |
def yield_fib(n): | |
if n > 0: | |
yield 1 | |
if n > 1: | |
yield 1 | |
prevprev = prev = 1 | |
for i in xrange(2,n): | |
cur = prevprev + prev | |
yield cur | |
prevprev = prev | |
prev = cur | |
# generate a list of fibonnaci numbers and return the list | |
def list_fib(n): | |
out = [] | |
if n > 0: | |
out.append(1) | |
if n > 1: | |
out.append(1) | |
prevprev = prev = 1 | |
for i in xrange(2,n): | |
cur = prevprev + prev | |
out.append(cur) | |
prevprev = prev | |
prev = cur | |
return out | |
def recur_fib_memoize_internal(n,accum=None): | |
# memoize partial results | |
if len(accum) >= n: | |
cur = accum[n-1] | |
return cur | |
if n == 0: | |
return 0 | |
elif n <= 2: | |
cur = 1 | |
accum += [1] * n | |
else: | |
prev = recur_fib_memoize_internal(n-1, accum) | |
prevprev = recur_fib_memoize_internal(n-2, accum) | |
cur = prevprev + prev | |
accum.append(cur) | |
return cur | |
# recurisve approach with memoization to return a sequence of fibonnaci numbers | |
# this still blows the stack somewhere pretty low | |
def recur_fib_memoize(n): | |
accum = [] | |
recur_fib_memoize_internal(n,accum) | |
return accum | |
def recur_nth_fib(n): | |
if n == 0: | |
return 0 | |
elif n == 1: | |
return 1 | |
elif n == 2: | |
return 1 | |
else: | |
v = recur_nth_fib(n-2) + recur_nth_fib(n-1) | |
return v | |
# purely recurisve approach to return a sequence of fibonnaci numbers | |
# beware - ridiculously inefficient | |
def recur_fib(n): | |
accum = [] | |
for i in range(1,n+1): | |
accum.append(recur_nth_fib(i)) | |
return accum | |
def test_fib(fib_func): | |
# avoid writing newline/be compatible with python2 or 3 | |
sys.stdout.write("testing fib function {}...".format(fib_func.func_name)) | |
x = list(fib_func(1)) | |
assert( len(x) == 1 ) | |
assert( x[0] == 1) | |
x = list(fib_func(2)) | |
assert( len(x) == 2 ) | |
assert( x[0] == 1) | |
assert( x[1] == 1) | |
x = list(fib_func(3)) | |
assert( len(x) == 3 ) | |
assert( x[0] == 1) | |
assert( x[2] == 2) | |
x = list(fib_func(5)) | |
assert( len(x) == 5 ) | |
assert( x[-1] == 5) | |
x = list(fib_func(6)) | |
assert( len(x) == 6 ) | |
assert( x[-1] == 8) | |
x = list(fib_func(7)) | |
assert( len(x) == 7 ) | |
assert( x[-1] == 13) | |
# http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibtable.html | |
tests = [ (20,6765), | |
(30,832040), | |
(40,102334155), | |
(50,12586269025), | |
(100,354224848179261915075)] | |
if fib_func.func_name == "recur_fib": | |
# too big to test for the recursive functions... | |
sys.stdout.write("skipping large values for recur_fib") | |
else: | |
for (nn,val) in tests: | |
x = list(fib_func(nn)) | |
assert( len(x) == nn ) | |
assert( x[-1] == val) | |
print("\ttests passed") | |
def sum_fib_series(magnitude, fib_func): | |
sum = 0 | |
for n in fib_func(10**magnitude): | |
sum += n | |
return sum | |
def time_one_fib(exp, func): | |
with timeit_context('Fib function {} for 10**{}'.format(func.func_name,exp)): | |
try: | |
sum_fib_series(exp, func) | |
except RuntimeError: | |
print(" hit a recursion depth limit for {}.".format(func.func_name)) | |
def time_fib(): | |
funcs = [recur_fib_memoize] | |
for exp in range(1,4): | |
for func in funcs: | |
time_one_fib(exp, func) | |
funcs = [yield_fib, list_fib] | |
for exp in range(1,7): | |
for func in funcs: | |
time_one_fib(exp, func) | |
if __name__ == '__main__': | |
for fib_func in (yield_fib, list_fib, recur_fib, recur_fib_memoize): | |
test_fib(fib_func) | |
time_fib() |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Stoll-MBP:fib pstoll$ python fib_fun.py | |
testing fib function yield_fib... tests passed | |
testing fib function list_fib... tests passed | |
testing fib function recur_fib... skipping large values for recur_fib tests passed | |
testing fib function recur_fib_memoize... tests passed | |
[Fib function recur_fib_memoize for 10**1] finished in 0 ms | |
[Fib function recur_fib_memoize for 10**2] finished in 0 ms | |
hit a recursion depth limit for recur_fib_memoize. | |
[Fib function recur_fib_memoize for 10**3] finished in 1 ms | |
[Fib function yield_fib for 10**1] finished in 0 ms | |
[Fib function list_fib for 10**1] finished in 0 ms | |
[Fib function yield_fib for 10**2] finished in 0 ms | |
[Fib function list_fib for 10**2] finished in 0 ms | |
[Fib function yield_fib for 10**3] finished in 0 ms | |
[Fib function list_fib for 10**3] finished in 0 ms | |
[Fib function yield_fib for 10**4] finished in 6 ms | |
[Fib function list_fib for 10**4] finished in 11 ms | |
[Fib function yield_fib for 10**5] finished in 322 ms | |
[Fib function list_fib for 10**5] finished in 674 ms | |
[Fib function yield_fib for 10**6] finished in 28306 ms | |
Killed: 9 | |
# note list_fib for 10**6 ran out of ram/swap space and was killed by the OS | |
# the moral being - avoid keeping huge lists in memory if you can avoid it - hence generators. |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment