{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"**Note**: Click on \"*Kernel*\" > \"*Restart Kernel and Clear All Outputs*\" in [JupyterLab](https://jupyterlab.readthedocs.io/en/stable/) *before* reading this notebook to reset its output. If you cannot run this file on your machine, you may want to open it [in the cloud <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_mb.png\">](https://mybinder.org/v2/gh/webartifex/intro-to-python/develop?urlpath=lab/tree/09_mappings/02_content.ipynb)."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"# Chapter 9: Mappings & Sets (continued)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"After introducing the `dict` type in the [first part <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_nb.png\">](https://nbviewer.jupyter.org/github/webartifex/intro-to-python/blob/develop/09_mappings/00_content.ipynb) of this chapter, we first look at an extension of the packing and unpacking syntax that involves `dict` objects. Then, we see how mappings can help us write computationally more efficient implementations to recursive solutions of problems as introduced in [Chapter 4 <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_nb.png\">](https://nbviewer.jupyter.org/github/webartifex/intro-to-python/blob/develop/04_iteration/00_content.ipynb#Recursion). In a way, this second part of the chapter \"finishes\" Chapter 4."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Packing & Unpacking (continued)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"Just as a single `*` symbol is used for packing and unpacking iterables in [Chapter 7 <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_nb.png\">](https://nbviewer.jupyter.org/github/webartifex/intro-to-python/blob/develop/07_sequences/03_content.ipynb#Packing-&-Unpacking), a double `**` symbol implements packing and unpacking for mappings.\n",
"\n",
"Let's say we have `to_words` and `more_words` as below and want to merge the items together into a *new* `dict` object."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [],
"source": [
"to_words = {\n",
" 0: \"zero\",\n",
" 1: \"one\",\n",
" 2: \"two\",\n",
"}"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"more_words = {\n",
" 2: \"TWO\", # to illustrate a point\n",
" 3: \"three\",\n",
" 4: \"four\",\n",
"}"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"By *unpacking* the items with `**`, the newly created `dict` object is first filled with the items from `to_words` and then from `more_words`. The item with the key `2` from `more_words` overwrites its counterpart from `to_words` as it is mentioned last."
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"{0: 'zero', 1: 'one', 2: 'TWO', 3: 'three', 4: 'four'}"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"{**to_words, **more_words}"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"### Function Definitions & Calls (continued)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"Both, `*` and `**` may be used within the header line of a function definition, for example, as in `print_args1()` below. Here, *positional* arguments not captured by positional parameters are *packed* into the `tuple` object `args`, and *keyword* arguments not captured by keyword parameters are *packed* into the `dict` object `kwargs`.\n",
"\n",
"For `print_args1()`, all arguments are optional, and ..."
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [],
"source": [
"def print_args1(*args, **kwargs):\n",
" \"\"\"Print out all arguments passed in.\"\"\"\n",
" for index, arg in enumerate(args):\n",
" print(\"position\", index, arg)\n",
"\n",
" for key, value in kwargs.items():\n",
" print(\"keyword\", key, value)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"... we may pass whatever we want to it, or nothing at all."
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [],
"source": [
"print_args1()"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"position 0 a\n",
"position 1 b\n",
"position 2 c\n"
]
}
],
"source": [
"print_args1(\"a\", \"b\", \"c\")"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"keyword first 1\n",
"keyword second 2\n",
"keyword third 3\n"
]
}
],
"source": [
"print_args1(first=1, second=2, third=3)"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"position 0 x\n",
"position 1 y\n",
"keyword flag True\n"
]
}
],
"source": [
"print_args1(\"x\", \"y\", flag=True)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"We may even unpack `dict` and `list` objects."
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [],
"source": [
"flags = {\"flag\": True, \"another_flag\": False}"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"keyword flag True\n",
"keyword another_flag False\n"
]
}
],
"source": [
"print_args1(**flags)"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"position 0 42\n",
"position 1 87\n",
"keyword flag True\n",
"keyword another_flag False\n"
]
}
],
"source": [
"print_args1(*[42, 87], **flags)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"The next example, `print_args2()`, requires the caller to pass one positional argument, captured in the `positional` parameter, and one keyword argument, captured in `keyword`. Further, an optional keyword argument `default` may be passed in. Any other positional or keyword arguments are packed into either `args` or `kwargs`."
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [],
"source": [
"def print_args2(positional, *args, keyword, default=True, **kwargs):\n",
" \"\"\"Print out all arguments passed in.\"\"\"\n",
" print(\"required positional\", positional)\n",
"\n",
" for index, arg in enumerate(args):\n",
" print(\"optional positional\", index, arg)\n",
"\n",
" print(\"required keyword\", keyword)\n",
" print(\"default keyword\", default)\n",
"\n",
" for key, value in kwargs.items():\n",
" print(\"optional keyword\", key, value)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"If the caller does not respect that, a `TypeError` is raised."
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [
{
"ename": "TypeError",
"evalue": "print_args2() missing 1 required positional argument: 'positional'",
"output_type": "error",
"traceback": [
"\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
"\u001b[0;31mTypeError\u001b[0m Traceback (most recent call last)",
"Cell \u001b[0;32mIn[13], line 1\u001b[0m\n\u001b[0;32m----> 1\u001b[0m \u001b[43mprint_args2\u001b[49m\u001b[43m(\u001b[49m\u001b[43m)\u001b[49m\n",
"\u001b[0;31mTypeError\u001b[0m: print_args2() missing 1 required positional argument: 'positional'"
]
}
],
"source": [
"print_args2()"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"ename": "TypeError",
"evalue": "print_args2() missing 1 required keyword-only argument: 'keyword'",
"output_type": "error",
"traceback": [
"\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
"\u001b[0;31mTypeError\u001b[0m Traceback (most recent call last)",
"Cell \u001b[0;32mIn[14], line 1\u001b[0m\n\u001b[0;32m----> 1\u001b[0m \u001b[43mprint_args2\u001b[49m\u001b[43m(\u001b[49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[38;5;124;43mp\u001b[39;49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[43m)\u001b[49m\n",
"\u001b[0;31mTypeError\u001b[0m: print_args2() missing 1 required keyword-only argument: 'keyword'"
]
}
],
"source": [
"print_args2(\"p\")"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"required positional p\n",
"required keyword k\n",
"default keyword True\n"
]
}
],
"source": [
"print_args2(\"p\", keyword=\"k\")"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"required positional p\n",
"required keyword k\n",
"default keyword False\n"
]
}
],
"source": [
"print_args2(\"p\", keyword=\"k\", default=False)"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"required positional p\n",
"optional positional 0 x\n",
"optional positional 1 y\n",
"required keyword k\n",
"default keyword True\n",
"optional keyword flag True\n"
]
}
],
"source": [
"print_args2(\"p\", \"x\", \"y\", keyword=\"k\", flag=True)"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"required positional p\n",
"optional positional 0 x\n",
"optional positional 1 y\n",
"required keyword k\n",
"default keyword False\n",
"optional keyword flag True\n"
]
}
],
"source": [
"print_args2(\"p\", \"x\", \"y\", keyword=\"k\", default=False, flag=True)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"As above, we may unpack `list` or `dict` objects in a function call."
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [],
"source": [
"positionals = [\"x\", \"y\", \"z\"]"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"required positional p\n",
"optional positional 0 x\n",
"optional positional 1 y\n",
"optional positional 2 z\n",
"required keyword k\n",
"default keyword False\n",
"optional keyword flag True\n",
"optional keyword another_flag False\n"
]
}
],
"source": [
"print_args2(\"p\", *positionals, keyword=\"k\", default=False, **flags)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Memoization"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"### \"Easy at first Glance\" Example: [Fibonacci Numbers <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_wiki.png\">](https://en.wikipedia.org/wiki/Fibonacci_number) (repeated)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"The *recursive* implementation of the [Fibonacci numbers <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_wiki.png\">](https://en.wikipedia.org/wiki/Fibonacci_number) in [Chapter 4 <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_nb.png\">](https://nbviewer.jupyter.org/github/webartifex/intro-to-python/blob/develop/04_iteration/00_content.ipynb#\"Easy-at-first-Glance\"-Example:-Fibonacci-Numbers) takes long to compute for large Fibonacci numbers. For easier comparison, we show the old `fibonacci()` version here again."
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [],
"source": [
"def fibonacci(i):\n",
" \"\"\"Calculate the ith Fibonacci number.\n",
"\n",
" Args:\n",
" i (int): index of the Fibonacci number to calculate\n",
"\n",
" Returns:\n",
" ith_fibonacci (int)\n",
" \"\"\"\n",
" if i == 0:\n",
" return 0\n",
" elif i == 1:\n",
" return 1\n",
" return fibonacci(i - 1) + fibonacci(i - 2)"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"144"
]
},
"execution_count": 22,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"fibonacci(12)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"#### Efficiency of Algorithms"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"Timing the code cells below with the `%%timeit` magic shows how doubling the input (i.e., `12` becomes `24`) more than doubles how long it takes `fibonacci()` to calculate the solution. This is actually an understatement as we see the time go up by roughly a factor of $1000$ (i.e., from nano-seconds to milli-seconds). That is an example of **exponential growth**."
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"40.1 µs ± 1.26 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
]
}
],
"source": [
"%%timeit -n 100\n",
"fibonacci(12)"
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"12.1 ms ± 149 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
]
}
],
"source": [
"%%timeit -n 100\n",
"fibonacci(24)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"The computation graph below visualizes what the problem is and also suggests a solution: In the recursive implementation, the same function calls are made over and over again. For example, in the visualization the call `fibonacci(3)`, shown as $F(3)$, is made *twice* when the actual goal is to calculate `fibonacci(5)`, shown as $F(5)$. This problem \"grows\" if the initial argument (i.e., `5` in the example) is chosen to be larger as we see with the many `fibonacci(2)`, `fibonacci(1)` and `fibonacci(0)` calls.\n",
"\n",
"Instead of calculating the return value of the `fibonacci()` function for the *same* argument over and over again, it makes sense to **cache** (i.e., \"store\") the result and reuse it. This concept is called **[memoization <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_wiki.png\">](https://en.wikipedia.org/wiki/Memoization)**."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"<img src=\"static/fibonacci_call_graph.png\" width=\"50%\" align=\"left\">"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"### \"Easy at second Glance\" Example: [Fibonacci Numbers <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_wiki.png\">](https://en.wikipedia.org/wiki/Fibonacci_number) (revisited)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"Below is a revision of the recursive `fibonacci()` implementation that uses a **globally** defined `dict` object, called `memo`, to store intermediate results and look them up.\n",
"\n",
"To be precise, the the revised `fibonacci()` first checks if the `i`th Fibonacci number has already been calculated before. If yes, it is in the `memo`. That number is then returned immediately *without* any more calculations. As `dict` objects are *optimized* for constant-time key look-ups, this takes essentially \"no\" time! With a `list` object, for example, the `in` operator would trigger a linear search, which takes longer the more elements are in the list. If the `i`th Fibonacci number has not been calculated before, there is no corresponding item in the `memo` and a recursive function call must be made. The result obtained by recursion is then inserted into the `memo`."
]
},
{
"cell_type": "code",
"execution_count": 25,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [],
"source": [
"memo = {\n",
" 0: 0,\n",
" 1: 1,\n",
"}"
]
},
{
"cell_type": "code",
"execution_count": 26,
"metadata": {
"code_folding": [],
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [],
"source": [
"def fibonacci(i, *, debug=False):\n",
" \"\"\"Calculate the ith Fibonacci number.\n",
"\n",
" Args:\n",
" i (int): index of the Fibonacci number to calculate\n",
" debug (bool): show non-cached calls; defaults to False\n",
"\n",
" Returns:\n",
" ith_fibonacci (int)\n",
" \"\"\"\n",
" if i in memo:\n",
" return memo[i]\n",
"\n",
" if debug: # added for didactical purposes\n",
" print(f\"fibonacci({i}) is calculated\")\n",
"\n",
" recurse = fibonacci(i - 1, debug=debug) + fibonacci(i - 2, debug=debug)\n",
" memo[i] = recurse\n",
" return recurse"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"When we follow the flow of execution closely, we realize that the intermediate results represented by the left-most path in the graph above are calculated first. `fibonacci(1)`, the left-most leaf node $F(1)$, is the first base case reached, followed immediately by `fibonacci(0)`. From that moment onwards, the flow of execution moves back up the left-most path while adding together the two corresponding child nodes. Effectively, this mirrors the *iterative* implementation in that the order of all computational steps are *identical* (cf., the \"*Hard at first Glance*\" example in [Chapter 4 <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_nb.png\">](https://nbviewer.jupyter.org/github/webartifex/intro-to-python/blob/develop/04_iteration/02_content.ipynb#\"Hard-at-first-Glance\"-Example:-Fibonacci-Numbers--(revisited))).\n",
"\n",
"We added a keyword-only argument `debug` that allows the caller to print out a message every time a `i` was *not* in the `memo`."
]
},
{
"cell_type": "code",
"execution_count": 27,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"fibonacci(12) is calculated\n",
"fibonacci(11) is calculated\n",
"fibonacci(10) is calculated\n",
"fibonacci(9) is calculated\n",
"fibonacci(8) is calculated\n",
"fibonacci(7) is calculated\n",
"fibonacci(6) is calculated\n",
"fibonacci(5) is calculated\n",
"fibonacci(4) is calculated\n",
"fibonacci(3) is calculated\n",
"fibonacci(2) is calculated\n"
]
},
{
"data": {
"text/plain": [
"144"
]
},
"execution_count": 27,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"fibonacci(12, debug=True)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"Now, calling `fibonacci()` has the *side effect* of growing the `memo` in the *global scope*. So, subsequent calls to `fibonacci()` need not calculate any Fibonacci number with an index `i` smaller than the maximum `i` used so far. Because of that, this `fibonacci()` is *not* a *pure* function."
]
},
{
"cell_type": "code",
"execution_count": 28,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"data": {
"text/plain": [
"144"
]
},
"execution_count": 28,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"fibonacci(12, debug=True) # no more recursive calls needed"
]
},
{
"cell_type": "code",
"execution_count": 29,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"{0: 0,\n",
" 1: 1,\n",
" 2: 1,\n",
" 3: 2,\n",
" 4: 3,\n",
" 5: 5,\n",
" 6: 8,\n",
" 7: 13,\n",
" 8: 21,\n",
" 9: 34,\n",
" 10: 55,\n",
" 11: 89,\n",
" 12: 144}"
]
},
"execution_count": 29,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"memo"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"#### Efficiency of Algorithms (continued)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"With memoization, the recursive `fibonacci()` implementation is as fast as its iterative counterpart, even for large numbers.\n",
"\n",
"The `%%timeit` magic, by default, runs a code cell seven times. Whereas in the first run, *new* Fibonacci numbers (i.e., intermediate results) are added to the `memo`, `fibonacci()` has no work to do in the subsequent six runs. `%%timeit` realizes this and tells us that \"an intermediate result is being cached.\""
]
},
{
"cell_type": "code",
"execution_count": 30,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"The slowest run took 252.65 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
"6.68 µs ± 15.8 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
]
}
],
"source": [
"%%timeit -n 1\n",
"fibonacci(99)"
]
},
{
"cell_type": "code",
"execution_count": 31,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"The slowest run took 3603.20 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
"85.1 µs ± 208 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
]
}
],
"source": [
"%%timeit -n 1\n",
"fibonacci(999)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"The iterative implementation still has an advantage as the `RecursionError` shows for larger `i`."
]
},
{
"cell_type": "code",
"execution_count": 32,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"ename": "RecursionError",
"evalue": "maximum recursion depth exceeded",
"output_type": "error",
"traceback": [
"\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
"\u001b[0;31mRecursionError\u001b[0m Traceback (most recent call last)",
"Cell \u001b[0;32mIn[32], line 1\u001b[0m\n\u001b[0;32m----> 1\u001b[0m \u001b[43mget_ipython\u001b[49m\u001b[43m(\u001b[49m\u001b[43m)\u001b[49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43mrun_cell_magic\u001b[49m\u001b[43m(\u001b[49m\u001b[38;5;124;43m'\u001b[39;49m\u001b[38;5;124;43mtimeit\u001b[39;49m\u001b[38;5;124;43m'\u001b[39;49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[38;5;124;43m'\u001b[39;49m\u001b[38;5;124;43m-n 1\u001b[39;49m\u001b[38;5;124;43m'\u001b[39;49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[38;5;124;43m'\u001b[39;49m\u001b[38;5;124;43mfibonacci(9999)\u001b[39;49m\u001b[38;5;130;43;01m\\n\u001b[39;49;00m\u001b[38;5;124;43m'\u001b[39;49m\u001b[43m)\u001b[49m\n",
"File \u001b[0;32m~/Repositories/intro-to-python/.venv/lib/python3.12/site-packages/IPython/core/interactiveshell.py:2541\u001b[0m, in \u001b[0;36mInteractiveShell.run_cell_magic\u001b[0;34m(self, magic_name, line, cell)\u001b[0m\n\u001b[1;32m 2539\u001b[0m \u001b[38;5;28;01mwith\u001b[39;00m \u001b[38;5;28mself\u001b[39m\u001b[38;5;241m.\u001b[39mbuiltin_trap:\n\u001b[1;32m 2540\u001b[0m args \u001b[38;5;241m=\u001b[39m (magic_arg_s, cell)\n\u001b[0;32m-> 2541\u001b[0m result \u001b[38;5;241m=\u001b[39m \u001b[43mfn\u001b[49m\u001b[43m(\u001b[49m\u001b[38;5;241;43m*\u001b[39;49m\u001b[43margs\u001b[49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[38;5;241;43m*\u001b[39;49m\u001b[38;5;241;43m*\u001b[39;49m\u001b[43mkwargs\u001b[49m\u001b[43m)\u001b[49m\n\u001b[1;32m 2543\u001b[0m \u001b[38;5;66;03m# The code below prevents the output from being displayed\u001b[39;00m\n\u001b[1;32m 2544\u001b[0m \u001b[38;5;66;03m# when using magics with decorator @output_can_be_silenced\u001b[39;00m\n\u001b[1;32m 2545\u001b[0m \u001b[38;5;66;03m# when the last Python token in the expression is a ';'.\u001b[39;00m\n\u001b[1;32m 2546\u001b[0m \u001b[38;5;28;01mif\u001b[39;00m \u001b[38;5;28mgetattr\u001b[39m(fn, magic\u001b[38;5;241m.\u001b[39mMAGIC_OUTPUT_CAN_BE_SILENCED, \u001b[38;5;28;01mFalse\u001b[39;00m):\n",
"File \u001b[0;32m~/Repositories/intro-to-python/.venv/lib/python3.12/site-packages/IPython/core/magics/execution.py:1189\u001b[0m, in \u001b[0;36mExecutionMagics.timeit\u001b[0;34m(self, line, cell, local_ns)\u001b[0m\n\u001b[1;32m 1186\u001b[0m \u001b[38;5;28;01mif\u001b[39;00m time_number \u001b[38;5;241m>\u001b[39m\u001b[38;5;241m=\u001b[39m \u001b[38;5;241m0.2\u001b[39m:\n\u001b[1;32m 1187\u001b[0m \u001b[38;5;28;01mbreak\u001b[39;00m\n\u001b[0;32m-> 1189\u001b[0m all_runs \u001b[38;5;241m=\u001b[39m \u001b[43mtimer\u001b[49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43mrepeat\u001b[49m\u001b[43m(\u001b[49m\u001b[43mrepeat\u001b[49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[43mnumber\u001b[49m\u001b[43m)\u001b[49m\n\u001b[1;32m 1190\u001b[0m best \u001b[38;5;241m=\u001b[39m \u001b[38;5;28mmin\u001b[39m(all_runs) \u001b[38;5;241m/\u001b[39m number\n\u001b[1;32m 1191\u001b[0m worst \u001b[38;5;241m=\u001b[39m \u001b[38;5;28mmax\u001b[39m(all_runs) \u001b[38;5;241m/\u001b[39m number\n",
"File \u001b[0;32m/usr/lib64/python3.12/timeit.py:208\u001b[0m, in \u001b[0;36mTimer.repeat\u001b[0;34m(self, repeat, number)\u001b[0m\n\u001b[1;32m 206\u001b[0m r \u001b[38;5;241m=\u001b[39m []\n\u001b[1;32m 207\u001b[0m \u001b[38;5;28;01mfor\u001b[39;00m i \u001b[38;5;129;01min\u001b[39;00m \u001b[38;5;28mrange\u001b[39m(repeat):\n\u001b[0;32m--> 208\u001b[0m t \u001b[38;5;241m=\u001b[39m \u001b[38;5;28;43mself\u001b[39;49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43mtimeit\u001b[49m\u001b[43m(\u001b[49m\u001b[43mnumber\u001b[49m\u001b[43m)\u001b[49m\n\u001b[1;32m 209\u001b[0m r\u001b[38;5;241m.\u001b[39mappend(t)\n\u001b[1;32m 210\u001b[0m \u001b[38;5;28;01mreturn\u001b[39;00m r\n",
"File \u001b[0;32m~/Repositories/intro-to-python/.venv/lib/python3.12/site-packages/IPython/core/magics/execution.py:173\u001b[0m, in \u001b[0;36mTimer.timeit\u001b[0;34m(self, number)\u001b[0m\n\u001b[1;32m 171\u001b[0m gc\u001b[38;5;241m.\u001b[39mdisable()\n\u001b[1;32m 172\u001b[0m \u001b[38;5;28;01mtry\u001b[39;00m:\n\u001b[0;32m--> 173\u001b[0m timing \u001b[38;5;241m=\u001b[39m \u001b[38;5;28;43mself\u001b[39;49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43minner\u001b[49m\u001b[43m(\u001b[49m\u001b[43mit\u001b[49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[38;5;28;43mself\u001b[39;49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43mtimer\u001b[49m\u001b[43m)\u001b[49m\n\u001b[1;32m 174\u001b[0m \u001b[38;5;28;01mfinally\u001b[39;00m:\n\u001b[1;32m 175\u001b[0m \u001b[38;5;28;01mif\u001b[39;00m gcold:\n",
"File \u001b[0;32m<magic-timeit>:1\u001b[0m, in \u001b[0;36minner\u001b[0;34m(_it, _timer)\u001b[0m\n",
"Cell \u001b[0;32mIn[26], line 17\u001b[0m, in \u001b[0;36mfibonacci\u001b[0;34m(i, debug)\u001b[0m\n\u001b[1;32m 14\u001b[0m \u001b[38;5;28;01mif\u001b[39;00m debug: \u001b[38;5;66;03m# added for didactical purposes\u001b[39;00m\n\u001b[1;32m 15\u001b[0m \u001b[38;5;28mprint\u001b[39m(\u001b[38;5;124mf\u001b[39m\u001b[38;5;124m\"\u001b[39m\u001b[38;5;124mfibonacci(\u001b[39m\u001b[38;5;132;01m{\u001b[39;00mi\u001b[38;5;132;01m}\u001b[39;00m\u001b[38;5;124m) is calculated\u001b[39m\u001b[38;5;124m\"\u001b[39m)\n\u001b[0;32m---> 17\u001b[0m recurse \u001b[38;5;241m=\u001b[39m \u001b[43mfibonacci\u001b[49m\u001b[43m(\u001b[49m\u001b[43mi\u001b[49m\u001b[43m \u001b[49m\u001b[38;5;241;43m-\u001b[39;49m\u001b[43m \u001b[49m\u001b[38;5;241;43m1\u001b[39;49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[43mdebug\u001b[49m\u001b[38;5;241;43m=\u001b[39;49m\u001b[43mdebug\u001b[49m\u001b[43m)\u001b[49m \u001b[38;5;241m+\u001b[39m fibonacci(i \u001b[38;5;241m-\u001b[39m \u001b[38;5;241m2\u001b[39m, debug\u001b[38;5;241m=\u001b[39mdebug)\n\u001b[1;32m 18\u001b[0m memo[i] \u001b[38;5;241m=\u001b[39m recurse\n\u001b[1;32m 19\u001b[0m \u001b[38;5;28;01mreturn\u001b[39;00m recurse\n",
"Cell \u001b[0;32mIn[26], line 17\u001b[0m, in \u001b[0;36mfibonacci\u001b[0;34m(i, debug)\u001b[0m\n\u001b[1;32m 14\u001b[0m \u001b[38;5;28;01mif\u001b[39;00m debug: \u001b[38;5;66;03m# added for didactical purposes\u001b[39;00m\n\u001b[1;32m 15\u001b[0m \u001b[38;5;28mprint\u001b[39m(\u001b[38;5;124mf\u001b[39m\u001b[38;5;124m\"\u001b[39m\u001b[38;5;124mfibonacci(\u001b[39m\u001b[38;5;132;01m{\u001b[39;00mi\u001b[38;5;132;01m}\u001b[39;00m\u001b[38;5;124m) is calculated\u001b[39m\u001b[38;5;124m\"\u001b[39m)\n\u001b[0;32m---> 17\u001b[0m recurse \u001b[38;5;241m=\u001b[39m \u001b[43mfibonacci\u001b[49m\u001b[43m(\u001b[49m\u001b[43mi\u001b[49m\u001b[43m \u001b[49m\u001b[38;5;241;43m-\u001b[39;49m\u001b[43m \u001b[49m\u001b[38;5;241;43m1\u001b[39;49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[43mdebug\u001b[49m\u001b[38;5;241;43m=\u001b[39;49m\u001b[43mdebug\u001b[49m\u001b[43m)\u001b[49m \u001b[38;5;241m+\u001b[39m fibonacci(i \u001b[38;5;241m-\u001b[39m \u001b[38;5;241m2\u001b[39m, debug\u001b[38;5;241m=\u001b[39mdebug)\n\u001b[1;32m 18\u001b[0m memo[i] \u001b[38;5;241m=\u001b[39m recurse\n\u001b[1;32m 19\u001b[0m \u001b[38;5;28;01mreturn\u001b[39;00m recurse\n",
" \u001b[0;31m[... skipping similar frames: fibonacci at line 17 (2969 times)]\u001b[0m\n",
"Cell \u001b[0;32mIn[26], line 17\u001b[0m, in \u001b[0;36mfibonacci\u001b[0;34m(i, debug)\u001b[0m\n\u001b[1;32m 14\u001b[0m \u001b[38;5;28;01mif\u001b[39;00m debug: \u001b[38;5;66;03m# added for didactical purposes\u001b[39;00m\n\u001b[1;32m 15\u001b[0m \u001b[38;5;28mprint\u001b[39m(\u001b[38;5;124mf\u001b[39m\u001b[38;5;124m\"\u001b[39m\u001b[38;5;124mfibonacci(\u001b[39m\u001b[38;5;132;01m{\u001b[39;00mi\u001b[38;5;132;01m}\u001b[39;00m\u001b[38;5;124m) is calculated\u001b[39m\u001b[38;5;124m\"\u001b[39m)\n\u001b[0;32m---> 17\u001b[0m recurse \u001b[38;5;241m=\u001b[39m \u001b[43mfibonacci\u001b[49m\u001b[43m(\u001b[49m\u001b[43mi\u001b[49m\u001b[43m \u001b[49m\u001b[38;5;241;43m-\u001b[39;49m\u001b[43m \u001b[49m\u001b[38;5;241;43m1\u001b[39;49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[43mdebug\u001b[49m\u001b[38;5;241;43m=\u001b[39;49m\u001b[43mdebug\u001b[49m\u001b[43m)\u001b[49m \u001b[38;5;241m+\u001b[39m fibonacci(i \u001b[38;5;241m-\u001b[39m \u001b[38;5;241m2\u001b[39m, debug\u001b[38;5;241m=\u001b[39mdebug)\n\u001b[1;32m 18\u001b[0m memo[i] \u001b[38;5;241m=\u001b[39m recurse\n\u001b[1;32m 19\u001b[0m \u001b[38;5;28;01mreturn\u001b[39;00m recurse\n",
"\u001b[0;31mRecursionError\u001b[0m: maximum recursion depth exceeded"
]
}
],
"source": [
"%%timeit -n 1\n",
"fibonacci(9999)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"This exception occurs as Python must keep track of *every* function call *until* it has returned, and with large enough `i`, the recursion tree above grows too big. By default, Python has a limit of up to 3000 *simultaneous* function calls. So, theoretically this exception is not a bug in the narrow sense but the result of a \"security\" measure that is supposed to keep a computer from crashing. However, practically most high-level languages like Python incur such an overhead cost: It results from the fact that someone (i.e., Python) needs to manage each function call's *local scope*. With the `for`-loop in the iterative version, we do this managing as the programmer.\n",
"\n",
"We could \"hack\" a bit with Python's default configuration using the [sys <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_py.png\">](https://docs.python.org/3/library/sys.html) module in the [standard library <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_py.png\">](https://docs.python.org/3/library/index.html) and make it work. As we are good citizens, we reset everything to the defaults after our hack is completed."
]
},
{
"cell_type": "code",
"execution_count": 33,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [],
"source": [
"import sys"
]
},
{
"cell_type": "code",
"execution_count": 34,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [],
"source": [
"old_recursion_limit = sys.getrecursionlimit()"
]
},
{
"cell_type": "code",
"execution_count": 35,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"data": {
"text/plain": [
"3000"
]
},
"execution_count": 35,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"old_recursion_limit"
]
},
{
"cell_type": "code",
"execution_count": 36,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [],
"source": [
"sys.setrecursionlimit(99999)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"Computational speed is *not* the problem here."
]
},
{
"cell_type": "code",
"execution_count": 37,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"The slowest run took 50532.39 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
"1.21 ms ± 2.97 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
]
}
],
"source": [
"%%timeit -n 1\n",
"fibonacci(9999)"
]
},
{
"cell_type": "code",
"execution_count": 38,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [],
"source": [
"sys.setrecursionlimit(old_recursion_limit)"
]
}
],
"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.12.2"
},
"livereveal": {
"auto_select": "code",
"auto_select_fragment": true,
"scroll": true,
"theme": "serif"
},
"toc": {
"base_numbering": 1,
"nav_menu": {},
"number_sections": false,
"sideBar": true,
"skip_h1_title": true,
"title_cell": "Table of Contents",
"title_sidebar": "Contents",
"toc_cell": false,
"toc_position": {
"height": "calc(100% - 180px)",
"left": "10px",
"top": "150px",
"width": "384px"
},
"toc_section_display": false,
"toc_window_display": false
}
},
"nbformat": 4,
"nbformat_minor": 4
}