week-02_IW_Data_Structures.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "import matplotlib\n",
    "import seaborn as sns\n",
    "matplotlib.rcParams['savefig.dpi'] = 144"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import expectexception"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Python Built-in Data Structures\n",
    "\n",
    "Python comes built-in with primitive data types for you to use to store your data. Here are some examples:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "42\n",
      "3.14\n",
      "data\n",
      "1j\n"
     ]
    }
   ],
   "source": [
    "thing1 = 42\n",
    "thing2 = 3.14\n",
    "thing3 = 'data'\n",
    "thing4 = complex(0, 1)\n",
    "\n",
    "print thing1\n",
    "print thing2\n",
    "print thing3\n",
    "print thing4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We created 4 variables to store 4 things. This works, but frequently you will need and want to group these together in a more sensible and efficient way.\n",
    "\n",
    "Python comes with many built-in data structures for you to use to group your data together and store in memory. In this notebook, we will explore the most common data structures and how to make thoughtful choices about which is the best data structure for your needs.\n",
    "\n",
    "One of the data structures we will learn about is a `list`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[42, 3.14, 'data', 1j]\n",
      "<type 'list'>\n"
     ]
    }
   ],
   "source": [
    "list_of_things = [42, 3.14, 'data', complex(0, 1)]\n",
    "\n",
    "print list_of_things\n",
    "print type(list_of_things)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Another built-in data structure is a `set`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "set([42, 1j, 'data', 3.14])\n",
      "<type 'set'>\n"
     ]
    }
   ],
   "source": [
    "set_of_things = {42, 3.14, 'data', complex(0, 1)}\n",
    "                 \n",
    "print set_of_things\n",
    "print type(set_of_things)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We could also use a `tuple`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(42, 3.14, 'data', 1j)\n",
      "<type 'tuple'>\n"
     ]
    }
   ],
   "source": [
    "tuple_of_things = (42, 3.14, 'data', complex(0, 1))\n",
    "                 \n",
    "print tuple_of_things\n",
    "print type(tuple_of_things)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Or perhaps a `dict` (dictionary):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{1: 42, 2: 3.14, 3: 'data', 4: 1j}\n",
      "<type 'dict'>\n"
     ]
    }
   ],
   "source": [
    "dict_of_things = {1: 42, 2: 3.14, 3: 'data', 4: complex(0, 1)}\n",
    "\n",
    "print dict_of_things\n",
    "print type(dict_of_things)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Each of these data structures offers different methods for adding, updating, or removing the contained data. You will need to think carefully about how your program needs to access data to make effective data structure choices."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Python `list`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The first data structure we will explore is the Python `list`.\n",
    "\n",
    "A Python `list` is an *ordered* collection of heterogeneous objects. A `list` can be created using square brackets [ ] and data items separated with commas:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "squares = [1, 4, 9, 16, 25]\n",
    "primes = [2, 3, 5, 7, 11, 13, 17, 19]\n",
    "misc = [1, 'foo', 2.71828, None]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 4, 9, 16, 25]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "squares"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The first two examples are lists of integers. The third is a list containing an integer, a string, a float, and a NoneType.\n",
    "\n",
    "The third is to show you that a list does not need to contain data items that are all the same type. This contrasts with Array data structures found in some other compiled programming languages like Java and C++.\n",
    "\n",
    "If we were so inclined, we could even make a list of lists:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1, 2, 3], [4, 5, 6], [7, 8, 9]]\n"
     ]
    }
   ],
   "source": [
    "list_of_lists = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]\n",
    "\n",
    "print list_of_lists"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You'll find that nesting data structures inside each other can be an extremely effective way of storing data.\n",
    "\n",
    "Consider the list of primes, defined above. We can *index* into the list using square brackets [ ] and an integer:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "11\n"
     ]
    }
   ],
   "source": [
    "print primes[4]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question:** Is that the 4th prime number in the list...or the 5th?\n",
    "\n",
    "It's actually the 5th, because Python `list`s are *zero indexed*:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "3\n",
      "5\n",
      "7\n",
      "11\n"
     ]
    }
   ],
   "source": [
    "print primes[0] # first\n",
    "print primes[1] # second\n",
    "print primes[2] # third\n",
    "print primes[3] # fourth\n",
    "print primes[4] # fifth"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Pay careful attention to this detail!** For people new to programming or coming from the matlab world, confusion about this can be a frequent source of error. People can get tripped up by this because we don't normally start counting things starting with zero.\n",
    "\n",
    "Index values needn't be fixed to one value; we can use a variable for that instead."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "11"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "index = 4\n",
    "primes[index]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This leads to an easy way of *iterating* through a list in a for-loop:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 2\n",
      "1 3\n",
      "2 5\n",
      "3 7\n",
      "4 11\n",
      "5 13\n",
      "6 17\n",
      "7 19\n"
     ]
    }
   ],
   "source": [
    "for i in range(len(primes)):\n",
    "    print i, primes[i]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You will frequently need to iterate through items in a `list` in a for-loop. Conveniently, Python offers a programming construct for doing this more simply:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "3\n",
      "5\n",
      "7\n",
      "11\n",
      "13\n",
      "17\n",
      "19\n"
     ]
    }
   ],
   "source": [
    "for prime in primes:\n",
    "    print prime"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this example each number in the list is assigned to the variable `prime`, one at a time, in the order that they are stored in the `list`.\n",
    "\n",
    "The above programming construct is preferred over the first one that used the `range` keyword.\n",
    "\n",
    "### Accessing and Modifying Python `list` data\n",
    "\n",
    "Frequently you will want to change a `list`'s contents. If we want to add an item to the end of the list, we can use the `append` method:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "primes.append(23)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice you don't see any output in the previous cell. That's because the `primes` list was modified *in place*. We can examine `primes` to see that it is in fact different:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 3, 5, 7, 11, 13, 17, 19, 23]\n"
     ]
    }
   ],
   "source": [
    "print primes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Remember this, as this concept will come up again later in our studies.\n",
    "\n",
    "We can also add extend the list with another list using the addition (`+`) operator:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 25, 29, 31]"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "primes + [25, 29, 31]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the previous cell you do see output because the Python statement created a new `list` that is a combination of `primes` and the list `[25, 29, 31]`. The list `primes` was not affected."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]\n"
     ]
    }
   ],
   "source": [
    "print primes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we wanted to update `primes`, we would have to assign it back to that variable."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 3, 5, 7, 11, 13, 17, 19, 23, 27, 31, 37]\n"
     ]
    }
   ],
   "source": [
    "primes = primes + [27, 31, 37]\n",
    "\n",
    "print primes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But wait a minute! We added the non-prime number 27 to the list. We meant to type 29. We can easily fix that using a `list`'s index functionality:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]\n"
     ]
    }
   ],
   "source": [
    "primes[9] = 29\n",
    "\n",
    "print primes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this example we indexed into `primes` using the number `9` because the number `27` was the 10th item starting from the front of the list. However, we didn't have to count from the front of the list: Python allows us to index from the rear of the list instead:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "primes[-3] = 29"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Observe that we used `-3`, not `-2`. That's because the last item in the list is accessed with the index `-1`, like so:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "37\n"
     ]
    }
   ],
   "source": [
    "print primes[-1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Python `list` indexing is a powerful feature. We can also use it access a sublist:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 3, 5, 7, 11]\n"
     ]
    }
   ],
   "source": [
    "print primes[0:5]  # first 5 primes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Observe that Python list indexing is *inclusive-exclusive*. That is, it starts at the first index and ends right *before* the last index:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "3\n",
      "5\n",
      "7\n",
      "11\n"
     ]
    }
   ],
   "source": [
    "print primes[0]  # included\n",
    "print primes[1]\n",
    "print primes[2]\n",
    "print primes[3]\n",
    "print primes[4]\n",
    "# print primes[5]  # excluded"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we want the sublist to begin or end at the beginning or ending of the original list, we can leave out that number:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 3, 5, 7, 11]\n",
      "[29, 31, 37]\n"
     ]
    }
   ],
   "source": [
    "print primes[:5]  # same because 0 is implicit\n",
    "print primes[-3:] # last 3 primes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can access every other prime number if we wish:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 5, 11, 17, 23, 31]\n",
      "[2, 5, 11, 17, 23, 31]\n"
     ]
    }
   ],
   "source": [
    "print primes[0:-1:2]  # step size of 2\n",
    "print primes[::2]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Or the list in reverse:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[37, 31, 29, 23, 19, 17, 13, 11, 7, 5, 3, 2]\n"
     ]
    }
   ],
   "source": [
    "print primes[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "primes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question:** What happens if we create a sublist and modify one of the values? Is the original `list` also modified?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['cat', 'dog', 'lion']\n",
      "['cat', 'dog', 'elephant', 'dolphin', 'tardigrade']\n"
     ]
    }
   ],
   "source": [
    "animals = ['cat', 'dog', 'elephant', 'dolphin', 'tardigrade']\n",
    "animals_sublist = animals[:3]\n",
    "\n",
    "animals_sublist[2] = 'lion'\n",
    "\n",
    "print animals_sublist\n",
    "print animals"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<function count>"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "animals.count"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It is not, because the Python command `animals[:3]` actually created a new list, referencing the same `str` objects. Modifying `animals_sublist[2]` only changed `animals_sublist`, not `animals`.\n",
    "\n",
    "You will frequently use the `len` built-in function to count the length of a `list`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "12\n"
     ]
    }
   ],
   "source": [
    "print len(primes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Python `list`s have a built-in method for sorting the items in the `list`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 4, 7, 7, 9]\n",
      "[9, 7, 7, 4, 2]\n"
     ]
    }
   ],
   "source": [
    "random = [7, 4, 7, 2, 9]\n",
    "\n",
    "random.sort()\n",
    "\n",
    "print random\n",
    "\n",
    "random.sort(reverse=True)\n",
    "\n",
    "print random"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There a few more `list` methods, but the ones discussed above are the ones that are most frequently used. Take the time to familiarize yourself with them as much as possible so you can recall them later. These methods will become the building blocks to data manipulations later in your Python adventures."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Python `dict` (a.k.a. dictionaries)\n",
    "\n",
    "The Python `dict` data structure provides you with the ability to create a mapping from one set of objects to another. \n",
    "\n",
    "A real [Dictionary](http://www.merriam-webster.com/) maps words in our language to each words' definition. The mapping is in one direction, meaning that we can easily use a word to look up a word's definition, but with a definition we cannot (easily) find the word that the definition belongs to. In this analogy, the words are like keys that are used to map to definitions, or values.\n",
    "\n",
    "A Python dictionary maps Python objects to each other. The objects used to do the \"looking up\" are called *keys*, and are mapped to other Python objects referred to as *values*. Together, each key and value can be called key-value pairs. A dictionary is composed of a collection of key-value pairs.\n",
    "\n",
    "Here is a simple example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'Stephen Hawking': 1942, 'Albert Einstein': 1879, 'Marie Curie': 1867}\n"
     ]
    }
   ],
   "source": [
    "physicists = {'Albert Einstein': 1879, \n",
    "              'Stephen Hawking': 1942,\n",
    "              'Marie Curie': 1867}\n",
    "\n",
    "print physicists"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This maps the names of famous Physicists to the year they were born.\n",
    "\n",
    "Carefully observe the syntax of this code. Notice we are using curly braces { } to define the dictionary. Also notice that we use a colon : to separate the keys (names) from the values (years). The key-value pairs are separated by commas.\n",
    "\n",
    "You can also define a `dict` using this syntax:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'square': 4, 'triangle': 3, 'octagon': 8}\n"
     ]
    }
   ],
   "source": [
    "num_of_sides = dict(triangle=3, square=4, octagon=8)\n",
    "\n",
    "print num_of_sides"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Observe the syntax differences. Instead of curly braces we have parentheses ( ) and are using the `dict` constructor. Instead of colons we have equals = signs. The keys, which are strings, do not have quotes around them like most other strings.\n",
    "\n",
    "This alternate syntax can only work when you want the dictionary's keys to be strings, those strings do not contain spaces, and several other limitations. Nevertheless, this syntax can be easier to type."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can access a `dict`'s values with square brackets [ ], much like a list, but instead of using an integer index, we will use the keys:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1867"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "physicists['Marie Curie']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can add additional key-value pairs to the `dict`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "physicists['Nikola Tesla'] = 1858"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'Stephen Hawking': 1942, 'Nikola Tesla': 1858, 'Albert Einstein': 1879, 'Marie Curie': 1867}\n"
     ]
    }
   ],
   "source": [
    "print physicists"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I can also change an existing value:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "physicists['Nikola Tesla'] = 1856"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'Stephen Hawking': 1942, 'Nikola Tesla': 1856, 'Albert Einstein': 1879, 'Marie Curie': 1867}\n"
     ]
    }
   ],
   "source": [
    "print physicists"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we try to access a non-existing key, we will get a KeyError exception:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[0;31m\u001b[0m\n",
      "\u001b[0;31mKeyError\u001b[0mTraceback (most recent call last)\n",
      "\u001b[0;32m<ipython-input-46-010a5ab864fa>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n",
      "\u001b[1;32m      1\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m----> 2\u001b[0;31m \u001b[0mphysicists\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m'Isaac Newton'\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0m\n",
      "\u001b[0;31mKeyError\u001b[0m: 'Isaac Newton'\n"
     ]
    }
   ],
   "source": [
    "%%expect_exception KeyError\n",
    "\n",
    "physicists['Isaac Newton']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Happily we can test a `dict` to see if it has a given key before the lookup:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n",
      "True\n",
      "1867\n"
     ]
    }
   ],
   "source": [
    "print 'Isaac Newton' in physicists\n",
    "print 'Nikola Tesla' in physicists\n",
    "\n",
    "if 'Marie Curie' in physicists:\n",
    "    print physicists['Marie Curie']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A `dict`'s get method can be very helpful in this case. It performs the same action as the square brackets [ ] lookup except it returns `None` if the key is not found. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None\n"
     ]
    }
   ],
   "source": [
    "print physicists.get('Isaac Newton')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we want, we can specify an alternative to `None`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n"
     ]
    }
   ],
   "source": [
    "print physicists.get('Isaac Newton', 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we wish to remove a key-value pair from a dictionary, we can use the `del` keyword:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'Stephen Hawking': 1942, 'Nikola Tesla': 1858, 'Albert Einstein': 1879, 'Marie Curie': 1867}\n",
      "{'Nikola Tesla': 1858, 'Albert Einstein': 1879, 'Marie Curie': 1867}\n"
     ]
    }
   ],
   "source": [
    "print physicists\n",
    "\n",
    "del physicists['Stephen Hawking']\n",
    "\n",
    "print physicists"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If Stephen Hawking was not in the `physicists` dictionary, the code would have raised another `KeyError`.\n",
    "\n",
    "The examples we have seen so far have all mapped strings to integers. Consider this example, which maps integers to integers:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{1: 1, 2: 4, 3: 9, 4: 16, 5: 25}\n"
     ]
    }
   ],
   "source": [
    "square_lut = {1: 1, 2: 4, 3: 9, 4: 16, 5: 25}\n",
    "\n",
    "print square_lut"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A lookup table like this could be used to get the square of an integer without having to recalculate it again and again. Used correctly, lookup tables can improve the execution performance of your code.\n",
    "\n",
    "If you want, you can access just a dictionary's keys or values using the `keys()` and `values()` methods:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "keys: [1, 2, 3, 4, 5]\n",
      "values: [1, 4, 9, 16, 25]\n"
     ]
    }
   ],
   "source": [
    "print 'keys:', square_lut.keys()\n",
    "print 'values:', square_lut.values()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can access the keys and values as pairs (`tuples`, discussed later) using the `items()` method:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(1, 1), (2, 4), (3, 9), (4, 16), (5, 25)]\n"
     ]
    }
   ],
   "source": [
    "print square_lut.items()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is a `list` but it can be converted back into a dictionary with the `dict` constructor:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{1: 1, 2: 4, 3: 9, 4: 16, 5: 25}\n"
     ]
    }
   ],
   "source": [
    "print dict(square_lut.items())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can iterate through a `dict`'s items much like a `list`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 1\n",
      "2 4\n",
      "3 9\n",
      "4 16\n",
      "5 25\n"
     ]
    }
   ],
   "source": [
    "for k, v in square_lut.items():\n",
    "    print '%d %d' % (k, v)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### A more sophisticated example...\n",
    "\n",
    "Let's try combining what we have learned so far about dictionaries and lists by making a dictionary that maps strings to a list of strings."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "foods = {'fruits': ['apple', 'watermelon', 'orange', 'nectarine'],\n",
    "         'vegetables': ['potato', 'lettuce', 'onion', 'spinach', 'kale']}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can access the data with a chain of square bracket lookups:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "watermelon\n",
      "['spinach', 'kale']\n"
     ]
    }
   ],
   "source": [
    "print foods['fruits'][1]\n",
    "print foods['vegetables'][3:]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Iterating over a dictionary yields its keys.  We can use this with nested for loops to create a little report of foods:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "vegetables\n",
      "==========\n",
      "potato\n",
      "lettuce\n",
      "onion\n",
      "spinach\n",
      "kale\n",
      "\n",
      "\n",
      "fruits\n",
      "======\n",
      "apple\n",
      "watermelon\n",
      "orange\n",
      "nectarine\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "for food_type in foods:\n",
    "    print food_type\n",
    "    print '=' * len(food_type)\n",
    "    for food_item in foods[food_type]:\n",
    "        print food_item\n",
    "    print '\\n'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that our food types come out in a different order than they were put in.  A dictionary is *unordered*&mdash;when you ask for its keys, you may get them in an arbitrary order.  (Sometimes, as in `square_lut` above, Python will seem to be ordering the keys.  This is an implementation detail and should not be counted on to stay consistent.)\n",
    "\n",
    "Our `foods` `dict` maps strings to `list`s. Can we do the reverse? Map a list to a string?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[0;31m\u001b[0m\n",
      "\u001b[0;31mTypeError\u001b[0mTraceback (most recent call last)\n",
      "\u001b[0;32m<ipython-input-59-d808df00ba26>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n",
      "\u001b[1;32m      1\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m----> 2\u001b[0;31m \u001b[0;34m{\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m3\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;34m'one, two, three'\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0;36m4\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m5\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m6\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;34m'four, five, six'\u001b[0m\u001b[0;34m}\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0m\n",
      "\u001b[0;31mTypeError\u001b[0m: unhashable type: 'list'\n"
     ]
    }
   ],
   "source": [
    "%%expect_exception TypeError\n",
    "\n",
    "{[1, 2, 3]: 'one, two, three', [4, 5, 6]: 'four, five, six'}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "No, we cannot. That has to do with the implementation of the Python `dict` class. Recall from earlier in our lesson that a Python `list` can change. A `dict`'s keys can only be immutable (unchangeable) objects."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Python `set`\n",
    "\n",
    "Python `set`s are less popular than `list`s and `dict`s but they are a fundamental data structure.\n",
    "\n",
    "Similar to a `list`, they group together a collection of heterogeneous objects. Two notable differences are that they are unordered, and they do not allow duplicates."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 3, 3, 4, 9]\n",
      "set([1, 3, 4, 9])\n"
     ]
    }
   ],
   "source": [
    "list_of_numbers = [1, 3, 3, 4, 9]\n",
    "set_of_numbers = {1, 3, 3, 4, 9}\n",
    "\n",
    "print list_of_numbers\n",
    "print set_of_numbers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Observe that the second data structure changed the original order and removed the duplicate `3`. This can be a useful feature if you have a list of items and want to know how many distinct items are in the list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "set([72, 42, 18, 39])\n"
     ]
    }
   ],
   "source": [
    "integers = [72, 42, 18, 42, 18, 72, 39, 72, 18, 72, 72, 72, 72, 18, 72, 39, 18, 18, 39, 42, 18, 39, 42, 18, 42]\n",
    "\n",
    "distinct_integers = set(integers)\n",
    "\n",
    "print distinct_integers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can't index into a set with square brackets [ ] but we can iterate through the items:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "72\n",
      "42\n",
      "18\n",
      "39\n"
     ]
    }
   ],
   "source": [
    "for i in distinct_integers:\n",
    "    print i"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A Python `set` is very much like a mathematical set. It can do the same mathematical operations. Much can be accomplished with this functionality."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "set(['python'])\n",
      "set(['python', 'tea', 'music', 'pb&j sandwiches', 'reading', 'ice cream', 'pizza'])\n",
      "set(['tea', 'reading', 'pb&j sandwiches'])\n",
      "set(['music', 'ice cream', 'pizza'])\n"
     ]
    }
   ],
   "source": [
    "person_a_likes = {'pizza', 'python', 'music', 'ice cream'}\n",
    "person_b_likes = {'tea', 'pb&j sandwiches', 'python', 'reading'}\n",
    "\n",
    "print person_a_likes.intersection(person_b_likes)\n",
    "print person_b_likes.union(person_a_likes)\n",
    "\n",
    "print person_b_likes.difference(person_a_likes)\n",
    "print person_a_likes.difference(person_b_likes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice the original `set`s are not altered by the `set` operations:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "set(['python', 'music', 'ice cream', 'pizza'])\n",
      "set(['python', 'tea', 'reading', 'pb&j sandwiches'])\n"
     ]
    }
   ],
   "source": [
    "print person_a_likes\n",
    "print person_b_likes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we wish we can add new items to the `set`, but like dictionary keys, those items must be Hashable."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "set(['python', 'music', 'sailing', 'ice cream', 'pizza'])\n"
     ]
    }
   ],
   "source": [
    "person_a_likes.add('sailing')\n",
    "\n",
    "print person_a_likes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[0;31m\u001b[0m\n",
      "\u001b[0;31mTypeError\u001b[0mTraceback (most recent call last)\n",
      "\u001b[0;32m<ipython-input-66-6ed707869b6c>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n",
      "\u001b[1;32m      1\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m----> 2\u001b[0;31m \u001b[0mperson_a_likes\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0madd\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m'mathematics'\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m'history'\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m'english'\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0m\n",
      "\u001b[0;31mTypeError\u001b[0m: unhashable type: 'list'\n"
     ]
    }
   ],
   "source": [
    "%%expect_exception TypeError\n",
    "\n",
    "person_a_likes.add(['mathematics', 'history', 'english'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Python `tuple`\n",
    "\n",
    "Python `tuple`s are simple immutable groupings of Python objects. They are similar to lists in that they are ordered, but they cannot be modified after they are created."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "person1 = ('John', 25, 'NYC')\n",
    "person2 = ('Jane', 28, 'SF')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "These simple `tuple`s represent names, ages, and cities. Here there is no special identifier indicating that the first item is a name, the second is an age, and the third is a city. This is a weakness of `tuple`s and can be a source of bugs but they make up for that in their simplicity.\n",
    "\n",
    "We can index into tuples like lists but we cannot modify their values."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "25\n",
      "(28, 'SF')\n"
     ]
    }
   ],
   "source": [
    "print person1[1]\n",
    "print person2[1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[0;31m\u001b[0m\n",
      "\u001b[0;31mTypeError\u001b[0mTraceback (most recent call last)\n",
      "\u001b[0;32m<ipython-input-69-1e8eadf96fae>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n",
      "\u001b[1;32m      1\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m----> 2\u001b[0;31m \u001b[0mperson1\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;36m35\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0m\n",
      "\u001b[0;31mTypeError\u001b[0m: 'tuple' object does not support item assignment\n"
     ]
    }
   ],
   "source": [
    "%%expect_exception TypeError\n",
    "\n",
    "person1[1] = 35"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A common use of `tuple`s is for returning multiple values from a function. For example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<type 'tuple'>\n",
      "(49, 343)\n"
     ]
    }
   ],
   "source": [
    "def squared_cubed(x):\n",
    "    squared = x * x\n",
    "    cubed = squared * x\n",
    "    \n",
    "    return squared, cubed\n",
    "\n",
    "calc = squared_cubed(7)\n",
    "\n",
    "print type(calc)\n",
    "print calc"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Observe that the `return` statement created a tuple from the variables `squared` and `cubed`.\n",
    "\n",
    "A power feature of tuples is *unpacking*:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "49\n",
      "343\n"
     ]
    }
   ],
   "source": [
    "xx, xxx = squared_cubed(7)\n",
    "\n",
    "print xx\n",
    "print xxx"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Python *unpacked* the returned `tuple` and assigned the first to `xx` and the second to `xxx`.\n",
    "\n",
    "What happens if we try to unpack a `tuple` to the wrong number of variables?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[0;31m\u001b[0m\n",
      "\u001b[0;31mValueError\u001b[0mTraceback (most recent call last)\n",
      "\u001b[0;32m<ipython-input-72-3194ab299fd3>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n",
      "\u001b[1;32m      1\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m----> 2\u001b[0;31m \u001b[0mxx\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mxxx\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mxxxx\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0msquared_cubed\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m7\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0m\n",
      "\u001b[0;31mValueError\u001b[0m: need more than 2 values to unpack\n"
     ]
    }
   ],
   "source": [
    "%%expect_exception ValueError\n",
    "\n",
    "xx, xxx, xxxx = squared_cubed(7)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Python `tuple` unpacking is powerful, but be careful about unpacking the wrong number of objects.\n",
    "\n",
    "**Question:** If I can create a `tuple` with this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(13, 3.14)\n"
     ]
    }
   ],
   "source": [
    "new_tuple = 13, 3.14\n",
    "\n",
    "print new_tuple"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And if I can unpack a tuple with this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "13\n",
      "3.14\n"
     ]
    }
   ],
   "source": [
    "unlucky_number, pi = new_tuple\n",
    "\n",
    "print unlucky_number\n",
    "print pi"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What will this do?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "20\n",
      "10\n"
     ]
    }
   ],
   "source": [
    "a = 10\n",
    "b = 20\n",
    "\n",
    "a, b = b, a\n",
    "\n",
    "print a\n",
    "print b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Comprehensions\n",
    "\n",
    "Python Comprehensions are a powerful and popular feature for creating new data structures. You will hear the term *list comprehensions* and *dictionary comprehensions*, and they both refer to the same concept of iterating through one data structure to make a new data structure.\n",
    "\n",
    "For example, if I start with the numbers from 1 to 10:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]\n"
     ]
    }
   ],
   "source": [
    "numbers = range(1, 11)\n",
    "\n",
    "print numbers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 4, 9, 16, 25, 36, 49, 64, 81, 100]\n"
     ]
    }
   ],
   "source": [
    "squares = [x * x for x in numbers]\n",
    "\n",
    "print squares"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We just created a list of squares without having to type them all out! Contrast that with similar code from earlier in this lesson.\n",
    "\n",
    "This is called a list comprehension.\n",
    "\n",
    "We can also do something similar with dictionaries:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{1: 1, 2: 4, 3: 9, 4: 16, 5: 25, 6: 36, 7: 49, 8: 64, 9: 81, 10: 100}\n"
     ]
    }
   ],
   "source": [
    "square_lut = {x: x * x for x in numbers}\n",
    "\n",
    "print square_lut"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Again, a much more convenient way of constructing a data structure.\n",
    "\n",
    "This can be more powerful when combined with custom functions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['1', '22', '333', '4444', '55555', '666666', '7777777', '88888888', '999999999', '10101010101010101010']\n"
     ]
    }
   ],
   "source": [
    "def silly_string(x):\n",
    "    \"\"\"repeat x digit x times\"\"\"\n",
    "    return x * str(x)\n",
    "\n",
    "print [silly_string(x) for x in numbers]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can also add filtering:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 3, 5, 7, 9]\n"
     ]
    }
   ],
   "source": [
    "def is_odd(x):\n",
    "    return x % 2\n",
    "\n",
    "odd_numbers = [x for x in numbers if is_odd(x)]\n",
    "\n",
    "print odd_numbers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can use list comprehensions to create a list of tuples:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(1, 1, 1), (3, 9, 27), (5, 25, 125), (7, 49, 343), (9, 81, 729)]\n"
     ]
    }
   ],
   "source": [
    "print [(x, x * x, x * x * x) for x in numbers if is_odd(x)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Upon learning about Python comprehensions it is tempting to use them to write increasingly complex code, but that is [discouraged](https://google.github.io/styleguide/pyguide.html#List_Comprehensions).\n",
    "\n",
    "Can you explain what this code does???"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "confusing = [(a, b, c) for a in range(15) for b in range(10) if is_odd(a) for c in range(5) if a + b + c < 42]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Please don't write code like that.\n",
    "\n",
    "When used properly, comprehensions can result in cleaner, more readable code. They can also be faster.\n",
    "\n",
    "Consider the task of finding the odd numbers from 1 to 1000. We will implement this using two methods and time them using Jupyter's `%timeit` magic. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "100 loops, best of 3: 2.05 ms per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "\n",
    "odd_numbers = []\n",
    "\n",
    "for i in xrange(10000):\n",
    "    if is_odd(i):\n",
    "        odd_numbers.append(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1000 loops, best of 3: 1.82 ms per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "\n",
    "odd_numbers = [x for x in xrange(10000) if is_odd(x)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Not only is the second approach easier to read, it is faster!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercises\n",
    "\n",
    "1. Create a dictionary that maps every integer from 1 to 1000 to its 4th power.\n",
    "1. Use a dictionary comprehension to invert that dictionary, mapping values to keys.\n",
    "1. Create a `list` that contains the items on your current grocery list.\n",
    "1. Create a `set` to identify your favorite hobbies and another `set` to identify someone else's hobbies. Using the two `set`s, what hobbies do you have in common? What hobbies do you not share?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exit Tickets\n",
    "\n",
    "1. What are the similarities and differences between a Python `list` and a `tuple`? Between a `list` and a `set`?\n",
    "1. What is a zero indexed array?\n",
    "1. What is a list comprehension? How do they help you code?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Copyright &copy; 2016 The Data Incubator.  All rights reserved.*"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}