Slides

# 12. Dictionaries

## 12.1. Dictionaries

All of the compound data types we have studied in detail so far — strings,
lists, and tuples — are sequential collections. This means that the items in the collection are
ordered from left to right and they use integers as indices to access
the values they contain.

**Dictionaries** are a different kind of collection. They are Python’s
built-in **mapping type**. A map is an unordered, associative collection. The association, or mapping,
is from a **key**, which can be any immutable type,
to a **value**, which can be any Python data object.

As an example, we will create a dictionary to translate English words into
Spanish. For this dictionary, the keys are strings and the values will also be strings.

One way to create a dictionary is to start with the empty dictionary and add
**key-value pairs**. The empty dictionary is denoted `{}`

Activity: CodeLens 12.1.1 (chp12\_dict1)

The first assignment creates an empty dictionary named `eng2sp`. The other
assignments add new key-value pairs to the dictionary. The left hand side gives the dictionary and the key being associated. The right hand side gives the value being associated with that key.
We can print the current
value of the dictionary in the usual way.
The key-value pairs of the dictionary are separated by commas. Each pair
contains a key and a value separated by a colon.

The order of the pairs may not be what you expected. Python uses complex
algorithms, designed for very fast access, to determine where the
key-value pairs are stored in a dictionary.
For our purposes we can think of this ordering as unpredictable.

Another way to create a dictionary is to provide a list of key-value pairs
using the same syntax as the previous output.

Activity: CodeLens 12.1.2 (chp12\_dict2)

It doesn’t matter what order we write the pairs. The values in a dictionary are
accessed with keys, not with indices, so there is no need to care about
ordering.

Here is how we use a key to look up the corresponding value.

Activity: CodeLens 12.1.3 (chp12\_dict3)

The key `'two'` yields the value `'dos'`.

Note

This workspace is provided for your convenience. You can use this activecode window to try out anything you like.

**Check your understanding**

A dictionary is an unordered collection of key-value pairs.

* False
* Dictionaries associate keys with values but there is no assumed order for the entries.
* True
* Yes, dictionaries are associative collections meaning that they store key-value pairs.

What is printed by the following statements?

```python
mydict = {"cat":12, "dog":6, "elephant":23}
print(mydict["dog"])
```

* 12
* 12 is associated with the key cat.
* 6
* Yes, 6 is associated with the key dog.
* 23
* 23 is associated with the key elephant.
* Error, you cannot use the index operator with a dictionary.
* The [ ] operator, when used with a dictionary, will look up a value based on its key.

## 12.2. Dictionary Operations

The `del` statement removes a key-value pair from a dictionary. For example,
the following dictionary contains the names of various fruits and the number of
each fruit in stock. If someone buys all of the pears, we can remove the entry from the dictionary.

Activity: CodeLens 12.2.1 (ch12\_dict4)

Dictionaries are also mutable. As we’ve seen before with lists, this means that the dictionary can
be modified by referencing an association on the left hand side of the assignment statement. In the previous
example, instead of deleting the entry for `pears`, we could have set the inventory to `0`.

Activity: CodeLens 12.2.2 (ch12\_dict4a)

Similarily,
a new shipment of 200 bananas arriving could be handled like this.

Activity: CodeLens 12.2.3 (ch12\_dict5)

Notice that there are now 512 bananas—the dictionary has been modified. Note also that the `len` function also works on dictionaries. It returns the number
of key-value pairs:

**Check your understanding**

What is printed by the following statements?

```python
mydict = {"cat":12, "dog":6, "elephant":23}
mydict["mouse"] = mydict["cat"] + mydict["dog"]
print(mydict["mouse"])
```

* 12
* 12 is associated with the key cat.
* 0
* The key mouse will be associated with the sum of the two values.
* 18
* Yes, add the value for cat and the value for dog (12 + 6) and create a new entry for mouse.
* Error, there is no entry with mouse as the key.
* Since the new key is introduced on the left hand side of the assignment statement, a new key-value pair is added to the dictionary.

## 12.3. Dictionary Methods

Dictionaries have a number of useful built-in methods.
The following table provides a summary and more details can be found in the
[Python Documentation](http://docs.python.org/py3k/library/stdtypes.html#mapping-types-dict).

| Method | Parameters | Description |
| --- | --- | --- |
| keys | none | Returns a view of the keys in the dictionary |
| values | none | Returns a view of the values in the dictionary |
| items | none | Returns a view of the key-value pairs in the dictionary |
| get | key | Returns the value associated with key; None otherwise |
| get | key,alt | Returns the value associated with key; alt otherwise |

The `keys` method returns what Python 3 calls a **view** of its underlying keys.
We can iterate over the view or turn the view into a
list by using the `list` conversion function.

```python
inventory = {'apples': 430, 'bananas': 312, 'oranges': 525, 'pears': 217}

for akey in inventory.keys():     # the order in which we get the keys is not defined
   print("Got key", akey, "which maps to value", inventory[akey])

ks = list(inventory.keys())
print(ks)
```

It is so common to iterate over the keys in a dictionary that you can
omit the `keys` method call in the `for` loop — iterating over
a dictionary implicitly iterates over its keys.

```python
inventory = {'apples': 430, 'bananas': 312, 'oranges': 525, 'pears': 217}

for k in inventory:
   print("Got key", k)
```

As we saw earlier with strings and lists, dictionary methods use dot notation,
which specifies the name of the method to the right of the dot and the name of
the object on which to apply the method immediately to the left of the dot. The empty
parentheses in the case of `keys` indicate that this method takes no parameters.

The `values` and `items` methods are similar to `keys`. They return view objects which can be turned
into lists or iterated over directly. Note that the items are shown as tuples containing the key and the associated value.

```python
inventory = {'apples': 430, 'bananas': 312, 'oranges': 525, 'pears': 217}

print(list(inventory.values()))
print(list(inventory.items()))

for (k,v) in inventory.items():
    print("Got", k, "that maps to", v)

for k in inventory:
    print("Got", k, "that maps to", inventory[k])
```

Note that tuples are often useful for getting both the key and the value at the same
time while you are looping. The two loops do the same thing.

The `in` and `not in` operators can test if a key is in the dictionary:

```python
inventory = {'apples': 430, 'bananas': 312, 'oranges': 525, 'pears': 217}
print('apples' in inventory)
print('cherries' in inventory)

if 'bananas' in inventory:
    print(inventory['bananas'])
else:
    print("We have no bananas")
```

This operator can be very useful since looking up a non-existent key in a
dictionary causes a runtime error.

The `get` method allows us to access the value associated with a key, similar to the `[ ]` operator.
The important difference is that `get` will not cause a runtime error if the key is not present. It
will instead return None. There exists a variation of `get` that allows a second parameter that serves as an alternative return value
in the case where the key is not present. This can be seen in the final example below. In this case, since “cherries” is not a key, return 0 (instead of None).

```python
inventory = {'apples': 430, 'bananas': 312, 'oranges': 525, 'pears': 217}

print(inventory.get("apples"))
print(inventory.get("cherries"))

print(inventory.get("cherries", 0))
```

Note

This workspace is provided for your convenience. You can use this activecode window to try out anything you like.

**Check your understanding**

What is printed by the following statements?

```python
mydict = {"cat":12, "dog":6, "elephant":23, "bear":20}
keylist = list(mydict.keys())
keylist.sort()
print(keylist[3])
```

* cat
* keylist is a list of all the keys which is then sorted. cat would be at index 1.
* dog
* keylist is a list of all the keys which is then sorted. dog would be at index 2.
* elephant
* Yes, the list of keys is sorted and the item at index 3 is printed.
* bear
* keylist is a list of all the keys which is then sorted. bear would be at index 0.

What is printed by the following statements?

```python
mydict = {"cat":12, "dog":6, "elephant":23, "bear":20}
answer = mydict.get("cat") // mydict.get("dog")
print(answer)
```

* 2
* get returns the value associated with a given key so this divides 12 by 6.
* 0.5
* 12 is divided by 6, not the other way around.
* bear
* Take another look at the example for get above. get returns the value associated with a given key.
* Error, divide is not a valid operation on dictionaries.
* The integer division operator is being used on the values returned from the get method, not on the dictionary.

What is printed by the following statements?

```python
mydict = {"cat":12, "dog":6, "elephant":23, "bear":20}
print("dog" in mydict)
```

* True
* Yes, dog is a key in the dictionary.
* False
* The in operator returns True if a key is in the dictionary, False otherwise.

What is printed by the following statements?

```python
mydict = {"cat":12, "dog":6, "elephant":23, "bear":20}
print(23 in mydict)
```

* True
* 23 is a value in the dictionary, not a key.
* False
* Yes, the in operator returns True if a key is in the dictionary, False otherwise.

What is printed by the following statements?

```python
total = 0
mydict = {"cat":12, "dog":6, "elephant":23, "bear":20}
for akey in mydict:
   if len(akey) > 3:
      total = total + mydict[akey]
print(total)
```

* 18
* Add the values that have keys greater than 3, not equal to 3.
* 43
* Yes, the for statement iterates over the keys. It adds the values of the keys that have length greater than 3.
* 0
* This is the accumulator pattern. total starts at 0 but then changes as the iteration proceeds.
* 61
* Not all the values are added together. The if statement only chooses some of them.

## 12.4. Aliasing and Copying

Because dictionaries are mutable, you need to be aware of aliasing (as we saw with lists). Whenever
two variables refer to the same dictionary object, changes to one affect the other.
For example, `opposites` is a dictionary that contains pairs
of opposites.

```python
opposites = {'up': 'down', 'right': 'wrong', 'true': 'false'}
alias = opposites

print(alias is opposites)

alias['right'] = 'left'
print(opposites['right'])
```

As you can see from the `is` operator, `alias` and `opposites` refer to the same object.

If you want to modify a dictionary and keep a copy of the original, use the dictionary
`copy` method. Since *acopy* is a copy of the dictionary, changes to it will not effect the original.

```python
acopy = opposites.copy()
acopy['right'] = 'left'    # does not change opposites
```

**Check your understanding**

What is printed by the following statements?

```python
mydict = {"cat":12, "dog":6, "elephant":23, "bear":20}
yourdict = mydict
yourdict["elephant"] = 999
print(mydict["elephant"])
```

* 23
* mydict and yourdict are both names for the same dictionary.
* None
* The dictionary is mutable so changes can be made to the keys and values.
* 999
* Yes, since yourdict is an alias for mydict, the value for the key elephant has been changed.
* Error, there are two different keys named elephant.
* There is only one dictionary with only one key named elephant. The dictionary has two different names, mydict and yourdict.

## 12.5. Sparse Matrices

A matrix is a two dimensional collection, typically thought of as having rows and columns of data. One of the easiest ways to create a matrix is to use a list of lists. For example, consider the matrix shown below.

![sparse matrix](../_images/sparse.png)

We can represent this collection as five rows, each row having five columns. Using a list of lists representation, we will have a list of five items, each of which is a list of five items. The
outer items represent the rows and the items in the nested lists represent the data in each column.

```python
matrix = [[0, 0, 0, 1, 0],
          [0, 0, 0, 0, 0],
          [0, 2, 0, 0, 0],
          [0, 0, 0, 0, 0],
          [0, 0, 0, 3, 0]]
```

One thing that you might note about this example matrix is that there are many items that are zero. In fact, only three of the
data values are nonzero. This type of matrix has a special name. It is called a [sparse matrix](http://en.wikipedia.org/wiki/Sparse_matrix).

Since there is really no need to store all of the zeros, the list of lists representation is considered to be inefficient.
An alternative representation is to use a dictionary. For the keys, we can use tuples that
contain the row and column numbers. Here is the dictionary representation of
the same matrix.

```python
matrix = {(0, 3): 1, (2, 1): 2, (4, 3): 3}
```

We only need three key-value pairs, one for each nonzero element of the matrix.
Each key is a tuple, and each value is an integer.

To access an element of the matrix, we could use the `[]` operator:

```python
matrix[(0, 3)]
```

Notice that the syntax for the dictionary representation is not the same as the
syntax for the nested list representation. Instead of two integer indices, we
use one index, which is a tuple of integers.

There is one problem. If we specify an element that is zero, we get an error,
because there is no entry in the dictionary with that key.
The alternative version of the `get` method solves this problem.
The first argument will be the key. The second argument is the value `get` should
return if the key is not in the dictionary (which would be 0 since it is sparse).

```python
matrix = {(0, 3): 1, (2, 1): 2, (4, 3): 3}
print(matrix.get((0,3)))

print(matrix.get((1, 3), 0))
```

Lab

* [Counting Letters](../Labs/lab12_01.html) In this guided lab exercise we will work
  through a problem solving exercise that will use dictionaries to generalize the solution
  to counting the occurrences of all letters in a string.

Lab

* [Letter Count Histogram](../Labs/lab12_02.html) Combine the previous lab with the histogram example.

## 12.6. Glossary

dictionary
:   A collection of key-value pairs that maps from keys to values. The keys
    can be any immutable type, and the values can be any type.

key
:   A data item that is *mapped to* a value in a dictionary. Keys are used
    to look up values in a dictionary.

key-value pair
:   One of the pairs of items in a dictionary. Values are looked up in a
    dictionary by key.

mapping type
:   A mapping type is a data type comprised of a collection of keys and
    associated values. Python’s only built-in mapping type is the
    dictionary. Dictionaries implement the
    [associative array](http://en.wikipedia.org/wiki/Associative_array)
    abstract data type.

## 12.7. Exercises

1. Write a program that allows the user to enter a string. It then prints a
   table of the letters of the alphabet in alphabetical order which occur in
   the string together with the number of times each letter occurs. Case should
   be ignored. A sample run of the program might look this this:

```python
   Please enter a sentence: ThiS is String with Upper and lower case Letters.
   a  2
   c  1
   d  1
   e  5
   g  1
   h  2
   i  4
   l  2
   n  2
   o  1
   p  2
   r  4
   s  5
   t  5
   u  1
   w  2
   $
   ```

```python
   x = input("Enter a sentence")

x = x.lower()   # convert to all lowercase

alphabet = 'abcdefghijklmnopqrstuvwxyz'

letter_count = {} # empty dictionary
   for char in x:
       if char in alphabet: # ignore any punctuation, numbers, etc
           if char in letter_count:
               letter_count[char] = letter_count[char] + 1
           else:
               letter_count[char] = 1

keys = letter_count.keys()
   for char in sorted(keys):
       print(char, letter_count[char])
   ```

[Show Comments](#disqus_thread)

2. > Give the Python interpreter’s response to each of the following from a
   > continuous interpreter session:
   >
   > 1. ```python
   >    >>> d = {'apples': 15, 'bananas': 35, 'grapes': 12}
   >    >>> d['banana']
   >    ```
   > 2. ```python
   >    >>> d['oranges'] = 20
   >    >>> len(d)
   >    ```
   > 3. ```python
   >    >>> 'grapes' in d
   >    ```
   > 4. ```python
   >    >>> d['pears']
   >    ```
   > 5. ```python
   >    >>> d.get('pears', 0)
   >    ```
   > 6. ```python
   >    >>> fruits = d.keys()
   >    >>> fruits.sort()
   >    >>> print(fruits)
   >    ```
   > 7. ```python
   >    >>> del d['apples']
   >    >>> 'apples' in d
   >    ```

Be sure you understand why you get each result. Then apply what you
   have learned to fill in the body of the function below, and add code for
   the tests indicated:

```python
   def add_fruit(inventory, fruit, quantity=0):
        pass

# make these tests work...
   new_inventory = {}
   add_fruit(new_inventory, 'strawberries', 10)
   #  test that 'strawberries' in new_inventory
   #  test that new_inventory['strawberries'] is 10
   add_fruit(new_inventory, 'strawberries', 25)
   #  test that new_inventory['strawberries'] is now 35)
   ```

3. Write a program called `alice_words.py` that creates a text file named
   `alice_words.txt` containing an alphabetical listing of all the words, and the
   number of times each occurs, in the text version of Alice’s Adventures in Wonderland.
   (You can obtain a free plain text version of the book, along with many others, from
   <http://www.gutenberg.org>.) The first 10 lines of your output file should look
   something like this

> | Word | Count |
   > | --- | --- |
   > | a | 631 |
   > | a-piece | 1 |
   > | abide | 1 |
   > | able | 1 |
   > | about | 94 |
   > | above | 3 |
   > | absence | 1 |
   > | absurd | 2 |

How many times does the word, `alice`, occur in the book? If you are writing this
   in the activecode window simply print out the results rather than write them to a file.

```python
   f = open('alice.txt', 'r')

count = {}

for line in f:
       for word in line.split():

# remove punctuation
           word = word.replace('_', '').replace('"', '').replace(',', '').replace('.', '')
           word = word.replace('-', '').replace('?', '').replace('!', '').replace("'", "")
           word = word.replace('(', '').replace(')', '').replace(':', '').replace('[', '')
           word = word.replace(']', '').replace(';', '')

# ignore case
           word = word.lower()

# ignore numbers
           if word.isalpha():
               if word in count:
                   count[word] = count[word] + 1
               else:
                   count[word] = 1

keys = count.keys()
   keys.sort()

# save the word count analysis to a file
   out = open('alice_words.txt', 'w')

for word in keys:
       out.write(word + " " + str(count[word]))
       out.write('\n')

print("The word 'alice' appears " + str(count['alice']) + " times in the book.")
   ```

[Show Comments](#disqus_thread)

4. What is the longest word in Alice in Wonderland? How many characters does it have?

5. Here’s a table of English to Pirate translations

| English | Pirate |
   | --- | --- |
   | sir | matey |
   | hotel | fleabag inn |
   | student | swabbie |
   | boy | matey |
   | madam | proud beauty |
   | professor | foul blaggart |
   | restaurant | galley |
   | your | yer |
   | excuse | arr |
   | students | swabbies |
   | are | be |
   | lawyer | foul blaggart |
   | the | th’ |
   | restroom | head |
   | my | me |
   | hello | avast |
   | is | be |
   | man | matey |

Write a function named `translator` that takes a parameter containing a sentence in English
   (no punctuation and all words in lowercase) and returns that sentence translated to Pirate.

For example, the sentence “hello there students” should be translated to “avast there swabbies”.

```python
   def translator(english):

pirate = {}
     pirate['sir'] = 'matey'
     pirate['hotel'] = 'fleabag inn'
     pirate['student'] = 'swabbie'
     pirate['boy'] = 'matey'
     pirate['restaurant'] = 'galley'
     pirate['hello'] = 'avast'
     pirate['students'] = 'swabbies'

# Complete the function

=====
   from unittest.gui import TestCaseGui

class myTests(TestCaseGui):

def testOne(self):
           self.assertEqual(translator("hello there students"),'avast there swabbies','translator("hello there students") yields "avast there swabbies"')
           self.assertEqual(translator("the boy stayed in the hotel"),'the matey stayed in the fleabag inn','translator("the boy stayed in the hotel") yields "the matey stayed in the fleabag inn"')

myTests().main()
   ```

```python
   def translator(sentence):

psentence = []
     words = sentence.split()
     for aword in words:
        if aword in pirate:
            psentence.append(pirate[aword])
        else:
            psentence.append(aword)

return " ".join(psentence)
   ```

[Show Comments](#disqus_thread)