06 Data structures.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Introduction\n",
    "\n",
    "A data structure is an 'object' in a program that holds a collection of data. A simple\n",
    "data structure might be an 'array' that holds the components of a vector, or a list of\n",
    "names. A more complicated data structure might represent a telephone directory, \n",
    "holding [name, telephone number] pairs.\n",
    "\n",
    "Modern languages, like Python, provide a range of library (built-in) data structures.\n",
    "These are well-tested and optimised; it is good practice to use library data structures to make programs\n",
    "simpler, easier to read and more efficient. \n",
    "\n",
    "It is possible to develop your own data structures for special purposes. In this activity\n",
    "we focus on selecting and using built-in data structures. The creation\n",
    "of your own data structures is introduced in Activity 12.\n",
    "\n",
    "\n",
    "### Objectives\n",
    "\n",
    "- Use `list`, `tuple` and dictionary (`dict`) data structures\n",
    "- Use iteratation to visit entries in a data structure \n",
    "- Learn to select the right data structure for an application"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Data structures\n",
    "\n",
    "So far we have restricted our examples to simple built-in data types, e.g. `string`, `int`, and `float`. In practice, programs will use *data structures* to collect data together into useful packages. For example, rather than representing a vector `r` of length 3 using three floats `u`, `v` and `w`, we could represent \n",
    "it as a list of floats, `r = [u, v, w]`. Similarly, if we want to store the names of students in a laboratory group, rather than a string variable for each student, we could work with a list of names, e.g.:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "lab_group0 = [\"Sarah\", \"John\", \"Joe\", \"Emily\"]\n",
    "lab_group1 = [\"Roger\", \"Rachel\", \"Amer\", \"Caroline\", \"Colin\"]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is a much more powerful construction because we can perform operations on a list, such as checking its length (number of students in a lab group), sort the names in the list into alphabetical order, and add or remove names. We could even make a list-of-lists, e.g."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "lab_groups = [lab_group0, lab_group1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "to collect all the lab groups together into a *nested* list.\n",
    "\n",
    "Data structures are particularly useful when passing data to functions. Say we want a function that prints the names of students in a given lab group. Rather than passing the name of each student (with different groups having differing numbers of members), we can pass just the list of lab group members to the function.\n",
    "Similarly, we could develop a function that computes the dot product between two vectors of arbitrary length, passing to the function just the two vectors rather than each component.\n",
    "\n",
    "We will look at three built-in Python data structures that are commonly used. They are:\n",
    "\n",
    "- `list` \n",
    "- `tuple`\n",
    "- `dict` (dictionary)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Lists\n",
    "\n",
    "A `list` is a sequence of data. An 'array' in most other languages is a similar concept, but Python lists are more general than most arrays as they can hold a mixture of types. A list is constructed using square brackets:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Lab group members: ['Sarah', 'John', 'Joe', 'Emily', 'Quang']\n",
      "Size of lab group: 5\n",
      "Check the Python object type: <class 'list'>\n"
     ]
    }
   ],
   "source": [
    "lab_group0 = [\"Sarah\", \"John\", \"Joe\", \"Emily\", \"Quang\"]\n",
    "print(\"Lab group members: {}\".format(lab_group0))\n",
    "print(\"Size of lab group: {}\".format(len(lab_group0)))\n",
    "\n",
    "print(\"Check the Python object type: {}\".format(type(lab_group0)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The function '`len`' returns the length (number of items) of the list.\n",
    "\n",
    "An empty list is created by"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "my_list = []"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A list of length 5 with repeated values can be created by"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['Oliver', 'Oliver', 'Oliver', 'Oliver', 'Oliver']\n"
     ]
    }
   ],
   "source": [
    "my_list = [\"Oliver\"]*5\n",
    "print(my_list)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Iterating over lists\n",
    "\n",
    "Looping over each item in a list (or more generally a sequence) is called *iterating*. We iterate over the members of the lab group using the syntax:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sarah\n",
      "John\n",
      "Joe\n",
      "Emily\n",
      "Quang\n"
     ]
    }
   ],
   "source": [
    "for member in lab_group0:\n",
    "    print(member)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Say we want to iterate over the names of the lab group members, and get the position\n",
    "of each member in the list. We use `enumerate` for this: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 Sarah\n",
      "1 John\n",
      "2 Joe\n",
      "3 Emily\n",
      "4 Quang\n"
     ]
    }
   ],
   "source": [
    "for n, member in enumerate(lab_group0):\n",
    "    print(n, member)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the above, `n` is the position in the list and `member` is the $n$th entry in the list. Sometimes we need to know the position, in which case `enumerate` is helpful. However, when possible it is preferable to use a 'plain' iteration. Note that Python counts from zero - it uses zero-based indexing."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Manipulating lists \n",
    "\n",
    "There are many functions for manipulating lists. It might be useful to sort the list:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Emily\n",
      "Joe\n",
      "John\n",
      "Quang\n",
      "Sarah\n"
     ]
    }
   ],
   "source": [
    "lab_group0.sort()\n",
    "for member in lab_group0:\n",
    "    print(member)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the above, `sort` is known as a 'method' of a `list`. It performs an *in-place* sort, i.e. `lab_group0` is sorted, rather than creating a new list with sorted entries (for the latter we would use `sorted(lab_group0)`, which returns a new list). More on methods later when we get to object-oriented design.\n",
    "\n",
    "With lists we can add and remove students:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['Emily', 'John', 'Quang', 'Sarah']\n",
      "['Emily', 'John', 'Quang', 'Sarah', 'Josephine']\n"
     ]
    }
   ],
   "source": [
    "# Remove the second student (indexing starts from 0, so 1 is the second element)\n",
    "lab_group0.pop(1)\n",
    "print(lab_group0)\n",
    "\n",
    "# Add new student \"Josephine\" at the end of the list\n",
    "lab_group0.append(\"Josephine\")\n",
    "print(lab_group0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "or maybe join two groups to create one larger group: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['Emily', 'John', 'Quang', 'Sarah', 'Josephine', 'Roger', 'Rachel', 'Amer', 'Caroline', 'Colin']\n"
     ]
    }
   ],
   "source": [
    "lab_group1 = [\"Roger\", \"Rachel\", \"Amer\", \"Caroline\", \"Colin\"]\n",
    "\n",
    "lab_group = lab_group0 + lab_group1\n",
    "print(lab_group)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "or create a list of group lists:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[['Emily', 'John', 'Quang', 'Sarah', 'Josephine'], ['Roger', 'Rachel', 'Amer', 'Caroline', 'Colin']]\n",
      "---\n",
      "Print each lab group (name and members):\n",
      "0 ['Emily', 'John', 'Quang', 'Sarah', 'Josephine']\n",
      "1 ['Roger', 'Rachel', 'Amer', 'Caroline', 'Colin']\n"
     ]
    }
   ],
   "source": [
    "lab_groups = [lab_group0, lab_group1]\n",
    "print(lab_groups)\n",
    "\n",
    "print(\"---\")\n",
    "\n",
    "print(\"Print each lab group (name and members):\")\n",
    "for i, lab_group in enumerate(lab_groups):\n",
    "    print(i, lab_group)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Indexing\n",
    "\n",
    "Lists store data in order, so it is possible to 'index into' a list using an integer (this will be familiar to anyone who has used C), e.g.:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Emily Quang\n"
     ]
    }
   ],
   "source": [
    "first_member = lab_group0[0]\n",
    "third_member = lab_group0[2]\n",
    "print(first_member, third_member)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "or"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Emily\n",
      "John\n",
      "Quang\n",
      "Sarah\n",
      "Josephine\n"
     ]
    }
   ],
   "source": [
    "for i in range(len(lab_group0)):\n",
    "    print(lab_group0[i])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Indices start from zero, and run through to (length - 1).\n",
    "\n",
    "Indexing can be useful for numerical computations. We use it here to compute the dot product of two vectors:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "154.45000000000002\n"
     ]
    }
   ],
   "source": [
    "# Two vectors of length 4\n",
    "x = [1.0, 3.5, 7.2, 8.9]\n",
    "y = [-1.0, 27.1, 1.0, 6]\n",
    "\n",
    "# Compute dot-product\n",
    "dot_product = 0.0\n",
    "for i in range(len(x)):\n",
    "    dot_product += x[i]*y[i]\n",
    "\n",
    "print(dot_product)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When possible, it is better to iterate over a list rather than use indexing, since there are data structures that support iterating but do not support indexing.\n",
    "\n",
    "If we have a list-of-lists,"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "lab_group0 = [\"Sarah\", \"John\", \"Joe\", \"Emily\"]\n",
    "lab_group1 = [\"Roger\", \"Rachel\", \"Amer\", \"Caroline\", \"Colin\"]\n",
    "lab_groups = [lab_group0, lab_group1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "we can use the first index to access a list, and a second index to access the entry in that list:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['Sarah', 'John', 'Joe', 'Emily']\n",
      "Amer\n"
     ]
    }
   ],
   "source": [
    "group = lab_groups[0]\n",
    "print(group)\n",
    "\n",
    "name = lab_groups[1][2]\n",
    "print(name)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Heterogeneity (lists with mixed types)\n",
    "\n",
    "Python lists are heterogeneous data structures - this means they can store mixed types, e.g."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Adam <class 'str'>\n",
      "(2+4j) <class 'complex'>\n",
      "1.0 <class 'float'>\n",
      "4 <class 'int'>\n"
     ]
    }
   ],
   "source": [
    "mixed_list = [\"Adam\", 2 + 4j, 1.0, 4]\n",
    "for entry in mixed_list:\n",
    "    print(entry, type(entry))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Arrays in most languages are homogeneous - all types in the array must be the same.\n",
    "\n",
    "There are *many* ways in which lists can be manipulated. The best way to learn how to perform a specific operation is to use a search engine."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## List comprehension (advanced, optional)\n",
    "\n",
    "A powerful construct in modern languages, including Python, is *list comprehension*. It is a way to succinctly build lists from other lists. It can be very useful, but should be applied sensibly as it can sometimes be difficult to read. There is an optional extension exercise at the end of this notebook that uses list comprehension.\n",
    "\n",
    "Say we have a list of numbers, and we wish to create a new list that squares each number in the original list and adds 5. Using list comprehension:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[4, 6, 10, 11]\n",
      "[21, 41, 105, 126]\n"
     ]
    }
   ],
   "source": [
    "x = [4, 6, 10, 11]\n",
    "y = [a*a + 5 for a in x]\n",
    "\n",
    "print(x)\n",
    "print(y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To understand the meaning, read the statement left-to-right.\n",
    "\n",
    "As another example, say we have a list of names and we want to \n",
    "\n",
    "- build a new list of names that contains only the names with more than 5 characters; and \n",
    "- for these names we want to add a full stop at the end.\n",
    "\n",
    "Using list comprehension:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['Roger', 'Rachel', 'Amer', 'Caroline', 'Colin']\n",
      "['Rachel.', 'Caroline.']\n"
     ]
    }
   ],
   "source": [
    "lab_group1 = [\"Roger\", \"Rachel\", \"Amer\", \"Caroline\", \"Colin\"]\n",
    "group = [name + \".\" for name in lab_group1 if len(name) > 5]\n",
    "\n",
    "print(lab_group1)\n",
    "print(group)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Mastering list comprehension is not simple, but it is very powerful."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Tuples\n",
    "\n",
    "Tuples are closely related to lists. The main difference is that a tuple cannot be changed after it has been created. \n",
    "In computing jargon, it is *immutable*.\n",
    "\n",
    "For something that should not change after it has been created, such as a vector of length three with fixed entries, a tuple is more appropriate than a list. It is 'safer' in this case since it cannot be modified accidentally in a program. Being immutable ('read-only') also permits implementations to be optimised for speed.\n",
    "\n",
    "To create a tuple, use round brackets. Say at a college each student is assigned a room, and the rooms are numbered. A student 'Laura' is given room 32:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Room allocation: ('Laura', 32)\n",
      "Length of entry: 2\n",
      "<class 'tuple'>\n"
     ]
    }
   ],
   "source": [
    "room = (\"Laura\", 32)\n",
    "print(\"Room allocation: {}\".format(room))\n",
    "print(\"Length of entry: {}\".format(len(room)))\n",
    "print(type(room))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can iterate over tuples in the same way as with lists,"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Laura\n",
      "32\n"
     ]
    }
   ],
   "source": [
    "# Iterate over tuple values\n",
    "for d in room:\n",
    "    print(d)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "and we can index into a tuple:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "32\n",
      "Laura\n"
     ]
    }
   ],
   "source": [
    "# Index into tuple values\n",
    "print(room[1])\n",
    "print(room[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We might have a student who is given permission to live outside of college. To keep track of them we still want an entry for the student, but there is no associated room number. We can create a tuple of length one using '`(\"a\",)`', e.g.:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Room allocation: ('Adrian',)\n",
      "Length of entry: 1\n",
      "<class 'tuple'>\n"
     ]
    }
   ],
   "source": [
    "room = (\"Adrian\",)\n",
    "print(\"Room allocation: {}\".format(room))\n",
    "print(\"Length of entry: {}\".format(len(room)))\n",
    "print(type(room))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As part of a rooms database, we can create a list of tuples:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[('Adrian',), ('Laura', 32), ('John', 31), ('Penelope', 28), ('Fraser', 28), ('Gaurav', 19)]\n"
     ]
    }
   ],
   "source": [
    "room_allocation = [(\"Adrian\",), (\"Laura\", 32), (\"John\", 31), (\"Penelope\", 28), (\"Fraser\", 28), (\"Gaurav\", 19)]\n",
    "print(room_allocation)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To make it easier for students to find their rooms on a printed room list, we can sort the list:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[('Adrian',), ('Fraser', 28), ('Gaurav', 19), ('John', 31), ('Laura', 32), ('Penelope', 28)]\n"
     ]
    }
   ],
   "source": [
    "room_allocation.sort()\n",
    "print(room_allocation)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We could improve the printed list by not printing those living outside of the college:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Name: Fraser \n",
      "  Room: 28\n",
      "Name: Gaurav \n",
      "  Room: 19\n",
      "Name: John \n",
      "  Room: 31\n",
      "Name: Laura \n",
      "  Room: 32\n",
      "Name: Penelope \n",
      "  Room: 28\n"
     ]
    }
   ],
   "source": [
    "for entry in room_allocation:\n",
    "    if len(entry) > 1:\n",
    "        print(\"Name: {} \\n  Room: {}\".format(entry[0], entry[1]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In summary, prefer tuples over lists when the length will not change."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Dictionaries (maps)\n",
    "\n",
    "We used a list of tuples in the previous section to store room allocations. If we wanted to find which room a particular student has been allocated we would need to iterate through the list and check each name. For a very large list, this might not be very efficient.\n",
    "\n",
    "There is a better way to do this, using a 'dictionary' (or sometimes called a 'map'). We have used indexing (with integers) into lists and tuples for direct access to a specific entry. This works if we know the index to the entry of interest. But, for a room list we identify individuals by name rather than a contiguous set of integers. Using a dictionary, we can build a 'map' from names (the *keys*) to room numbers (the *values*). \n",
    "\n",
    "A Python dictionary (`dict`) is declared using curly braces:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'Penelope': 28, 'John': 31, 'Adrian': None, 'Fraser': 28, 'Laura': 32, 'Gaurav': 19}\n",
      "<class 'dict'>\n"
     ]
    }
   ],
   "source": [
    "room_allocation = {\"Adrian\": None, \"Laura\": 32, \"John\": 31, \"Penelope\": 28, \"Fraser\": 28, \"Gaurav\": 19}\n",
    "print(room_allocation)\n",
    "print(type(room_allocation))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Each entry is separated by a comma. For each entry we have a 'key', which is followed by a colon, and then the 'value'. Note that for Adrian we have used '`None`' for the value, which is a Python keyword for 'nothing' or 'empty'.\n",
    "\n",
    "Now if we want to know which room Fraser has been allocated, we can query the dictionary by key:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "28\n"
     ]
    }
   ],
   "source": [
    "frasers_room = room_allocation[\"Fraser\"]\n",
    "print(frasers_room)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we try to use a key that does not exist in the dictionary, e.g.\n",
    "\n",
    "    frasers_room = room_allocation[\"Frasers\"]\n",
    "\n",
    "Python will give an error (raise an exception). If we're not sure that a key is present, we can check:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "print(\"Fraser\" in room_allocation)\n",
    "print(\"Frasers\" in room_allocation)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(We can also use '`in`' to check if an entry exists in a list or tuple).\n",
    "We can iterate over the keys in a dictionary:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Penelope\n",
      "John\n",
      "Adrian\n",
      "Fraser\n",
      "Laura\n",
      "Gaurav\n"
     ]
    }
   ],
   "source": [
    "for d in room_allocation:\n",
    "    print(d)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "or iterate over both the keys and the values:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Penelope 28\n",
      "John 31\n",
      "Adrian None\n",
      "Fraser 28\n",
      "Laura 32\n",
      "Gaurav 19\n"
     ]
    }
   ],
   "source": [
    "for name, room_number in room_allocation.items():\n",
    "    print(name, room_number)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that the order of the printed entries in the dictionary is different from the input order. This is because a dictionary stores data differently from a list or tuple. Lists and tuples store entries 'linearly' in memory\n",
    "(contiguous pieces of memory), which is why we can access entries by index. Dictionaries use a different type of storage which allows us to perform look-ups using a 'key'.\n",
    "\n",
    "We have used a string as the key so far, which is common. However, we can use almost any type as a key, and we can mix types. For example, we might want to 'invert' the room allocation dictionary to create a room-to-name map: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{32: 'Laura', 19: 'Gaurav', None: 'Adrian', 28: 'Fraser', 31: 'John'}\n"
     ]
    }
   ],
   "source": [
    "# Create empty dictionary\n",
    "room_allocation_inverse = {}\n",
    "\n",
    "# Build inverse dictionary to map 'room number' -> name \n",
    "for name, room_number in room_allocation.items():\n",
    "    # Insert entry into dictionary\n",
    "    room_allocation_inverse[room_number] = name\n",
    "\n",
    "print(room_allocation_inverse)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can now ask who is in room 28 and who is in room 29. Not all rooms are occupied, so we should include a check that the room number is a key in our dictionary:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Room 28 is occupied by Fraser.\n",
      "Room 29 is unoccupied.\n"
     ]
    }
   ],
   "source": [
    "rooms_to_check = [28, 29]\n",
    "\n",
    "for room in rooms_to_check:\n",
    "    if room in room_allocation_inverse:\n",
    "        print(\"Room {} is occupied by {}.\".format(room, room_allocation_inverse[room]))\n",
    "    else:\n",
    "        print(\"Room {} is unoccupied.\".format(room))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# Choosing a data structure\n",
    "\n",
    "An important task when developing a computer program is selecting the *appropriate* data structure for a task.\n",
    "The more flexible the data structure, generally the less efficient it will be and it will use more memory compared to simpler data structures.\n",
    "\n",
    "- If efficiency is not critical, pick a data structure that provides the functionality you need, and offers \n",
    "  flexibility and ease of use. Safety should also be considered (this can be a good reason for choosing a \n",
    "  tuple over a list).\n",
    "- Use iterators rather than indexing when possible. This will allow switching from data structures that support \n",
    "  indexing to data structures that do not support indexing (such as a '`set`' data structure).\n",
    "\n",
    "For many numerical computations, efficiency is essential and picking the right data structure is critical\n",
    "for this. We will look at data structures that are specialied for numerical computations in the next notebook, and we'll see the huge difference in speed there can be between different data structures."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Exercises\n",
    "\n",
    "Complete now the [06 Exercises](Exercises/06%20Exercises.ipynb) notebook."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}