02 - dictionaries - instructor.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Hash table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Previously we learned about sequence objects such as: *string*, *list*, *tuple*. Now we are going to learn about a new object which implements the notion of **hash table**.\n",
    "\n",
    "Why do we need this new object? \n",
    "\n",
    "Sequences are a great tool but they have one big limitation. The execution time to find one specific value inside is linear:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "'x' in range(100)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%timeit -n100 'x' in range(100)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%timeit -n100 'x' in range(100_000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%timeit -n100 'x' in range(1_000_000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is a real problem because the membership test is a very useful and common procedure. So we would like to have something which is not dependent of the number of elements."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Another limitation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We would like, for example to associate a key to an element like here the name alice with the age 35. We cannot do that with a list or any other sequence object. \n",
    "\n",
    "We will get an error if we try:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "t = []\n",
    "t['alice'] = 35"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The hash table structure is the answer to these two limitations and in python it is implemented by the 'dictionary' object."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Dictionary"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Creation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p>Lists are created by using square brackets **[ ]**</p>\n",
    "<p>Dictionaries are created by using curly brackets **{ }**</p>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "d = {} # en empty dictionary"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The simplest way to create a dictionary with some value is:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "d = {'keyname': 'keyvalue'}\n",
    "print(d)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Following the previous example, we can create a hash table, a python dictionary, using the name of the person as *key* and the age as *value*:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "d = {'alice': 35, 'bob': 18}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(d)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Note: To go deeper**\n",
    "\n",
    "A dictionary object can also be created with the function *dict* similar to the *list* function used to create a list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "d2 = dict([('alice', 35), ('jane', 24), ('bob',18)])\n",
    "print(d2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "or:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "d3 = dict(bob=18, alice=35, jane=24)\n",
    "print(d3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Accessing elements"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To access an element of the dictionary:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "key = 'alice'\n",
    "value = d['alice']\n",
    "\n",
    "print('The name of the person is used as key:', key)\n",
    "print('The value associated to that key is:', d[key])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Adding an element"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Adding an element to a dictionary is done by creating a new *key* and affecting a value to it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "d['jane'] = 24"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(d)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It is also possible to add element using the method **update**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "d2 = {'tom': 54, 'david': 87}\n",
    "\n",
    "d.update(d2)\n",
    "print(d)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**note:**\n",
    "\n",
    "It is not possible to use the operator *+* to concatenate dictionaries. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "{'alice': 35} + {'bob': 18}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Key have to be unique; you cannot have two keys with the same name. If you try to add a key with a name already used you will overwrite the value of the previous one."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(d)\n",
    "d['alice'] = 12\n",
    "print(d)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Equality between dictionaries"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To be equal, all the elements which compose the first dictionay must be present in the second, and only those elements. \n",
    "\n",
    "The **position** (ordering) is not important. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "d1 = {'alice': 12, 'bob': 18, 'jane': 24, 'tom': 54, 'david': 87}\n",
    "d2 = {'tom': 54, 'david': 87}\n",
    "d3 = {'bob': 18, 'alice': 35, 'jane': 24}\n",
    "d4 = {'alice': 35, 'bob': 18, 'jane': 24}\n",
    "\n",
    "\n",
    "print('dictionary 1:', d1)\n",
    "print('dictionary 2:', d2)\n",
    "print('dictionary 3:', d3)\n",
    "print('dictionary 4:', d4)\n",
    "\n",
    "print()\n",
    "print('Dictionary 1 and dictionary 2 are not equal:', d1 == d2)\n",
    "print('Dictionary 1 and dictionary 3 are not equal:', d1 == d3)\n",
    "print('Dictionary 3 and dictionary 4 are equal:', d3 == d4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Useful dictionary methods"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dictionaries have their own methods. Two of the most useful are *keys* and *values* which, as their name suggest, extract all the keys and all the values in an iterator."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "d.keys()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "d.values()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Dictionaries are iterable (it is possible to use loops with them)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It is possible to perform some operations on a dictionary by iterating on the elements using the *keys* method:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for key in d.keys():\n",
    "    print(key)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**note: To go depper**\n",
    "\n",
    "You can iterate on a dictionary directly. This is equivalent to asking for the keys. It saves some typing but at the cost of readability."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for k in d:\n",
    "    print(k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "keys = list(d3.keys())\n",
    "print('Keys from dictionary 3:', keys)\n",
    "\n",
    "# We can sort them.\n",
    "keys.sort()\n",
    "print(keys)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Presence (or not) of an element inside a dictionary"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It is possible to test if a *key* is present in the dictionary (or not) using the keyword **in**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "'alice' in d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "'mark' in d"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "or not:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "'mark' not in d"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Warning:**\n",
    "\n",
    "You cannot test for the presence of values:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "12 in d"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But you can use the method *values* which will return a list of the values:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "12 in d.values()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Composite dictionary"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It is possible to have composite objects in a dictionary. A key has to be a simple object (string, integer, float). It cannot be a complex one like a numpy array but the value can be any valid python object:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "d = {'key1': 1}\n",
    "d['key2'] = 2\n",
    "d['key3'] = {'subdic': 3}\n",
    "d['key4'] = np.arange(10)\n",
    "\n",
    "for key in d:\n",
    "    print(key, ':', d[key])\n",
    "    \n",
    "print()\n",
    "print('A composite dictionary:', d)\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## dictionary and string formatting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Strings and dictionarys are closely linked and using dictionaries increases the capacity of the print function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "d = {'a': 1, 'b':2, 'c': 3}\n",
    "\n",
    "print('1st:', d['a'], '2nd:', d['b'], '3rd:', d['c'])\n",
    "\n",
    "print('1st:', d['a'], ', 2nd:', d['b'], ', 3rd:', d['c'])\n",
    "\n",
    "print('1st: {}, 2nd: {}, 3rd: {}'.format(d['a'], d['b'],d['c']))\n",
    "\n",
    "print('1st: {0}, 2nd: {2}, 3rd: {1}'.format(d['a'], d['c'], d['b']))\n",
    "\n",
    "print('1st: {var[a]}, 2nd: {var[b]}, 3rd: {var[c]}'.format(var=d))\n",
    "\n",
    "print('1st: {first}, 2nd: {second}, 3rd: {third}'.format(first=1, second=2, third=3))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The format method allows you to manipulate your string in a very powerful way. You can find more documentation [here](https://pyformat.info/)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When you want to save information in a file, this is also how you will format your output:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "f = open('myfile.txt', 'w')\n",
    "\n",
    "line1 = '1st: {var[a]}, 2nd: {var[b]}, 3rd: {var[c]}\\n'.format(var=d)\n",
    "line2 = '1st: {first}, 2nd: {second}, 3rd: {third}\\n'.format(first=1, second=2, third=3)\n",
    "line3 = '1st: {var[a]:04d}, 2nd: {var[b]:3.4f}, 3rd: {var[c]}\\n'.format(var=d)\n",
    "\n",
    "f.write(line1)\n",
    "f.write(line2)\n",
    "f.write(line3)\n",
    "f.close()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%more myfile.txt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style='background:#B1E0A8; padding:10px 10px 10px 10px;'>\n",
    "<H2> Challenges </H2>\n",
    "<li>\n",
    "    Read the file *agelist.txt* and copy the data into a dictionary similar to the one above.\n",
    "    <br>\n",
    "    Hint: Splice the data to avoid using the first line. \n",
    "</li>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "with open('data/agelist.txt') as f:\n",
    "    data = f.readlines()\n",
    "\n",
    "print(data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "data[1].strip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "data[1].strip().split()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "with open('data/agelist.txt') as f:\n",
    "    data = f.readlines()\n",
    "\n",
    "data = data[1:]  # Remove the header\n",
    "d = {}\n",
    "\n",
    "for i, line in enumerate(data):\n",
    "    line = line.strip().split()\n",
    "    d[line[0]] = int(line[1])\n",
    "print(d)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style='background:#B1E0A8; padding:10px 10px 10px 10px;'>\n",
    "<H2> Challenges </H2>\n",
    "<li>\n",
    "    Create a list containing the *inflammations* csv file-names that are present in the *data* directory as items.\n",
    "    <br>\n",
    "    Hint: Use the \"glob\" library.\n",
    "</li>\n",
    "<br>\n",
    "<li>\n",
    "Create a dictionary which has the file names (from the list created above) as keys and the data within the files as values.\n",
    "</li>\n",
    "Hint: You can use the function 'loadtxt' provided by the library 'numpy'\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution Challenge 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution Challenge 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "   \n"
   ]
  }
 ],
 "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.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}