11-dictionaries.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "8z5cONg8rUrX",
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Dictionaries\n",
    "\n",
    "## Programming Fundamentals (NB11)\n",
    "\n",
    "### MIEIC/2020-21\n",
    "\n",
    "#### João Correia Lopes\n",
    "\n",
    "FEUP/DEI and INESC TEC"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "MZzE7pYorju5",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## Goals\n",
    "\n",
    "By the end of this class, the student should be able to:\n",
    "\n",
    "- Use the main operations and methods available to work with dictionaries\n",
    "- Describe the differences between dictionary aliasing and shallow copying\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "eR5Lh1jNroE2",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## Bibliography\n",
    "\n",
    "- Peter Wentworth, Jeffrey Elkner, Allen B. Downey, and Chris Meyers, *How to Think Like a Computer Scientist — Learning with Python 3* (Section 5.4)\n",
    "\n",
    "- Brad Miller and David Ranum, Learning with Python: Interactive Edition. Based on material by Jeffrey Elkner, Allen B. Downey, and Chris Meyers (Chapter 12)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "QiR_tOOIkpCT",
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Data type: Dictionaries"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "aO_WjhJaOLx7",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### A compound data type (recap)\n",
    "\n",
    "- So far we have seen built-in types like `int`, `float`, `bool`,\n",
    "    `str` and also lists, pairs or tuples\n",
    "\n",
    "- Strings, lists, and tuples are qualitatively different from the\n",
    "    others because they are made up of smaller pieces\n",
    "\n",
    "- Lists, tuples, and strings have been called *sequences*, because\n",
    "    their items occur in order\n",
    "\n",
    "- All of those use integers as indices to access the values they contain within them"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "zfj2mfLsOhTR",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Dictionary\n",
    "\n",
    "- Dictionaries are yet another kind of compound type\n",
    "\n",
    "- They are Python’s built-in **mapping type**\n",
    "\n",
    "- They map **keys**, which can be any *immutable type*, to **values**,\n",
    "    which can be any type (heterogeneous)<sup>1</sup> \n",
    "\n",
    "- In other languages, they are called *associative arrays* since they\n",
    "    associate a key with a value\n",
    "\n",
    "- One way to create a dictionary is to start with the empty dictionary\n",
    "    and add **key:value** pairs\n",
    "\n",
    "```\n",
    "    >>> english_spanish = {}\n",
    "    >>> english_spanish['one'] = \"uno\"\n",
    "    >>> english_spanish[\"two\"] = 'dos'\n",
    "    >>> print(english_spanish)\n",
    "    {'one': 'uno', 'two': 'dos'}\n",
    "```\n",
    "\n",
    "<sup>1</sup> \n",
    "Just like the elements of a list or tuple"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Let's try it here:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "RRoPs7gqd6kX",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "english_portuguese = {}\n",
    "print(english_portuguese)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "FDRdv2GleX41",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "english_portuguese['one'] = \"um\"\n",
    "english_portuguese[\"two\"] = 'dois'\n",
    "print(english_portuguese)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "NSZliOG-O8ai",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Hashing\n",
    "\n",
    "- Python uses complex algorithms, designed for very fast access, to\n",
    "    determine where the **key:value** pairs are stored in a dictionary\n",
    "\n",
    "- The implementation uses a technique called **hashing**\n",
    "[[wiki]](https://en.wikipedia.org/wiki/Hash_function)\n",
    "\n",
    "- For 3.7 onwards, the order of the pairs *key:value* follows the insertion order\n",
    "\n",
    "- The same concept of mapping a key to a value could be implemented\n",
    "    using a list of tuples...\n",
    "\n",
    "```\n",
    "  >>> {\"apples\": 430, \"bananas\": 312, \"oranges\": 525, \"pears\": 217}\n",
    "  {'apples': 430, 'bananas': 312, 'oranges': 525, 'pears': 217}\n",
    "\n",
    "  >>> [(\"apples\", 430), (\"bananas\", 312), (\"oranges\", 525), (\"pears\", 217)]\n",
    "  [('apples', 430), ('bananas', 312), ('oranges', 525), ('pears', 217)]\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "00iUd9pZPkKm",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Efficiency\n",
    "\n",
    "- The reason to choose this new data type is because dictionaries are **very fast**\n",
    "- Hashing allows us to access a value very quickly\n",
    "- By contrast, the list of tuples implementation is slow\n",
    "  - If we wanted to find a value associated with a key, we would have to iterate over every tuple, checking the 0th element\n",
    "  - What if the key wasn’t even in the list? \n",
    "  - We would have to get to the end of it to find out"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "5bnZHXFpQnIp",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Look up a value (in a dictionary)\n",
    "\n",
    "![mafalda](images/11/mafalda.png)\n",
    "\n",
    "$\\Rightarrow$\n",
    "<https://en.wikipedia.org/wiki/Mafalda>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "ZSZ2BBa8QtGZ",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Look up a value\n",
    "\n",
    "- Another way to create a dictionary is to provide a list of\n",
    "    **key:value** pairs using the same syntax as the previous output\n",
    "\n",
    "- It doesn’t matter what order we write the pairs (there’s no\n",
    "    indexing!)<sup>2</sup> \n",
    "\n",
    "```\n",
    "  >>> english_spanish = {\"one\": \"uno\", \"three\": \"tres\", \"two\": \"dos\"}\n",
    "  >>> english_spanish\n",
    "  {'one': 'uno', 'three': 'tres', 'two': 'dos'}\n",
    "\n",
    "  >>> print(english_spanish[\"two\"])\n",
    "  dos\n",
    "```\n",
    "\n",
    "<sup>2</sup> \n",
    "The dictionary is the first compound type that we’ve seen that is\n",
    "    not a sequence, so we can’t index or slice a dictionary"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "Z0RX9-eSemsQ",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "english_portuguese = {\"one\": \"um\", \"three\": \"tres\", \"two\": \"dois\"}\n",
    "print(english_portuguese[\"three\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "xHNuGoUzQ-34",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## 5.4.1 Dictionary operations\n",
    "\n",
    "- The `del` statement removes a *key:value* pair from a dictionary\n",
    "\n",
    "- The `len` function also works on dictionaries; it returns the number\n",
    "    of *key:value* pairs\n",
    "\n",
    "```\n",
    "   >>> inventory = {\"apples\": 430, \"bananas\": 312, \"quinces\": 217}\n",
    "   >>> del inventory[\"bananas\"]\n",
    "   >>> len(inventory)\n",
    "```\n",
    "\n",
    "$\\Rightarrow$\n",
    "<https://github.com/fpro-feup/public/tree/master/lectures/11/operations.py>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "yUBrHCvie6AT",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Watch for some operations:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "lnsa3wZVexsP",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "inventory = {\"apples\": 430, \"bananas\": 312, \"oranges\": 525, \"pears\": 217}\n",
    "print(inventory)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "8-czAIwIe4yf",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "del inventory[\"pears\"]\n",
    "print(inventory)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "_a-jrdPtfC5b",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "inventory[\"bananas\"] = 0\n",
    "print(inventory)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "qiSDuYBLfFfG",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "inventory[\"bananas\"] += 200\n",
    "print(inventory)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "F-raMYM8Rh_6",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## 5.4.2  Dictionary methods\n",
    "\n",
    "- Dictionaries have a number of useful built-in methods\n",
    "\n",
    "- The `keys()` method returns what Python3 calls a *view* of its\n",
    "    underlying keys\n",
    "\n",
    "    - A *view* object has some similarities to the *range* object we saw\n",
    "        earlier — it is a **lazy promise**, to deliver its elements when\n",
    "        they’re needed by the rest of the program\n",
    "\n",
    "    - We can *iterate over the view*, or turn the view into a list\n",
    "\n",
    "- The `values()` method is similar\n",
    "\n",
    "- The `items()` method also returns a *view*, which *promises* a list of\n",
    "    tuples\n",
    "\n",
    "```\n",
    "  for key in english_spanish.keys():\n",
    "      print(\"Got key\", key, \"which maps to value\", english_spanish[key])\n",
    "```\n",
    "\n",
    "$\\Rightarrow$\n",
    "<https://github.com/fpro-feup/public/tree/master/lectures/11/methods.py>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "l5T2FzlhgJhs",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Use `keys()`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "F8FQ-dqrfaa4",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "english_portuguese = {\"one\": \"um\", \"two\": \"dois\", \"three\": \"tres\"}\n",
    "\n",
    "for key in english_portuguese.keys():\n",
    "    print(\"Got key\", key, \"which maps to value\", english_portuguese[key])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "SdtZAuBYgTyP",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "keys = list(english_portuguese.keys())\n",
    "print(keys)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "egKfxKr4gaM9",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Iterating over a dictionary implicitly iterates over its keys:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "weaK1-z3gYlP",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "for key in english_portuguese:\n",
    "    print(\"Got key\", key)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "OgLTWbW4gh7D",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Use `values()`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "l1k645i0gq9f",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "values = list(english_portuguese.values())\n",
    "print(values)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "rnP7plTigwVR",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Use `items()`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "PMNGse1IhNNI",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "print(list(english_portuguese.items()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "59GraRivhQJU",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "for (key, value) in english_portuguese.items():\n",
    "    print(\"Got key\", key, \"which maps to value\", value)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "jhkeGyj0hbeb",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "What about membership?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "3LEUWYeMhXYZ",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "print(\"one\" in english_portuguese)\n",
    "print(\"six\" in english_portuguese)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "xQ0n06S2hk5l",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Note that `in` tests *keys*, not *values*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "EVgZvFWthjK_",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "print(\"tres\" in english_portuguese)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "Yb04Wtj-hqai",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "What's the result of looking up a non-existent key in a dictionary?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "UHmYTQnmhvJc",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "print(english_portuguese[\"dog\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "So, you better be sure before doing it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "if \"three\" in english_portuguese:\n",
    "    print(english_portuguese[\"three\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "aVrq-lh_SHiO",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## 5.4.3 Aliasing and copying\n",
    "\n",
    "- As in the case of lists, because **dictionaries are mutable**, we\n",
    "    need to be aware of *aliasing*\n",
    "\n",
    "- Whenever two variables refer to the same object, changes to one\n",
    "    affect the other\n",
    "\n",
    "- To modify a dictionary and keep a copy of the original,\n",
    "    use the `copy()` method\n",
    "\n",
    "```\n",
    "  >>> opposites = {\"up\": \"down\", \"right\": \"wrong\", \"yes\": \"no\"}\n",
    "  >>> alias = opposites\n",
    "  >>> copy = opposites.copy()  # Shallow copy\n",
    "```\n",
    "\n",
    "- A *shallow copy* constructs a new compound object and then (to the extent possible) inserts references into it to the objects found in the original\n",
    "\n",
    "$\\Rightarrow$\n",
    "<https://github.com/fpro-feup/public/tree/master/lectures/11/aliases.py>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "BDc6KcBEiLOt",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Those are aliases:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "xzVNr7OFiD5L",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "opposites = {\"up\": \"down\", \"right\": \"wrong\", \"yes\": \"no\"}\n",
    "\n",
    "alias = opposites"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "hxZRZsrXiase",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "But this is a shallow copy:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "lyj1hBHdiYec",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "copy = opposites.copy()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "fece1unjiVHj",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "What now?\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "xyswZ4FSiij5",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "alias[\"right\"] = \"left\"\n",
    "print(opposites[\"right\"])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "LlQ-4gTGij2t",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "copy[\"right\"] = \"Guiness\"\n",
    "print(opposites[\"right\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "ttztXYUtqYr1",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## 5.4.4 Counting letters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "0KBjCaYbSp0R",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Generate a Frequency Table\n",
    "\n",
    "- To write a function that counted the number of occurrences of a\n",
    "    letter in a string\n",
    "\n",
    "- Dictionaries provide an elegant way to generate a frequency table\n",
    "\n",
    "- An algorithm:\n",
    "\n",
    "```\n",
    "     start with an empty dictionary\n",
    "     for each letter in the string:\n",
    "        find the current count (possibly zero) and increment it\n",
    "     the dictionary contains pairs of letters and their frequencies \n",
    "```\n",
    "\n",
    "$\\Rightarrow$\n",
    "<https://github.com/fpro-feup/public/tree/master/lectures/11/frequency-table.py>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "UuW7MrqSi-s0",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Consider the text:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "BOUaCS4KjAVI",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "s = \"\"\" \n",
    "This parrot is no more! It has ceased to be! \n",
    "It’s expired and gone to meet its maker! \n",
    "This is a late parrot! It’s a stiff! \n",
    "Bereft of life, it rests in peace! \n",
    "If you hadn’t nailed it to the perch, it would be pushing up the daisies! \n",
    "It’s run down the curtain and joined the choir invisible! \n",
    "This is an ex-parrot!\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "mIn1VbzjkBjZ",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Let's count the letters of the text (any idea where it came from?)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "mERpKMTjkEZo",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "letter_counts = {}\n",
    "for letter in s:\n",
    "    letter_counts[letter] = letter_counts.get(letter, 0) + 1 \n",
    "print(letter_counts)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "HuxSv0blS2Hx",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## Sparse matrices\n",
    "\n",
    "- We previously used a list of lists to represent a matrix\n",
    "\n",
    "- That is a good choice for a matrix with mostly nonzero values, but\n",
    "    consider a sparse matrix like this one:\n",
    "\n",
    "$$\\left[\n",
    "    \\begin{array}{ccccc}\n",
    "    0 & 0 & 0 & 1 & 0 \\\\\n",
    "    0 & 0 & 0 & 0 & 0 \\\\\n",
    "    0 & 2 & 0 & 0 & 0 \\\\\n",
    "    0 & 0 & 0 & 0 & 0 \\\\\n",
    "    0 & 0 & 0 & 3 & 0 \\\\\n",
    "    \\end{array}\n",
    "  \\right]$$\n",
    "\n",
    "- The list representation contains a lot of zeroes\n",
    "\n",
    "- An alternative is to use a dictionary and the `get()` method (as you'll see next)\n",
    "\n",
    "- Beware that there’s a trade-off here, as the access may take more time\n",
    "\n",
    "$\\Rightarrow$\n",
    "<https://github.com/fpro-feup/public/tree/master/lectures/11/matrix.py>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "gSxSJPgglUU3",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "The sparse matrix as a list:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "Df3wrni1lX89",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "matrix = [[0, 0, 0, 1, 0],\n",
    "          [0, 0, 0, 0, 0],\n",
    "          [0, 2, 0, 0, 0],\n",
    "          [0, 0, 0, 0, 0],\n",
    "          [0, 0, 0, 3, 0]]\n",
    "\n",
    "print(matrix)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "g_FhYjI9lbqb",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "The sparse matrix as a dictionary:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "41CogqNVle5j",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "# For the keys, we can use tuples that contain the row and column numbers\n",
    "matrix = {(0, 3): 1, (2, 1): 2, (4, 3): 3}\n",
    "\n",
    "print(matrix)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "niJbaznwlpff",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Accessing matrix elements:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "fFg6anGIluXb",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "print(matrix[(0, 3)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "jooz24CKlw2j",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "What happens if we try:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "Sqnc2ZnVl1_9",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "print(matrix[(1, 3)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "fTvV-mAal9sW",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "The `get()` method solves this problem:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "irThl_o6mHHS",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "# The first argument is the key; the second argument is the value\n",
    "# get should return 0 if the key is not in the dictionary\n",
    "\n",
    "print(matrix.get((0, 3), 0))\n",
    "print(matrix.get((1, 3), 0))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "8kQWpy3JTE5M",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## Memoisation\n",
    "\n",
    "- Considering the sequence of [Fibonacci numbers](https://en.wikipedia.org/wiki/Fibonacci_number)\n",
    "\n",
    "- and the function call graph for `fib()` with n = 4 \n",
    "\n",
    "![fib](images/11/fib.png)\n",
    "\n",
    "\n",
    "- A good solution is to keep track of values that have already been computed by **storing them in a dictionary**\n",
    "\n",
    "- A previously computed value that is stored for later use is called a **memo**\n",
    "    \n",
    "$\\Rightarrow$\n",
    "<https://github.com/fpro-feup/public/tree/master/lectures/11/fib.py>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "JRaixz4Ynfbi",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Let's have a look at a `fib()` implementation (using **recursion**!):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "sUaLF5j8o1Fc",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "# This is a particularly inefficient algorithm, and this could be solved\n",
    "# far more efficient iteratively or using memoisation\n",
    "\n",
    "def fib(n):\n",
    "    if n <= 1: return n\n",
    "    return fib(n-1) + fib(n-2)\n",
    "\n",
    "print(fib(10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "6kLNasDApOv9",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Now, using **memoisation**:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "qdhYfxiYnlzq",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "already_known = {0: 0, 1: 1}\n",
    "\n",
    "def fib(n):\n",
    "    if n not in already_known:\n",
    "        new_value = fib(n-1) + fib(n-2)\n",
    "        already_known[n] = new_value\n",
    "    return already_known[n]\n",
    "\n",
    "print(fib(10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "Zz-UtV8ORH_t",
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Ticket to leave"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "C-hchAExRRVh",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## Moodle activity\n",
    "\n",
    "[LE11: Dictionaries](https://moodle.up.pt/course/view.php?id=1738#section-1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "uV1OP6ahRYne",
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "\n",
    "$\\Rightarrow$ \n",
    "[Go back to the Table of Contents](00-contents.ipynb)\n",
    "\n",
    "$\\Rightarrow$ \n",
    "[Read the Preface](00-preface.ipynb)"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "collapsed_sections": [],
   "name": "11-dictionaries.ipynb",
   "private_outputs": true,
   "provenance": [],
   "toc_visible": true
  },
  "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.8.5"
  },
  "rise": {
   "enable_chalkboard": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}