{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Dictionaries\n", "\n", "## Motivation\n", "\n", "Lists and tuples, as we've seen, allow us to store multiple values in\n", "a single object. Recall that these are both examples of ordered sequences,\n", "e.g., the items occur in a specific order. With both lists and tuples,\n", "we access the individual elements using an index, which is an integer\n", "from $0, 1, \\ldots, n-1$, where $n$ is the number of elements in the\n", "sequence. For instance, suppose we have the following list:\n", "```\n", "names = [\"Bill\", \"Bob\", \"Alice\", \"Sue\"]\n", "```\n", "then `\"Bill\"` is at index 0, `\"Bob\"` is at index 1, and `\"Alice\"` is\n", "at index 2.\n", "\n", "While lists and tuples can be extremely helpful, there is often\n", "a need to associate multiple things with one another. For example,\n", "suppose you wish to count how frequently each of the letters\n", "of the alphabet occurs in a certain document. In this example, you would\n", "want to store 26 counts, one for each of a, b, ..., z. With the techniques\n", "we know now, there are a few possible ways to handle this (listed from\n", "best to worst)\n", "\n", "1. Keep track of two lists, with the values in each corresponding to\n", " one another. One list would contain the letters\n", " of the alphabet. The other list would contain the counts, so the value\n", " at index 0 in the counts list would store the count for the letter\n", " at index 0 in the letters list, etc.\n", "1. Simply store the counts in a list and assume some ordering, such\n", " as assuming `'a'` is at index 0, `'b'` at index 1, etc. This type of approach\n", " is often difficult or impossible to manage fully within code.\n", "2. Create 26 different count variables. This would be a completely valid\n", " approach for just a couple of values, but for more than a couple,\n", " this would be a very bad approach. It would result in massive amounts\n", " of repeated code and code that cannot be easily adapted to other similar\n", " tasks.\n", "\n", "None of these are great options to address this type of problem, ranging\n", "from clunky to downright atrocious. Instead, it'd be better to use a single\n", "object to store all of these counts that associated the letter with the count.\n", "\n", "## Basic Idea\n", "Thankfully, Python has an additional\n", "data structure designed to solve problems such as these. In Python, this\n", "is a *dictionary*, which stores key-value pairs. Essentially, this is like\n", "a list, but instead of using consecutive integer indices, other values\n", "such as strings, tuples, etc. can be the index (or in dictionary terms as the\n", "*key*. Keys can be any immutable type (technically, the key can be any\n", "*hashable* type, but that goes beyond the scope of our discussion). Note that\n", "keys must be unique (the same key cannot occur more than once in the dictionary).\n", "For each key there is some *value* stored, which can be any type:\n", "single value, list, another dictionary, etc.\n", "\n", "\n", "## Creating Dictionaries\n", "With lists, we used empty brackets, `[]` to create an empty list.\n", "To create an empty dictionary, we use `{}`. Alternatively, we can also use\n", "`dict()`, which is why you should never name your dictionary `dict`." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "dct1 = {}\n", "dct2 = dict()\n", "print(type(dct1))\n", "print(type(dct2))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "To create a dictionary with some key-value pairs already in it, we\n", "list them between the brackets in the general form:\n", "```\n", "dct = {keyA: valueA, keyB: valueB, keyC: valueC}\n", "```" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "For instance, suppose we want to create a dictionary to store the following\n", "population data:\n", "\n", "* Grand Rapids: 200,217\n", "* Holland: 33,327\n", "* Lansing: 118,427\n", "* Detroit: 672,662" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "populations = {'Grand Rapids': 200217, 'Holland': 33327, 'Lansing': 118427, 'Detroit': 672662}\n", "print(populations)\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Dictionaries are frequently used because:\n", "1. They are very fast. Because of the underlying way in which dictionaries\n", " are stored, checking if a specific key is in a dictionary takes a constant\n", " amount of time (meaning it does not have to go through all of the keys,\n", " so the time it takes is not dependent on the number of items in the dictionary).\n", "2. They are very convenient. It is very common to need to store values that\n", " correspond to one another and dictionaries are exactly suited to this task\n", " and often much cleaner than trying to handle implementing a solution\n", " with separate pieces correctly.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Dictionary Operations\n", "\n", "As with the other main types of objects we've seen for storing\n", "multiple data values, dictionaries have a variety of built-in operations\n", "available.\n", "\n", "### Accessing Values\n", "\n", "As with lists, tuples, and strings, we can access values in dictionaries with `[]`.\n", "However, instead of using an integer index, we now use the key as the index.\n", "For instance, to get the population of Grand Rapids:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "popGR = populations['Grand Rapids']\n", "print(popGR)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In the above, the key was in quotes because the key was a string.\n", "You can use other types as well. For instance, consider\n", "the following dictionary which holds hypothetical student grades.\n", "Each key is tuple of the form `(lastName, firstName)`\n", "and the value associated with each key is a list with the grades for\n", "that student." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "grades = {('Bob', 'Billy'):[100, 80, 80],\n", " ('Patricks', 'Patty'):[50, 65, 60],\n", " ('Smith', 'Summer'):[75,90,90]}\n", "\n", "print(grades[('Patricks','Patty')])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "If the key is not in the dictionary, then the code will raise a `KeyError`.\n", "Sometimes this is helpful as it informs you that there is an issue with the\n", "key. " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "populations['Ann Arbor']" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In other cases, though, it is easier to denote a specific value\n", "that you want when the key does not exist. For instance, suppose\n", "a dictionary contains the number of copies of a book that a library has.\n", "Rather than getting an error, it's possible that we might just want the\n", "result to be the value 0 if the book is not in the dictionary. In\n", "these cases, we can use the `get(key, default)` method, which takes\n", "both the desired key and the default value to return if the key is\n", "not in the dictionary." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "library = {'To Kill a Mockingbird':3, 'East of Eden':2, 'Brave New World':2}\n", "copies = library.get('The Great Gatsby', 0)\n", "print(copies)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Accessing All Keys/Values\n", "\n", "While indexing notation, `dictname[key]` allows us to access\n", "the value for a specific key, there are also methods available\n", "that allow us to access all of the dictionary contents. Specifically,\n", "\n", "* `keys()` -> returns all of the keys in the dictionary\n", "* `values()` -> returns all of the values in the dictionary\n", "* `items()` -> returns all of `(key,value)` pairs as tuples\n", "\n", "#### Examples" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "print('----- keys -----')\n", "print(grades.keys())\n", "print('----- values -----')\n", "print(grades.values())\n", "print('----- items -----')\n", "print(grades.items())" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Each of these are actually special types (similar to what\n", "you get when you call the `range` function. We can see that\n", "by calling the `type` function. " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "type(grades.keys())" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Similarly to `range`, we can iterate (with a for loop) through\n", "the results of `keys()`, `values()`, and `items()` directly\n", "([see iterating section](#iterating)).\n", "However, they can be easily converted to a list by calling the `list`\n", "function if an explicit list is needed." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "keylist = list(grades.keys())\n", "print(keylist)\n", "print(type(keylist))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Modifying Dictionaries\n", "Dictionaries are *mutable*, meaning it is possible\n", "to change what is in the dictionary. We can change\n", "dictionaries in one of a few ways:\n", "\n", "* adding new keys\n", " * `dictname[newkey] = new_key_value`\n", "* modifying values to existing keys\n", " * access current value for that key\n", " * assign new value to `dictname[key]`\n", "* removing keys\n", " * `dictname.pop(key)`\n", " \n", "#### Examples\n", "\n", "##### Adding New Keys" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "library = {'To Kill a Mockingbird':3, 'East of Eden':2, 'Brave New World':2}\n", "library['Jurassic Park'] = 2\n", "print(library)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "##### Modifying Values" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "library['To Kill a Mockingbird'] -= 1\n", "library['East of Eden'] += 1\n", "print(library)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "library.pop('To Kill a Mockingbird')\n", "print(library)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Containment\n", "\n", "As with tuples, lists, strings, etc. it is easy to check\n", "if a dictionary contains a specific key using `key in dictname`.\n", "If the key is in the dictionary, it will evaluate to `True`, otherwise\n", "it will evaluate to `False`. As with other scenarios, this is often\n", "used in an `if` statement. Note that this can be, and is often, used\n", "to first check if a dictionary contains a key prior to attempting to\n", "modfiy it's value.\n", "\n", "##### Example" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "print('To Kill a Mockingbird' in library)\n", "print('East of Eden' in library)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Iterating Through Dictionaries\n", "\n", "Often, we want to loop through a dictionary.\n", "We can loop directly through a dictionary with a for loop\n", "of the form\n", "```\n", "for key in dictname:\n", " # do something\n", "```\n", "This will loop through the keys, so to access the values\n", "inside the loop we would need to index into the dictionary\n", "with `dictname[key]` or `dictname.get(key)`." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "for city in populations:\n", " print(city, populations[city])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "It's also possible to loop through just the values (by looping through `dictname.values()`)\n", "or loop through tuples of the key-value pairs (by looping through `dictname.items()`)." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "for val in populations.values():\n", " print(val)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Sorting Dictionaries\n", "Dictionaries in python were historically *unordered*, meaning the key-value pairs were not \n", "guaranteed to occur in any order (regardless of the order they are added\n", "to the dictionary). However, as of new versions of Python (3.7+), dictionaries\n", "will be ordered in the order the items are inserted. If we want to loop through\n", "a dictionary alphabetically or numerically, we can simply call `sorted(dictname)`\n", "which returns a sorted list of the keys. Note that it is not in-place\n", "(it doesn't actually modify the underlying dictionary).\n", "By default calling `sorted` will sort by keys. To sort\n", "by values instead, we can pass a function to the optional `key`\n", "argument to sorted and it will instead sort by whatever values\n", "this function returns. Thankfully, we already have such a function -- `get`,\n", "e.g. `sorted(dictname, key=dictname.get)`.\n", "\n", "#### Examples" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "print(sorted(populations))\n", "print(sorted(populations, key=populations.get))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Relevant Functions\n", "As with lists, tuples, etc. there are also built-in functions that apply\n", "to dictionaries. The primary functions used are:\n", "\n", "* `min(dictname)` -> returns the minimum key in the dictionary\n", "* `max(dictname)` -> returns the maximum key in the dictionary\n", "* `len(dictname)` -> returns the number of key-value pairs in the dictionary\n", "\n", "#### Examples" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "print(min(populations))\n", "print(max(populations))\n", "print(len(populations))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Note that `min` and `max` only looks at the keys, not the values.\n", "To get key associated with the min (or max) value,\n", "we can pass a function that gets the value we want to look for\n", "min and max of\n", "to the optional keyword argument `key` in the `min` (or `max`)\n", "functions. Thankfully, we already have such a function -- `get`.\n", "This is a unique task to do (and very \"pythonic\"), that we can\n", "actually pass around functions the same way we can pass around\n", "lists or values. To make sure that it knows what we want to\n", "run `get` on, we specifically indicate our dictionary, e.g.\n", "`min(dictname, key=dictname.get)`" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "key_of_min = min(populations, key=populations.get)\n", "print(key_of_min)\n", "key_of_max = max(populations, key=populations.get)\n", "print(key_of_max)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Counter\n", "\n", "By far one of the most common use cases for dictionaries is to\n", "keep track of the number of times each number, word, character, etc.\n", "that appears in a list, string, etc. \n", "This is such a popular task, that python has a built-in mechanism\n", "to compute the dictionary of counts, called a `Counter`. Like\n", "we saw with the random functions though, `Counter` is in a separate\n", "module called collections. So, to use it we first have to `import collections` and\n", "call it with `collections.Counter(items)`" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import collections" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "A `Counter` is actually a special type of dictionary, so it's more\n", "than just a function, it's known as a constructor. But,\n", "that difference doesn't matter much -- we call it exactly like\n", "a function. We can create a Counter from anything that is *iterable*,\n", "which just means anything we can loop through. This includes all of\n", "sequences we've talked about (strings, tuples, lists), as well\n", "as things like the result of `range` that are not technically lists.\n", "That being said, the vast majority of times you would use a counter,\n", "you will create it from either a string, a tuple, or a list.\n", "\n", "### Examples: Creating Counters\n", "\n", "#### From Strings\n", "From strings, it create a Counter object (e.g. special dictionary)\n", "with counts of each of the characters and how frequently they occur." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "char_counts = collections.Counter('abracadabra alakazam')\n", "print(char_counts)\n", "print(type(char_counts))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### From Lists\n", "When called with a list as the argument, it creates a Counter object\n", "(e.g. special dictionary) with each item in the list and the number\n", "of times that item occurs. " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "foods = ['bacon', 'eggs', 'ham', 'eggs', 'spam', 'orange', 'apple', 'apple', 'bacon', 'bacon']\n", "food_counts = collections.Counter(foods)\n", "print(food_counts)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Creating a Counter from tuples works exactly like creating one from lists." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### From Other\n", "As mentioned above, it's possible (though unlikely to be wanted)\n", "to create a Counter from other iterable things like the\n", "result of `range`. For example," ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "count_range = collections.Counter(range(0,10,2))\n", "print(count_range)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Counter vs Dictionaries\n", "Since `Counter` objects are special types of dictionaries,\n", "they have all of the same methods that dictionaries have,\n", "can be looped through like dictionaries,\n", "and the same built-in functions work on Counters as well.\n", "\n", "The most noticeable difference in behavior is what happens if there\n", "is a missing key. Whereas with regular dictionaries,\n", "using the `dictname[key]` notation would raise a `KeyError`\n", "when used with a missing key, a `Counter` will automatically\n", "give the value 0, as it recognizes that this is just 0\n", "occurrences of the item." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "print(food_counts['kiwi'])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In addition to behaving differently with non-existent keys,\n", "`Counter` objects have a few additional methods beyond regular\n", "dictionaries. Two of the most commonly used ones are:\n", "* `elements()` -> returns an iterator (something you can loop through)\n", " over all of the elements, each element repeated count times, where\n", " count is the count for that element. A list can be created from this\n", " using `list()`\n", "* `most_common(n)` -> returns list of n most common elements and their\n", " counts (list of tuples `(element,count)`) ordered from most common\n", " to least common" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "for food in food_counts.elements():\n", " print(food)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "print(food_counts.most_common(3))" ] } ], "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.8.6" } }, "nbformat": 4, "nbformat_minor": 4 }