fibonacci-functions.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "\n",
       "<div id=\"altair-viz-508c190d1da64d7ba2a5c9d61c11ec2e\"></div>\n",
       "<script type=\"text/javascript\">\n",
       "  var VEGA_DEBUG = (typeof VEGA_DEBUG == \"undefined\") ? {} : VEGA_DEBUG;\n",
       "  (function(spec, embedOpt){\n",
       "    let outputDiv = document.currentScript.previousElementSibling;\n",
       "    if (outputDiv.id !== \"altair-viz-508c190d1da64d7ba2a5c9d61c11ec2e\") {\n",
       "      outputDiv = document.getElementById(\"altair-viz-508c190d1da64d7ba2a5c9d61c11ec2e\");\n",
       "    }\n",
       "    const paths = {\n",
       "      \"vega\": \"https://cdn.jsdelivr.net/npm//vega@5?noext\",\n",
       "      \"vega-lib\": \"https://cdn.jsdelivr.net/npm//vega-lib?noext\",\n",
       "      \"vega-lite\": \"https://cdn.jsdelivr.net/npm//vega-lite@4.17.0?noext\",\n",
       "      \"vega-embed\": \"https://cdn.jsdelivr.net/npm//vega-embed@6?noext\",\n",
       "    };\n",
       "\n",
       "    function maybeLoadScript(lib, version) {\n",
       "      var key = `${lib.replace(\"-\", \"\")}_version`;\n",
       "      return (VEGA_DEBUG[key] == version) ?\n",
       "        Promise.resolve(paths[lib]) :\n",
       "        new Promise(function(resolve, reject) {\n",
       "          var s = document.createElement('script');\n",
       "          document.getElementsByTagName(\"head\")[0].appendChild(s);\n",
       "          s.async = true;\n",
       "          s.onload = () => {\n",
       "            VEGA_DEBUG[key] = version;\n",
       "            return resolve(paths[lib]);\n",
       "          };\n",
       "          s.onerror = () => reject(`Error loading script: ${paths[lib]}`);\n",
       "          s.src = paths[lib];\n",
       "        });\n",
       "    }\n",
       "\n",
       "    function showError(err) {\n",
       "      outputDiv.innerHTML = `<div class=\"error\" style=\"color:red;\">${err}</div>`;\n",
       "      throw err;\n",
       "    }\n",
       "\n",
       "    function displayChart(vegaEmbed) {\n",
       "      vegaEmbed(outputDiv, spec, embedOpt)\n",
       "        .catch(err => showError(`Javascript Error: ${err.message}<br>This usually means there's a typo in your chart specification. See the javascript console for the full traceback.`));\n",
       "    }\n",
       "\n",
       "    if(typeof define === \"function\" && define.amd) {\n",
       "      requirejs.config({paths});\n",
       "      require([\"vega-embed\"], displayChart, err => showError(`Error loading script: ${err.message}`));\n",
       "    } else {\n",
       "      maybeLoadScript(\"vega\", \"5\")\n",
       "        .then(() => maybeLoadScript(\"vega-lite\", \"4.17.0\"))\n",
       "        .then(() => maybeLoadScript(\"vega-embed\", \"6\"))\n",
       "        .catch(showError)\n",
       "        .then(() => displayChart(vegaEmbed));\n",
       "    }\n",
       "  })({\"config\": {\"view\": {\"continuousWidth\": 400, \"continuousHeight\": 300}}, \"data\": {\"name\": \"data-2f4fe6fe43515b3b91ba86a3b96c4abc\"}, \"mark\": \"line\", \"encoding\": {\"color\": {\"field\": \"Method\", \"type\": \"nominal\"}, \"x\": {\"field\": \"n\", \"type\": \"quantitative\"}, \"y\": {\"field\": \"Time\", \"scale\": {\"type\": \"log\"}, \"type\": \"quantitative\"}}, \"$schema\": \"https://vega.github.io/schema/vega-lite/v4.17.0.json\", \"datasets\": {\"data-2f4fe6fe43515b3b91ba86a3b96c4abc\": [{\"n\": 0, \"Method\": \"recursive\", \"Time\": 1.2090000041098392e-06}, {\"n\": 1, \"Method\": \"recursive\", \"Time\": 4.1699999542288424e-07}, {\"n\": 2, \"Method\": \"recursive\", \"Time\": 7.500000123172867e-07}, {\"n\": 3, \"Method\": \"recursive\", \"Time\": 6.660000053670956e-07}, {\"n\": 4, \"Method\": \"recursive\", \"Time\": 9.169999941605056e-07}, {\"n\": 5, \"Method\": \"recursive\", \"Time\": 1.2499999968440534e-06}, {\"n\": 6, \"Method\": \"recursive\", \"Time\": 1.917000005846603e-06}, {\"n\": 7, \"Method\": \"recursive\", \"Time\": 2.8329999963716546e-06}, {\"n\": 8, \"Method\": \"recursive\", \"Time\": 4.458999995904378e-06}, {\"n\": 9, \"Method\": \"recursive\", \"Time\": 7.166999992591627e-06}, {\"n\": 10, \"Method\": \"recursive\", \"Time\": 1.1499999999387e-05}, {\"n\": 11, \"Method\": \"recursive\", \"Time\": 1.866600000255403e-05}, {\"n\": 12, \"Method\": \"recursive\", \"Time\": 3.041600000130984e-05}, {\"n\": 13, \"Method\": \"recursive\", \"Time\": 4.4625000001019544e-05}, {\"n\": 14, \"Method\": \"recursive\", \"Time\": 7.200000000295859e-05}, {\"n\": 15, \"Method\": \"recursive\", \"Time\": 0.00022583399999120957}, {\"n\": 16, \"Method\": \"recursive\", \"Time\": 0.00018820799999730298}, {\"n\": 17, \"Method\": \"recursive\", \"Time\": 0.0003037910000074362}, {\"n\": 18, \"Method\": \"recursive\", \"Time\": 0.0006939999999957536}, {\"n\": 19, \"Method\": \"recursive\", \"Time\": 0.001037334000002943}, {\"n\": 20, \"Method\": \"recursive\", \"Time\": 0.0018172500000019909}, {\"n\": 21, \"Method\": \"recursive\", \"Time\": 0.002051625000007107}, {\"n\": 22, \"Method\": \"recursive\", \"Time\": 0.0032714169999934484}, {\"n\": 23, \"Method\": \"recursive\", \"Time\": 0.005537416999999323}, {\"n\": 24, \"Method\": \"recursive\", \"Time\": 0.00863524999999754}, {\"n\": 25, \"Method\": \"recursive\", \"Time\": 0.01403345800000011}, {\"n\": 26, \"Method\": \"recursive\", \"Time\": 0.022663125000008222}, {\"n\": 27, \"Method\": \"recursive\", \"Time\": 0.03555641699999512}, {\"n\": 28, \"Method\": \"recursive\", \"Time\": 0.05723600000000317}, {\"n\": 29, \"Method\": \"recursive\", \"Time\": 0.09203879199999676}, {\"n\": 0, \"Method\": \"iterative\", \"Time\": 7.090000053722179e-07}, {\"n\": 1, \"Method\": \"iterative\", \"Time\": 3.339999921081471e-07}, {\"n\": 2, \"Method\": \"iterative\", \"Time\": 5.419999951072896e-07}, {\"n\": 3, \"Method\": \"iterative\", \"Time\": 4.5899999179255246e-07}, {\"n\": 4, \"Method\": \"iterative\", \"Time\": 4.1699999542288424e-07}, {\"n\": 5, \"Method\": \"iterative\", \"Time\": 4.5800000236795313e-07}, {\"n\": 6, \"Method\": \"iterative\", \"Time\": 4.999999987376214e-07}, {\"n\": 7, \"Method\": \"iterative\", \"Time\": 5.419999951072896e-07}, {\"n\": 8, \"Method\": \"iterative\", \"Time\": 7.090000053722179e-07}, {\"n\": 9, \"Method\": \"iterative\", \"Time\": 6.249999984220267e-07}, {\"n\": 10, \"Method\": \"iterative\", \"Time\": 6.659999911562409e-07}, {\"n\": 11, \"Method\": \"iterative\", \"Time\": 7.49999998106432e-07}, {\"n\": 12, \"Method\": \"iterative\", \"Time\": 7.910000050515009e-07}, {\"n\": 13, \"Method\": \"iterative\", \"Time\": 8.330000014211691e-07}, {\"n\": 14, \"Method\": \"iterative\", \"Time\": 9.159999905250515e-07}, {\"n\": 15, \"Method\": \"iterative\", \"Time\": 1.041999993844911e-06}, {\"n\": 16, \"Method\": \"iterative\", \"Time\": 1.167000007740171e-06}, {\"n\": 17, \"Method\": \"iterative\", \"Time\": 1.2499999968440534e-06}, {\"n\": 18, \"Method\": \"iterative\", \"Time\": 1.166000004104717e-06}, {\"n\": 19, \"Method\": \"iterative\", \"Time\": 1.2080000004743852e-06}, {\"n\": 20, \"Method\": \"iterative\", \"Time\": 1.2080000004743852e-06}, {\"n\": 21, \"Method\": \"iterative\", \"Time\": 1.2910000037891223e-06}, {\"n\": 22, \"Method\": \"iterative\", \"Time\": 1.3340000037942445e-06}, {\"n\": 23, \"Method\": \"iterative\", \"Time\": 1.3749999965284587e-06}, {\"n\": 24, \"Method\": \"iterative\", \"Time\": 1.4170000071089817e-06}, {\"n\": 25, \"Method\": \"iterative\", \"Time\": 1.499999996212864e-06}, {\"n\": 26, \"Method\": \"iterative\", \"Time\": 1.541000003157933e-06}, {\"n\": 27, \"Method\": \"iterative\", \"Time\": 1.6249999958972694e-06}, {\"n\": 28, \"Method\": \"iterative\", \"Time\": 1.6249999958972694e-06}, {\"n\": 29, \"Method\": \"iterative\", \"Time\": 1.7079999992120065e-06}]}}, {\"mode\": \"vega-lite\"});\n",
       "</script>"
      ],
      "text/plain": [
       "alt.Chart(...)"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import altair as alt\n",
    "import pandas as pd\n",
    "from timeit import timeit\n",
    "\n",
    "def fibonacci_recursive(n):\n",
    "    if n < 2:\n",
    "        return n\n",
    "    return fibonacci_recursive(n - 2) + fibonacci_recursive(n - 1)\n",
    "\n",
    "def fibonacci_iterative(n):\n",
    "    a = 0\n",
    "    b = 1\n",
    "    if n == 0:\n",
    "        return a\n",
    "    if n == 1:\n",
    "        return b\n",
    "    i = 1\n",
    "    while i < n:\n",
    "        c = a + b\n",
    "        a = b\n",
    "        b = c\n",
    "        i += 1\n",
    "    return b\n",
    "\n",
    "funcs = {\n",
    "    \"recursive\": fibonacci_recursive,\n",
    "    \"iterative\": fibonacci_iterative\n",
    "}\n",
    "\n",
    "df = pd.DataFrame({\n",
    "    k: [timeit(lambda: v(n), number=1) for n in range(30)]\n",
    "    for k,v in funcs.items()\n",
    "})\n",
    "\n",
    "df = df.reset_index().melt(id_vars=\"index\", value_vars=funcs.keys())\n",
    "df = df.rename(columns={\"index\": \"n\", \"value\": \"Time\", \"variable\": \"Method\"})\n",
    "\n",
    "alt.Chart(df).mark_line().encode(\n",
    "    x=alt.X(\"n\"),\n",
    "    y=alt.Y(\"Time\", scale=alt.Scale(type=\"log\")),\n",
    "    color=\"Method\"\n",
    ")"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}