Skip to content

Instantly share code, notes, and snippets.

@stharrold

stharrold/20150203T195000_interview_prep_fibonacci.ipynb

Last active August 29, 2015 14:14
Show Gist options
  • Save stharrold/bd9f398661a9e0c750e8 to your computer and use it in GitHub Desktop.
Save stharrold/bd9f398661a9e0c750e8 to your computer and use it in GitHub Desktop.
Download ZIP
Example using code for calculating Fibonacci sequence.
Display the source blob
Display the rendered blob
Raw
20150203T195000_interview_prep_fibonacci.ipynb
{
"metadata": {
"name": "",
"signature": "sha256:1ccd47cfa76345cafc44e098793c7571ecc27ccf791bb73bf94587c4d865052d"
},
"nbformat": 3,
"nbformat_minor": 0,
"worksheets": [
{
"cells": [
{
"cell_type": "heading",
"level": 1,
"metadata": {},
"source": [
"Example using code for calculating Fibonacci sequence."
]
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Path, imports, logger"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"cd ~/Documents/GitHub/stharrold/interview_prep/"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"/Users/harrold/Documents/GitHub/stharrold/interview_prep\n"
]
}
],
"prompt_number": 1
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"from __future__ import absolute_import, print_function, division\n",
"import os\n",
"import re\n",
"import sys\n",
"import logging\n",
"import tempfile\n",
"import interview_prep as ip\n",
"%load_ext line_profiler\n",
"%load_ext memory_profiler"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 2
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"logger = logging.getLogger()\n",
"shandler = logging.StreamHandler(sys.stdout)\n",
"logger.addHandler(shandler)"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 3
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Run tests"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"!py.test -v"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"\u001b[1m============================= test session starts ==============================\u001b[0m\r\n",
"platform darwin -- Python 2.7.8 -- py-1.4.25 -- pytest-2.6.3 -- /Users/harrold/anaconda/bin/python\r\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"\u001b[1m\r",
"collecting 0 items\u001b[0m"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"\u001b[1m\r",
"collecting 3 items\u001b[0m\u001b[1m\r",
"collected 3 items \r\n",
"\u001b[0m\r\n",
"tests/test_fibonacci/test_fib.py::test__init_fibs \u001b[32mPASSED\u001b[0m\r\n",
"tests/test_fibonacci/test_fib.py::test_fib_lookup \u001b[32mPASSED\u001b[0m\r\n",
"tests/test_fibonacci/test_fib.py::test_fib_recur \u001b[32mPASSED\u001b[0m\r\n",
"\r\n",
"\u001b[32m\u001b[1m=========================== 3 passed in 0.27 seconds ===========================\u001b[0m\r\n"
]
}
],
"prompt_number": 4
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Inspect code"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"logger.setLevel(logging.DEBUG)"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 5
},
{
"cell_type": "heading",
"level": 3,
"metadata": {},
"source": [
"Compute Fibonacci number with lookup"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print(ip.fibonacci.fib.fib_lookup.__doc__)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Compute Fibonacci number, looked up from an array.\n",
"\n",
" Parameters\n",
" ----------\n",
" idx : int\n",
" Index of Fibonacci number, >= 0.\n",
"\n",
" Returns\n",
" -------\n",
" fn : int\n",
" Fibonacci number at given index.\n",
"\n",
" Notes\n",
" -----\n",
" * Fibonacci sequence [1]_:\n",
" F_n = F_n-1 + F_n-2\n",
" * Complexities [2]_:\n",
" Time complexity is O(1) to O(n) for dynamic array.\n",
" Space complexity is O(n) for dynamic array.\n",
"\n",
" References\n",
" ----------\n",
" .. [1] http://en.wikipedia.org/wiki/Fibonacci_number\n",
" .. [2] http://bigocheatsheet.com/\n",
"\n",
" \n"
]
}
],
"prompt_number": 6
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# Global fibs is empty.\n",
"ip.fibonacci.fib.fibs"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 7,
"text": [
"[]"
]
}
],
"prompt_number": 7
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# Compute Fibonacci numbers up to index 5 with lookup.\n",
"ip.fibonacci.fib.fib_lookup(5)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stderr",
"text": [
"DEBUG:interview_prep.fibonacci.fib:Recursive call: fib_lookup(idx=4) + fib_lookup(idx=3)\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Recursive call: fib_lookup(idx=4) + fib_lookup(idx=3)\n"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
"DEBUG:interview_prep.fibonacci.fib:Recursive call: fib_lookup(idx=3) + fib_lookup(idx=2)\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Recursive call: fib_lookup(idx=3) + fib_lookup(idx=2)\n"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
"DEBUG:interview_prep.fibonacci.fib:Recursive call: fib_lookup(idx=2) + fib_lookup(idx=1)\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Recursive call: fib_lookup(idx=2) + fib_lookup(idx=1)\n"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
"DEBUG:interview_prep.fibonacci.fib:Recursive call: fib_lookup(idx=1) + fib_lookup(idx=0)\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Recursive call: fib_lookup(idx=1) + fib_lookup(idx=0)\n"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
"DEBUG:interview_prep.fibonacci.fib:F1 = 1\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"F1 = 1\n"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
"DEBUG:interview_prep.fibonacci.fib:fibs = [0, 1]\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"fibs = [0, 1]\n"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
"DEBUG:interview_prep.fibonacci.fib:F0 = 0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"F0 = 0\n"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
"DEBUG:interview_prep.fibonacci.fib:fibs = [0, 1]\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"fibs = [0, 1]\n"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
"DEBUG:interview_prep.fibonacci.fib:F2 = 1\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"F2 = 1\n"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
"DEBUG:interview_prep.fibonacci.fib:fibs = [0, 1, 1]\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"fibs = [0, 1, 1]\n"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
"DEBUG:interview_prep.fibonacci.fib:F1 = 1\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"F1 = 1\n"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
"DEBUG:interview_prep.fibonacci.fib:fibs = [0, 1, 1]\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"fibs = [0, 1, 1]\n"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
"DEBUG:interview_prep.fibonacci.fib:F3 = 2\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"F3 = 2\n"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
"DEBUG:interview_prep.fibonacci.fib:fibs = [0, 1, 1, 2]\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"fibs = [0, 1, 1, 2]\n"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
"DEBUG:interview_prep.fibonacci.fib:F2 = 1\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"F2 = 1\n"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
"DEBUG:interview_prep.fibonacci.fib:fibs = [0, 1, 1, 2]\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"fibs = [0, 1, 1, 2]\n"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
"DEBUG:interview_prep.fibonacci.fib:F4 = 3\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"F4 = 3\n"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
"DEBUG:interview_prep.fibonacci.fib:fibs = [0, 1, 1, 2, 3]\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"fibs = [0, 1, 1, 2, 3]\n"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
"DEBUG:interview_prep.fibonacci.fib:F3 = 2\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"F3 = 2\n"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
"DEBUG:interview_prep.fibonacci.fib:fibs = [0, 1, 1, 2, 3]\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"fibs = [0, 1, 1, 2, 3]\n"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
"DEBUG:interview_prep.fibonacci.fib:F5 = 5\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"F5 = 5\n"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
"DEBUG:interview_prep.fibonacci.fib:fibs = [0, 1, 1, 2, 3, 5]\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"fibs = [0, 1, 1, 2, 3, 5]\n"
]
},
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 8,
"text": [
"5"
]
}
],
"prompt_number": 8
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# Global fibs is now defined up to index 5.\n",
"ip.fibonacci.fib.fibs"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 9,
"text": [
"[0, 1, 1, 2, 3, 5]"
]
}
],
"prompt_number": 9
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# Again compute Fibonacci numbers up to index 5 with lookup.\n",
"ip.fibonacci.fib.fib_lookup(5)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stderr",
"text": [
"DEBUG:interview_prep.fibonacci.fib:F5 = 5\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"F5 = 5\n"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
"DEBUG:interview_prep.fibonacci.fib:fibs = [0, 1, 1, 2, 3, 5]\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"fibs = [0, 1, 1, 2, 3, 5]\n"
]
},
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 10,
"text": [
"5"
]
}
],
"prompt_number": 10
},
{
"cell_type": "heading",
"level": 3,
"metadata": {},
"source": [
"Compute Fibonacci number without lookup"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print(ip.fibonacci.fib.fib_recur.__doc__)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Compute Fibonacci number, recursively.\n",
"\n",
" Parameters\n",
" ----------\n",
" idx : int\n",
" Index of Fibonacci number, >= 0.\n",
"\n",
" Returns\n",
" -------\n",
" fn : int\n",
" Fibonacci number at given index.\n",
"\n",
" Notes\n",
" -----\n",
" * Fibonacci sequence [1_]:\n",
" F_n = F_n-1 + F_n-2\n",
" * Complexities [2]_, [3]_:\n",
" Time complexity is O(phi^n), where phi is golden ratio, ~1.6.\n",
" Space complexity is O(n), for storing 1 ``int`` for each of n stack frames.\n",
"\n",
" References\n",
" ----------\n",
" .. [1] http://en.wikipedia.org/wiki/Fibonacci_number\n",
" .. [2] http://stackoverflow.com/questions/360748/computational-complexity-of-fibonacci-sequence\n",
" .. [3] http://www.quora.com/What-is-the-space-complexity-of-a-recursive-fibonacci-function\n",
"\n",
" \n"
]
}
],
"prompt_number": 11
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# Compute Fibonacci numbers up to index 5 without lookup.\n",
"ip.fibonacci.fib.fib_recur(5)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stderr",
"text": [
"DEBUG:interview_prep.fibonacci.fib:Recursive call: fib_lookup(idx=4) + fib_lookup(idx=3)\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Recursive call: fib_lookup(idx=4) + fib_lookup(idx=3)\n"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
"DEBUG:interview_prep.fibonacci.fib:Recursive call: fib_lookup(idx=3) + fib_lookup(idx=2)\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Recursive call: fib_lookup(idx=3) + fib_lookup(idx=2)\n"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
"DEBUG:interview_prep.fibonacci.fib:Recursive call: fib_lookup(idx=2) + fib_lookup(idx=1)\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Recursive call: fib_lookup(idx=2) + fib_lookup(idx=1)\n"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
"DEBUG:interview_prep.fibonacci.fib:Recursive call: fib_lookup(idx=1) + fib_lookup(idx=0)\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Recursive call: fib_lookup(idx=1) + fib_lookup(idx=0)\n"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
"DEBUG:interview_prep.fibonacci.fib:F1 = 1\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"F1 = 1\n"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
"DEBUG:interview_prep.fibonacci.fib:F0 = 0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"F0 = 0\n"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
"DEBUG:interview_prep.fibonacci.fib:F2 = 1\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"F2 = 1\n"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
"DEBUG:interview_prep.fibonacci.fib:F1 = 1\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"F1 = 1\n"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
"DEBUG:interview_prep.fibonacci.fib:F3 = 2\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"F3 = 2\n"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
"DEBUG:interview_prep.fibonacci.fib:Recursive call: fib_lookup(idx=1) + fib_lookup(idx=0)\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Recursive call: fib_lookup(idx=1) + fib_lookup(idx=0)\n"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
"DEBUG:interview_prep.fibonacci.fib:F1 = 1\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"F1 = 1\n"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
"DEBUG:interview_prep.fibonacci.fib:F0 = 0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"F0 = 0\n"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
"DEBUG:interview_prep.fibonacci.fib:F2 = 1\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"F2 = 1\n"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
"DEBUG:interview_prep.fibonacci.fib:F4 = 3\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"F4 = 3\n"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
"DEBUG:interview_prep.fibonacci.fib:Recursive call: fib_lookup(idx=2) + fib_lookup(idx=1)\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Recursive call: fib_lookup(idx=2) + fib_lookup(idx=1)\n"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
"DEBUG:interview_prep.fibonacci.fib:Recursive call: fib_lookup(idx=1) + fib_lookup(idx=0)\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Recursive call: fib_lookup(idx=1) + fib_lookup(idx=0)\n"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
"DEBUG:interview_prep.fibonacci.fib:F1 = 1\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"F1 = 1\n"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
"DEBUG:interview_prep.fibonacci.fib:F0 = 0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"F0 = 0\n"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
"DEBUG:interview_prep.fibonacci.fib:F2 = 1\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"F2 = 1\n"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
"DEBUG:interview_prep.fibonacci.fib:F1 = 1\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"F1 = 1\n"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
"DEBUG:interview_prep.fibonacci.fib:F3 = 2\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"F3 = 2\n"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
"DEBUG:interview_prep.fibonacci.fib:F5 = 5\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"F5 = 5\n"
]
},
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 12,
"text": [
"5"
]
}
],
"prompt_number": 12
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Benchmark and profile complexity in time and space"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"`%timeit`: Time spent by the Python statement. \n",
"`%memit`: Memory used by the Python statement. \n",
"`sys.getsizeof()`: Compute size of in-memory object. \n",
"`%prun -s cumtime`: Time spent for each function call, sorted by cumulative time spent in each function. \n",
"`%lprun`: Time spent in each line. \n",
"`%mprun`: Memory used when running each line. "
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"logger.setLevel(logging.INFO)"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 13
},
{
"cell_type": "heading",
"level": 3,
"metadata": {},
"source": [
"Computing Fibonacci number with lookup"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"for idx in [2**pwr for pwr in xrange(11)]:\n",
" print()\n",
" print(\"Computing F{idx}\".format(idx=idx))\n",
" ip.fibonacci.fib._init_fibs()\n",
" %timeit ip.fibonacci.fib.fib_lookup(idx=idx)\n",
" %memit ip.fibonacci.fib.fib_lookup(idx=idx)\n",
" size_bytes = sys.getsizeof(ip.fibonacci.fib.fibs)\n",
" print(\"Size of in-memory global: {size} bytes\".format(size=size_bytes))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"\n",
"Computing F1\n",
"100000 loops, best of 3: 10.2 \u00b5s per loop"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"peak memory: 33.31 MiB, increment: 0.08 MiB\n",
"Size of in-memory global: 88 bytes\n",
"\n",
"Computing F2\n",
"100000 loops, best of 3: 10.5 \u00b5s per loop"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"peak memory: 33.36 MiB, increment: 0.01 MiB\n",
"Size of in-memory global: 120 bytes\n",
"\n",
"Computing F4\n",
"100000 loops, best of 3: 11 \u00b5s per loop"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"peak memory: 33.37 MiB, increment: 0.00 MiB\n",
"Size of in-memory global: 120 bytes\n",
"\n",
"Computing F8\n",
"100000 loops, best of 3: 12.2 \u00b5s per loop"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"peak memory: 33.38 MiB, increment: 0.00 MiB\n",
"Size of in-memory global: 152 bytes\n",
"\n",
"Computing F16\n",
"100000 loops, best of 3: 13.2 \u00b5s per loop"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"peak memory: 33.40 MiB, increment: 0.00 MiB\n",
"Size of in-memory global: 216 bytes\n",
"\n",
"Computing F32\n",
"100000 loops, best of 3: 15.7 \u00b5s per loop"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"peak memory: 33.41 MiB, increment: 0.00 MiB\n",
"Size of in-memory global: 368 bytes\n",
"\n",
"Computing F64\n",
"10000 loops, best of 3: 21.9 \u00b5s per loop"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"peak memory: 33.46 MiB, increment: 0.01 MiB\n",
"Size of in-memory global: 672 bytes\n",
"\n",
"Computing F128\n",
"10000 loops, best of 3: 37.4 \u00b5s per loop"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"peak memory: 33.55 MiB, increment: 0.00 MiB\n",
"Size of in-memory global: 1104 bytes\n",
"\n",
"Computing F256\n",
"10000 loops, best of 3: 86.4 \u00b5s per loop"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"peak memory: 33.73 MiB, increment: 0.00 MiB\n",
"Size of in-memory global: 2288 bytes\n",
"\n",
"Computing F512\n",
"1000 loops, best of 3: 284 \u00b5s per loop"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"peak memory: 34.06 MiB, increment: 0.00 MiB\n",
"Size of in-memory global: 4400 bytes\n",
"\n",
"Computing F1024\n",
"1 loops, best of 3: 257 \u00b5s per loop"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"\n"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F59 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F58 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F58 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F57 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F58 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F57 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F57 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F56 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F58 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F57 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F57 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F56 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F57 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F56 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F56 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F55 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F58 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F57 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F57 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F56 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F57 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F56 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F56 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F55 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F57 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F56 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F56 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F55 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F56 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F55 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F55 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F54 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F58 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F57 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F57 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F56 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F57 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F56 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F56 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F55 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F57 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F56 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F56 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F55 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F56 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F55 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F55 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F54 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F57 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F56 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F56 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F55 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F56 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F55 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F55 is set to nan\n",
"RuntimeError: maximum recursion depth exceeded while calling a Python object\n",
"F54 is set to nan\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"peak memory: 34.66 MiB, increment: 0.00 MiB\n",
"Size of in-memory global: 9288 bytes\n"
]
}
],
"prompt_number": 14
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"ip.fibonacci.fib._init_fibs()\n",
"prun_stats = %prun -r -s cumtime ip.fibonacci.fib.fib_lookup(idx=2**4)\n",
"prun_stats.print_stats()"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
" 480 function calls (450 primitive calls) in 0.001 seconds\n",
"\n",
" Ordered by: cumulative time\n",
"\n",
" ncalls tottime percall cumtime percall filename:lineno(function)\n",
" 1 0.000 0.000 0.001 0.001 <string>:1(<module>)\n",
" 31/1 0.000 0.000 0.001 0.001 fib.py:35(fib_lookup)\n",
" 77 0.000 0.000 0.000 0.000 __init__.py:1138(debug)\n",
" 77 0.000 0.000 0.000 0.000 __init__.py:1353(isEnabledFor)\n",
" 77 0.000 0.000 0.000 0.000 __init__.py:1339(getEffectiveLevel)\n",
" 77 0.000 0.000 0.000 0.000 {method 'format' of 'str' objects}\n",
" 62 0.000 0.000 0.000 0.000 {len}\n",
" 31 0.000 0.000 0.000 0.000 {isinstance}\n",
" 31 0.000 0.000 0.000 0.000 {globals}\n",
" 15 0.000 0.000 0.000 0.000 {method 'append' of 'list' objects}\n",
" 1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}\n",
"\n",
"\n"
]
},
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 15,
"text": [
"<pstats.Stats instance at 0x1027b9488>"
]
}
],
"prompt_number": 15
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"ip.fibonacci.fib._init_fibs()\n",
"lprun_stats = %lprun -f ip.fibonacci.fib.fib_lookup -r ip.fibonacci.fib.fib_lookup(idx=2**4)\n",
"lprun_stats.print_stats()"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Timer unit: 1e-06 s\n",
"\n",
"Total time: 0.001239 s\n",
"File: interview_prep/fibonacci/fib.py\n",
"Function: fib_lookup at line 35\n",
"\n",
"Line # Hits Time Per Hit % Time Line Contents\n",
"==============================================================\n",
" 35 def fib_lookup(idx):\n",
" 36 \"\"\"Compute Fibonacci number, looked up from an array.\n",
" 37 \n",
" 38 Parameters\n",
" 39 ----------\n",
" 40 idx : int\n",
" 41 Index of Fibonacci number, >= 0.\n",
" 42 \n",
" 43 Returns\n",
" 44 -------\n",
" 45 fn : int\n",
" 46 Fibonacci number at given index.\n",
" 47 \n",
" 48 Notes\n",
" 49 -----\n",
" 50 * Fibonacci sequence [1]_:\n",
" 51 F_n = F_n-1 + F_n-2\n",
" 52 * Complexities [2]_:\n",
" 53 Time complexity is O(1) to O(n) for dynamic array.\n",
" 54 Space complexity is O(n) for dynamic array.\n",
" 55 \n",
" 56 References\n",
" 57 ----------\n",
" 58 .. [1] http://en.wikipedia.org/wiki/Fibonacci_number\n",
" 59 .. [2] http://bigocheatsheet.com/\n",
" 60 \n",
" 61 \"\"\"\n",
" 62 # Check input.\n",
" 63 31 50 1.6 4.0 if not isinstance(idx, int):\n",
" 64 idx = int(idx)\n",
" 65 31 32 1.0 2.6 if idx < 0:\n",
" 66 raise ValueError((\"`idx` must be an ``int`` >= 0:\\n\" +\n",
" 67 \"idx = {idx}\").format(idx=idx))\n",
" 68 # Initialize fibs array and compute Fibonacci number.\n",
" 69 31 41 1.3 3.3 if 'fibs' not in globals():\n",
" 70 _init_fibs()\n",
" 71 31 40 1.3 3.2 if len(fibs) < 2:\n",
" 72 _init_fibs()\n",
" 73 31 41 1.3 3.3 if len(fibs) - 1 < idx:\n",
" 74 15 15 1.0 1.2 if idx > 1:\n",
" 75 # Note: Lookup F_n-1 before F_n-2 for clearer trace.\n",
" 76 15 16 1.1 1.3 try:\n",
" 77 15 22 1.5 1.8 logger.debug(\n",
" 78 15 19 1.3 1.5 (\"Recursive call: fib_lookup(idx={idxn1}) + fib_lookup(idx={idxn2})\").format(\n",
" 79 15 137 9.1 11.1 idxn1=idx-1, idxn2=idx-2))\n",
" 80 15 26 1.7 2.1 fn = fib_lookup(idx=idx-1) + fib_lookup(idx=idx-2)\n",
" 81 15 23 1.5 1.9 fibs.append(fn)\n",
" 82 except RuntimeError as err:\n",
" 83 fn = np.NaN\n",
" 84 print((\"RuntimeError: {err}\\n\" +\n",
" 85 \"F{idx} is set to {fn}\").format(err=err, idx=idx, fn=fn),\n",
" 86 file=sys.stderr)\n",
" 87 \n",
" 88 else:\n",
" 89 raise AssertionError((\"Program error. `fibs` must be initialized with [0,1]:\\n\" +\n",
" 90 \"fibs = {fibs}\").format(fibs=fibs))\n",
" 91 else:\n",
" 92 16 22 1.4 1.8 fn = fibs[idx]\n",
" 93 31 354 11.4 28.6 logger.debug((\"F{idx} = {fn}\").format(idx=idx, fn=fn))\n",
" 94 31 364 11.7 29.4 logger.debug((\"fibs = {fibs}\").format(fibs=fibs))\n",
" 95 31 37 1.2 3.0 return fn\n",
"\n"
]
}
],
"prompt_number": 16
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"ip.fibonacci.fib._init_fibs()\n",
"fout = os.path.join(tempfile.gettempdir(), 'mprun.txt')\n",
"%mprun -f ip.fibonacci.fib.fib_lookup -T $fout ip.fibonacci.fib.fib_lookup(idx=2**4)\n",
"with open(fout, 'rb') as fobj:\n",
" for line in fobj:\n",
" print(line.strip())"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"('',)\n",
"\n",
"*** Profile printout saved to text file /var/folders/y6/p22hbzpn3txcssg9ckv4p0bh0000gq/T/mprun.txt. \n",
"Filename: interview_prep/fibonacci/fib.py\n",
"\n",
"Line # Mem usage Increment Line Contents\n",
"================================================\n",
"35 34.7 MiB 0.0 MiB def fib_lookup(idx):\n",
"36 \"\"\"Compute Fibonacci number, looked up from an array.\n",
"37\n",
"38 Parameters\n",
"39 ----------\n",
"40 idx : int\n",
"41 Index of Fibonacci number, >= 0.\n",
"42\n",
"43 Returns\n",
"44 -------\n",
"45 fn : int\n",
"46 Fibonacci number at given index.\n",
"47\n",
"48 Notes\n",
"49 -----\n",
"50 * Fibonacci sequence [1]_:\n",
"51 F_n = F_n-1 + F_n-2\n",
"52 * Complexities [2]_:\n",
"53 Time complexity is O(1) to O(n) for dynamic array.\n",
"54 Space complexity is O(n) for dynamic array.\n",
"55\n",
"56 References\n",
"57 ----------\n",
"58 .. [1] http://en.wikipedia.org/wiki/Fibonacci_number\n",
"59 .. [2] http://bigocheatsheet.com/\n",
"60\n",
"61 \"\"\"\n",
"62 # Check input.\n",
"63 34.7 MiB 0.0 MiB if not isinstance(idx, int):\n",
"64 idx = int(idx)\n",
"65 34.7 MiB 0.0 MiB if idx < 0:\n",
"66 raise ValueError((\"`idx` must be an ``int`` >= 0:\\n\" +\n",
"67 \"idx = {idx}\").format(idx=idx))\n",
"68 # Initialize fibs array and compute Fibonacci number.\n",
"69 34.7 MiB 0.0 MiB if 'fibs' not in globals():\n",
"70 _init_fibs()\n",
"71 34.7 MiB 0.0 MiB if len(fibs) < 2:\n",
"72 _init_fibs()\n",
"73 34.7 MiB 0.0 MiB if len(fibs) - 1 < idx:\n",
"74 34.7 MiB 0.0 MiB if idx > 1:\n",
"75 # Note: Lookup F_n-1 before F_n-2 for clearer trace.\n",
"76 34.7 MiB 0.0 MiB try:\n",
"77 34.7 MiB 0.0 MiB logger.debug(\n",
"78 34.7 MiB 0.0 MiB (\"Recursive call: fib_lookup(idx={idxn1}) + fib_lookup(idx={idxn2})\").format(\n",
"79 34.7 MiB 0.0 MiB idxn1=idx-1, idxn2=idx-2))\n",
"80 fn = fib_lookup(idx=idx-1) + fib_lookup(idx=idx-2)\n",
"81 34.7 MiB 0.0 MiB fibs.append(fn)\n",
"82 except RuntimeError as err:\n",
"83 fn = np.NaN\n",
"84 print((\"RuntimeError: {err}\\n\" +\n",
"85 \"F{idx} is set to {fn}\").format(err=err, idx=idx, fn=fn),\n",
"86 file=sys.stderr)\n",
"87\n",
"88 else:\n",
"89 raise AssertionError((\"Program error. `fibs` must be initialized with [0,1]:\\n\" +\n",
"90 \"fibs = {fibs}\").format(fibs=fibs))\n",
"91 else:\n",
"92 34.7 MiB 0.0 MiB fn = fibs[idx]\n",
"93 34.7 MiB 0.0 MiB logger.debug((\"F{idx} = {fn}\").format(idx=idx, fn=fn))\n",
"94 34.7 MiB 0.0 MiB logger.debug((\"fibs = {fibs}\").format(fibs=fibs))\n",
"95 34.7 MiB 0.0 MiB return fn\n"
]
}
],
"prompt_number": 17
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Benchmark results for computing Fibonacci number with lookup: \n",
"* Time complexity is O(1) for n <~ 100; O(n) for n >~ 100. \n",
"* Space complexity is O(1) for n <~ 10; O(n) for n >~ 10. \n",
"* Note: As implemented here, `%memit` and `%mprun` did not include the memory usage by the global variable `fib.fibs`. Instead, `sys.getsizeof` was used."
]
},
{
"cell_type": "heading",
"level": 3,
"metadata": {},
"source": [
"Computing Fibonacci number without lookup"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"for idx in [2**pwr for pwr in xrange(6)]:\n",
" print()\n",
" print(\"Computing F{idx}\".format(idx=idx))\n",
" %timeit ip.fibonacci.fib.fib_recur(idx=idx)\n",
" %memit ip.fibonacci.fib.fib_recur(idx=idx)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"\n",
"Computing F1\n",
"100000 loops, best of 3: 3.94 \u00b5s per loop"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"peak memory: 34.71 MiB, increment: 0.00 MiB\n",
"\n",
"Computing F2\n",
"100000 loops, best of 3: 14.2 \u00b5s per loop"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"peak memory: 34.71 MiB, increment: 0.00 MiB\n",
"\n",
"Computing F4\n",
"10000 loops, best of 3: 45.1 \u00b5s per loop"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"peak memory: 34.71 MiB, increment: 0.00 MiB\n",
"\n",
"Computing F8\n",
"1000 loops, best of 3: 399 \u00b5s per loop"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"peak memory: 34.71 MiB, increment: 0.00 MiB\n",
"\n",
"Computing F16\n",
"100 loops, best of 3: 19.8 ms per loop"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"peak memory: 34.72 MiB, increment: 0.00 MiB\n",
"\n",
"Computing F32\n",
"1 loops, best of 3: 35.8 s per loop"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"peak memory: 34.72 MiB, increment: 0.00 MiB\n"
]
}
],
"prompt_number": 18
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"ip.fibonacci.fib._init_fibs()\n",
"prun_stats = %prun -r -s cumtime ip.fibonacci.fib.fib_recur(idx=2**4)\n",
"prun_stats.print_stats()"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
" 25544 function calls (22352 primitive calls) in 0.030 seconds\n",
"\n",
" Ordered by: cumulative time\n",
"\n",
" ncalls tottime percall cumtime percall filename:lineno(function)\n",
" 1 0.000 0.000 0.030 0.030 <string>:1(<module>)\n",
" 3193/1 0.012 0.000 0.030 0.030 fib.py:98(fib_recur)\n",
" 4789 0.003 0.000 0.012 0.000 __init__.py:1138(debug)\n",
" 4789 0.004 0.000 0.009 0.000 __init__.py:1353(isEnabledFor)\n",
" 4789 0.005 0.000 0.005 0.000 {method 'format' of 'str' objects}\n",
" 4789 0.005 0.000 0.005 0.000 __init__.py:1339(getEffectiveLevel)\n",
" 3193 0.000 0.000 0.000 0.000 {isinstance}\n",
" 1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}\n",
"\n",
"\n"
]
},
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 19,
"text": [
"<pstats.Stats instance at 0x10719b7e8>"
]
}
],
"prompt_number": 19
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"ip.fibonacci.fib._init_fibs()\n",
"lprun_stats = %lprun -f ip.fibonacci.fib.fib_recur -r ip.fibonacci.fib.fib_recur(idx=2**4)\n",
"lprun_stats.print_stats()"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Timer unit: 1e-06 s\n",
"\n",
"Total time: 0.098323 s\n",
"File: interview_prep/fibonacci/fib.py\n",
"Function: fib_recur at line 98\n",
"\n",
"Line # Hits Time Per Hit % Time Line Contents\n",
"==============================================================\n",
" 98 def fib_recur(idx):\n",
" 99 \"\"\"Compute Fibonacci number, recursively.\n",
" 100 \n",
" 101 Parameters\n",
" 102 ----------\n",
" 103 idx : int\n",
" 104 Index of Fibonacci number, >= 0.\n",
" 105 \n",
" 106 Returns\n",
" 107 -------\n",
" 108 fn : int\n",
" 109 Fibonacci number at given index.\n",
" 110 \n",
" 111 Notes\n",
" 112 -----\n",
" 113 * Fibonacci sequence [1_]:\n",
" 114 F_n = F_n-1 + F_n-2\n",
" 115 * Complexities [2]_, [3]_:\n",
" 116 Time complexity is O(phi^n), where phi is golden ratio, ~1.6.\n",
" 117 Space complexity is O(n), for storing 1 ``int`` for each of n stack frames.\n",
" 118 \n",
" 119 References\n",
" 120 ----------\n",
" 121 .. [1] http://en.wikipedia.org/wiki/Fibonacci_number\n",
" 122 .. [2] http://stackoverflow.com/questions/360748/computational-complexity-of-fibonacci-sequence\n",
" 123 .. [3] http://www.quora.com/What-is-the-space-complexity-of-a-recursive-fibonacci-function\n",
" 124 \n",
" 125 \"\"\"\n",
" 126 # Check input.\n",
" 127 3193 4143 1.3 4.2 if not isinstance(idx, int):\n",
" 128 idx = int(idx)\n",
" 129 3193 3982 1.2 4.0 if idx < 0:\n",
" 130 raise ValueError((\"`idx` must be an ``int`` >= 0:\\n\" +\n",
" 131 \"idx = {idx}\").format(idx=idx))\n",
" 132 # Compute Fibonacci number.\n",
" 133 3193 3380 1.1 3.4 if idx == 0:\n",
" 134 610 653 1.1 0.7 fn = 0\n",
" 135 2583 3177 1.2 3.2 elif idx == 1:\n",
" 136 987 2132 2.2 2.2 fn = 1\n",
" 137 1596 15243 9.6 15.5 elif idx > 1:\n",
" 138 # Note: Lookup F_n-1 before F_n-2 for clearer trace.\n",
" 139 1596 2069 1.3 2.1 try:\n",
" 140 1596 1975 1.2 2.0 logger.debug(\n",
" 141 1596 1738 1.1 1.8 (\"Recursive call: fib_lookup(idx={idxn1}) + fib_lookup(idx={idxn2})\").format(\n",
" 142 1596 20834 13.1 21.2 idxn1=idx-1, idxn2=idx-2))\n",
" 143 1596 2505 1.6 2.5 fn = fib_recur(idx=idx-1) + fib_recur(idx=idx-2)\n",
" 144 except RuntimeError as err:\n",
" 145 print(err, file=sys.stderr)\n",
" 146 else:\n",
" 147 raise AssertionError((\"Program error. `idx` must be an ``int`` >= 0:\\n\" +\n",
" 148 \"idx = {idx}\").format(idx=idx))\n",
" 149 3193 33082 10.4 33.6 logger.debug((\"F{idx} = {fn}\").format(idx=idx, fn=fn))\n",
" 150 3193 3410 1.1 3.5 return fn\n",
"\n"
]
}
],
"prompt_number": 20
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"ip.fibonacci.fib._init_fibs()\n",
"fout = os.path.join(tempfile.gettempdir(), 'mprun.txt')\n",
"%mprun -f ip.fibonacci.fib.fib_recur -T $fout ip.fibonacci.fib.fib_recur(idx=2**4)\n",
"with open(fout, 'rb') as fobj:\n",
" for line in fobj:\n",
" print(line.strip())"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"('',)\n",
"\n",
"*** Profile printout saved to text file /var/folders/y6/p22hbzpn3txcssg9ckv4p0bh0000gq/T/mprun.txt. \n",
"Filename: interview_prep/fibonacci/fib.py\n",
"\n",
"Line # Mem usage Increment Line Contents\n",
"================================================\n",
"98 34.7 MiB 0.0 MiB def fib_recur(idx):\n",
"99 \"\"\"Compute Fibonacci number, recursively.\n",
"100\n",
"101 Parameters\n",
"102 ----------\n",
"103 idx : int\n",
"104 Index of Fibonacci number, >= 0.\n",
"105\n",
"106 Returns\n",
"107 -------\n",
"108 fn : int\n",
"109 Fibonacci number at given index.\n",
"110\n",
"111 Notes\n",
"112 -----\n",
"113 * Fibonacci sequence [1_]:\n",
"114 F_n = F_n-1 + F_n-2\n",
"115 * Complexities [2]_, [3]_:\n",
"116 Time complexity is O(phi^n), where phi is golden ratio, ~1.6.\n",
"117 Space complexity is O(n), for storing 1 ``int`` for each of n stack frames.\n",
"118\n",
"119 References\n",
"120 ----------\n",
"121 .. [1] http://en.wikipedia.org/wiki/Fibonacci_number\n",
"122 .. [2] http://stackoverflow.com/questions/360748/computational-complexity-of-fibonacci-sequence\n",
"123 .. [3] http://www.quora.com/What-is-the-space-complexity-of-a-recursive-fibonacci-function\n",
"124\n",
"125 \"\"\"\n",
"126 # Check input.\n",
"127 34.7 MiB 0.0 MiB if not isinstance(idx, int):\n",
"128 idx = int(idx)\n",
"129 34.7 MiB 0.0 MiB if idx < 0:\n",
"130 raise ValueError((\"`idx` must be an ``int`` >= 0:\\n\" +\n",
"131 \"idx = {idx}\").format(idx=idx))\n",
"132 # Compute Fibonacci number.\n",
"133 34.7 MiB 0.0 MiB if idx == 0:\n",
"134 34.7 MiB 0.0 MiB fn = 0\n",
"135 34.7 MiB 0.0 MiB elif idx == 1:\n",
"136 34.7 MiB 0.0 MiB fn = 1\n",
"137 34.7 MiB 0.0 MiB elif idx > 1:\n",
"138 # Note: Lookup F_n-1 before F_n-2 for clearer trace.\n",
"139 34.7 MiB 0.0 MiB try:\n",
"140 34.7 MiB 0.0 MiB logger.debug(\n",
"141 34.7 MiB 0.0 MiB (\"Recursive call: fib_lookup(idx={idxn1}) + fib_lookup(idx={idxn2})\").format(\n",
"142 34.7 MiB 0.0 MiB idxn1=idx-1, idxn2=idx-2))\n",
"143 fn = fib_recur(idx=idx-1) + fib_recur(idx=idx-2)\n",
"144 except RuntimeError as err:\n",
"145 print(err, file=sys.stderr)\n",
"146 else:\n",
"147 raise AssertionError((\"Program error. `idx` must be an ``int`` >= 0:\\n\" +\n",
"148 \"idx = {idx}\").format(idx=idx))\n",
"149 34.7 MiB 0.0 MiB logger.debug((\"F{idx} = {fn}\").format(idx=idx, fn=fn))\n",
"150 34.7 MiB 0.0 MiB return fn\n"
]
}
],
"prompt_number": 21
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Benchmark results for computing Fibonacci number without lookup: \n",
"* Time complexity is O(~1.6^n) for n >~ 2 \n",
"* Space complexity was not accounted for. \n",
"* Note: As implemented here, `%memit` and `%mprun` did not include the memory usage by recurring stack frames."
]
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Check PEP8 compliance"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"!pylint interview_prep/fibonacci"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"No config file found, using default configuration\r\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"************* Module interview_prep.fibonacci.fib\r\n",
"C: 13, 0: Invalid constant name \"logger\" (invalid-name)\r\n",
"C: 14, 0: Invalid constant name \"fibs\" (invalid-name)\r\n",
"W: 30, 4: Using the global statement (global-statement)\r\n",
"C: 30, 4: Invalid constant name \"fibs\" (invalid-name)\r\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"W: 78,21: Use % formatting in logging functions but pass the % parameters as arguments (logging-format-interpolation)\r\n",
"C: 80,16: Invalid variable name \"fn\" (invalid-name)\r\n",
"C: 83,16: Invalid variable name \"fn\" (invalid-name)\r\n",
"E: 83,21: Module 'numpy' has no 'NaN' member (no-member)\r\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"C: 92, 8: Invalid variable name \"fn\" (invalid-name)\r\n",
"W: 93,18: Use % formatting in logging functions but pass the % parameters as arguments (logging-format-interpolation)\r\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"W: 94,18: Use % formatting in logging functions but pass the % parameters as arguments (logging-format-interpolation)\r\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"C:134, 8: Invalid variable name \"fn\" (invalid-name)\r\n",
"C:136, 8: Invalid variable name \"fn\" (invalid-name)\r\n",
"W:141,17: Use % formatting in logging functions but pass the % parameters as arguments (logging-format-interpolation)\r\n",
"C:143,12: Invalid variable name \"fn\" (invalid-name)\r\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"W:149,18: Use % formatting in logging functions but pass the % parameters as arguments (logging-format-interpolation)\r\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"\r\n",
"\r\n",
"Report\r\n",
"======\r\n",
"53 statements analysed.\r\n",
"\r\n",
"Statistics by type\r\n",
"------------------\r\n",
"\r\n",
"+---------+-------+-----------+-----------+------------+---------+\r\n",
"|type |number |old number |difference |%documented |%badname |\r\n",
"+=========+=======+===========+===========+============+=========+\r\n",
"|module |2 |2 |= |100.00 |0.00 |\r\n",
"+---------+-------+-----------+-----------+------------+---------+\r\n",
"|class |0 |0 |= |0 |0 |\r\n",
"+---------+-------+-----------+-----------+------------+---------+\r\n",
"|method |0 |0 |= |0 |0 |\r\n",
"+---------+-------+-----------+-----------+------------+---------+\r\n",
"|function |3 |3 |= |100.00 |0.00 |\r\n",
"+---------+-------+-----------+-----------+------------+---------+\r\n",
"\r\n",
"\r\n",
"\r\n",
"External dependencies\r\n",
"---------------------\r\n",
"::\r\n",
"\r\n",
" numpy (interview_prep.fibonacci.fib)\r\n",
"\r\n",
"\r\n",
"\r\n",
"Raw metrics\r\n",
"-----------\r\n",
"\r\n",
"+----------+-------+------+---------+-----------+\r\n",
"|type |number |% |previous |difference |\r\n",
"+==========+=======+======+=========+===========+\r\n",
"|code |60 |38.46 |60 |= |\r\n",
"+----------+-------+------+---------+-----------+\r\n",
"|docstring |76 |48.72 |76 |= |\r\n",
"+----------+-------+------+---------+-----------+\r\n",
"|comment |4 |2.56 |4 |= |\r\n",
"+----------+-------+------+---------+-----------+\r\n",
"|empty |16 |10.26 |16 |= |\r\n",
"+----------+-------+------+---------+-----------+\r\n",
"\r\n",
"\r\n",
"\r\n",
"Duplication\r\n",
"-----------\r\n",
"\r\n",
"+-------------------------+------+---------+-----------+\r\n",
"| |now |previous |difference |\r\n",
"+=========================+======+=========+===========+\r\n",
"|nb duplicated lines |0 |0 |= |\r\n",
"+-------------------------+------+---------+-----------+\r\n",
"|percent duplicated lines |0.000 |0.000 |= |\r\n",
"+-------------------------+------+---------+-----------+\r\n",
"\r\n",
"\r\n",
"\r\n",
"Messages by category\r\n",
"--------------------\r\n",
"\r\n",
"+-----------+-------+---------+-----------+\r\n",
"|type |number |previous |difference |\r\n",
"+===========+=======+=========+===========+\r\n",
"|convention |9 |9 |= |\r\n",
"+-----------+-------+---------+-----------+\r\n",
"|refactor |0 |0 |= |\r\n",
"+-----------+-------+---------+-----------+\r\n",
"|warning |6 |6 |= |\r\n",
"+-----------+-------+---------+-----------+\r\n",
"|error |1 |1 |= |\r\n",
"+-----------+-------+---------+-----------+\r\n",
"\r\n",
"\r\n",
"\r\n",
"% errors / warnings by module\r\n",
"-----------------------------\r\n",
"\r\n",
"+-----------------------------+-------+--------+---------+-----------+\r\n",
"|module |error |warning |refactor |convention |\r\n",
"+=============================+=======+========+=========+===========+\r\n",
"|interview_prep.fibonacci.fib |100.00 |100.00 |0.00 |100.00 |\r\n",
"+-----------------------------+-------+--------+---------+-----------+\r\n",
"\r\n",
"\r\n",
"\r\n",
"Messages\r\n",
"--------\r\n",
"\r\n",
"+-----------------------------+------------+\r\n",
"|message id |occurrences |\r\n",
"+=============================+============+\r\n",
"|invalid-name |9 |\r\n",
"+-----------------------------+------------+\r\n",
"|logging-format-interpolation |5 |\r\n",
"+-----------------------------+------------+\r\n",
"|no-member |1 |\r\n",
"+-----------------------------+------------+\r\n",
"|global-statement |1 |\r\n",
"+-----------------------------+------------+\r\n",
"\r\n",
"\r\n",
"\r\n",
"Global evaluation\r\n",
"-----------------\r\n",
"Your code has been rated at 6.23/10 (previous run: 6.23/10, +0.00)\r\n",
"\r\n"
]
}
],
"prompt_number": 22
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"pylint rating: ~6/10. \n",
"Complaints include: \n",
"* Global variable `fibs` should be called `FIBS` if it were a constant, but it's a list. \n",
"* Logging strings should use `%` instead of `.format()`.\n",
"* `fn` is considered an improper variable name."
]
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Clean up"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"logger.removeHandler(shandler)"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 23
}
],
"metadata": {}
}
]
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment