Last active
September 12, 2018 22:49
-
-
Save schicks/08775a374752555373a9d21357a8cedc to your computer and use it in GitHub Desktop.
fibonacci
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
{ | |
"cells": [ | |
{ | |
"cell_type": "code", | |
"execution_count": 21, | |
"metadata": {}, | |
"outputs": [], | |
"source": [ | |
"def fib(n):\n", | |
" if n < 2:\n", | |
" return n\n", | |
" else: return fib(n-1)+fib(n-2) # O(2^n)" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 22, | |
"metadata": {}, | |
"outputs": [ | |
{ | |
"data": { | |
"text/plain": [ | |
"[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]" | |
] | |
}, | |
"execution_count": 22, | |
"metadata": {}, | |
"output_type": "execute_result" | |
} | |
], | |
"source": [ | |
"[fib(n) for n in range(10)]" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 33, | |
"metadata": {}, | |
"outputs": [ | |
{ | |
"name": "stdout", | |
"output_type": "stream", | |
"text": [ | |
"326 ms ± 14.9 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n" | |
] | |
} | |
], | |
"source": [ | |
"%timeit fib(30) # unbelievably slow, since it repeats a huge amount of work" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 23, | |
"metadata": {}, | |
"outputs": [], | |
"source": [ | |
"def helper(a, b, n):\n", | |
" if n < 2:\n", | |
" return b\n", | |
" else:\n", | |
" return helper(b, a+b, n-1)\n", | |
"def fib_rec(n):\n", | |
" return helper(0,1,n) # O(n)" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 24, | |
"metadata": {}, | |
"outputs": [ | |
{ | |
"data": { | |
"text/plain": [ | |
"[1, 1, 1, 2, 3, 5, 8, 13, 21, 34]" | |
] | |
}, | |
"execution_count": 24, | |
"metadata": {}, | |
"output_type": "execute_result" | |
} | |
], | |
"source": [ | |
"[fib_rec(n) for n in range(10)]" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 35, | |
"metadata": {}, | |
"outputs": [ | |
{ | |
"name": "stdout", | |
"output_type": "stream", | |
"text": [ | |
"50.5 µs ± 2 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n" | |
] | |
} | |
], | |
"source": [ | |
"%timeit fib_rec(300)" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 26, | |
"metadata": {}, | |
"outputs": [], | |
"source": [ | |
"def fib_dyn(n):\n", | |
" a,b = 1,1\n", | |
" for _ in range(2, n):\n", | |
" a, b = b, a+b\n", | |
" return b # O(n), but not recursive, so it doesn't hit pythons recursion limit." | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 27, | |
"metadata": {}, | |
"outputs": [ | |
{ | |
"data": { | |
"text/plain": [ | |
"[1, 1, 1, 2, 3, 5, 8, 13, 21, 34]" | |
] | |
}, | |
"execution_count": 27, | |
"metadata": {}, | |
"output_type": "execute_result" | |
} | |
], | |
"source": [ | |
"[fib_dyn(n) for n in range(10)]" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 36, | |
"metadata": {}, | |
"outputs": [ | |
{ | |
"name": "stdout", | |
"output_type": "stream", | |
"text": [ | |
"17.7 µs ± 434 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)\n" | |
] | |
} | |
], | |
"source": [ | |
"%timeit fib_dyn(300) # significantly faster than recursive because of the lack of overhead of python function calls" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 40, | |
"metadata": {}, | |
"outputs": [], | |
"source": [ | |
"def modified_helper(a,b,n):\n", | |
" if n < 2:\n", | |
" return (a,b,n)\n", | |
" else:\n", | |
" return modified_helper(b, a+b, n-1)\n", | |
"\n", | |
"def fib_rec_trampolined(n):\n", | |
" '''\n", | |
" Conceptually this is basically the same as the recursive version.\n", | |
" However, because it 'bounces' the state back up into the parent function, it avoids the recursion limit.\n", | |
" While this is still slower than the dynamic method because of function call overhead, it presents a straightforward way to convert tail recursive functions into iterative ones.\n", | |
" '''\n", | |
" a,b = 0,1\n", | |
" while n >=2:\n", | |
" (a, b, n) = modified_helper(a,b,n)\n", | |
" return b" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 41, | |
"metadata": {}, | |
"outputs": [ | |
{ | |
"data": { | |
"text/plain": [ | |
"[1, 1, 1, 2, 3, 5, 8, 13, 21, 34]" | |
] | |
}, | |
"execution_count": 41, | |
"metadata": {}, | |
"output_type": "execute_result" | |
} | |
], | |
"source": [ | |
"[fib_rec_trampolined(n) for n in range(10)]" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 42, | |
"metadata": {}, | |
"outputs": [ | |
{ | |
"name": "stdout", | |
"output_type": "stream", | |
"text": [ | |
"55.4 µs ± 1.6 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n" | |
] | |
} | |
], | |
"source": [ | |
"%timeit fib_rec_trampolined(300)" | |
] | |
} | |
], | |
"metadata": { | |
"kernelspec": { | |
"display_name": "Python 3", | |
"language": "python", | |
"name": "python3" | |
}, | |
"language_info": { | |
"codemirror_mode": { | |
"name": "ipython", | |
"version": 3 | |
}, | |
"file_extension": ".py", | |
"mimetype": "text/x-python", | |
"name": "python", | |
"nbconvert_exporter": "python", | |
"pygments_lexer": "ipython3", | |
"version": "3.6.5" | |
} | |
}, | |
"nbformat": 4, | |
"nbformat_minor": 2 | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment