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:

>>> inventory = {"apples": 430, "bananas": 312, "oranges": 525, "pears": 217}
>>> print(inventory)
{'pears': 217, 'apples': 430, 'oranges': 525, 'bananas': 312}

If someone buys all of the pears, we can remove the entry from the dictionary:

>>> del inventory["pears"]
>>> print(inventory)
{'apples': 430, 'oranges': 525, 'bananas': 312}

Or if we're expecting more pears soon, we might just change the value associated with pears:

>>> inventory["pears"] = 0
>>> print(inventory)
{'pears': 0, 'apples': 430, 'oranges': 525, 'bananas': 312}

A new shipment of bananas arriving could be handled like this:

>>> inventory["bananas"] += 200
>>> print(inventory)
{'pears': 0, 'apples': 430, 'oranges': 525, 'bananas': 512}

The len function also works on dictionaries; it returns the number of key:value pairs:

>>> len(inventory)
4

Dictionary methods

Dictionaries have a number of useful built-in methods.

The keys method returns what Python 3 calls a view of its underlying keys. A view object has some similarities to the range object we saw earlier --- it is a lazy promise, to deliver its elements when they're needed by the rest of the program. We can iterate over the view, or turn the view into a list like this:

for k in eng2sp.keys():   # The order of the k's is not defined
   print("Got key", k, "which maps to value", eng2sp[k])

ks = list(eng2sp.keys())
print(ks)

This produces this output:

Got key three which maps to value tres
Got key two which maps to value dos
Got key one which maps to value uno
['three', 'two', 'one']

It is so common to iterate over the keys in a dictionary that we can omit the keys method call in the for loop --- iterating over a dictionary implicitly iterates over its keys:

for k in eng2sp:
   print("Got key", k)

The values method is similar; it returns a view object which can be turned into a list:

>>> list(eng2sp.values())
['tres', 'dos', 'uno']

The items method also returns a view, which promises a list of tuples --- one tuple for each key:value pair:

>>> list(eng2sp.items())
[('three', 'tres'), ('two', 'dos'), ('one', 'uno')]

Tuples are often useful for getting both the key and the value at the same time while we are looping:

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

This produces:

Got three that maps to tres
Got two that maps to dos
Got one that maps to uno

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

>>> "one" in eng2sp
True
>>> "six" in eng2sp
False
>>> "tres" in eng2sp    # Note that 'in' tests keys, not values.
False

This method can be very useful, since looking up a non-existent key in a dictionary causes a runtime error:

>>> eng2esp["dog"]
Traceback (most recent call last):
  ...
KeyError: 'dog'

Aliasing and copying

As in the case of lists, because dictionaries are mutable, we need to be aware of aliasing. Whenever two variables refer to the same object, changes to one affect the other.

If we want to modify a dictionary and keep a copy of the original, use the copy method. For example, opposites is a dictionary that contains pairs of opposites:

>>> opposites = {"up": "down", "right": "wrong", "yes": "no"}
>>> alias = opposites
>>> copy = opposites.copy()  # Shallow copy

alias and opposites refer to the same object; copy refers to a fresh copy of the same dictionary. If we modify alias, opposites is also changed:

>>> alias["right"] = "left"
>>> opposites["right"]
'left'

If we modify copy, opposites is unchanged:

>>> copy["right"] = "privilege"
>>> opposites["right"]
'left'

Sparse matrices

We previously used a list of lists to represent a matrix. That is a good choice for a matrix with mostly nonzero values, but consider a sparse matrix like this one:

The list representation contains a lot of zeroes:

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]]

An alternative 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:

>>> 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:

>>> matrix[(0, 3)]
1

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:

>>> matrix[(1, 3)]
KeyError: (1, 3)

The get method solves this problem:

>>> matrix.get((0, 3), 0)
1

The first argument is the key; the second argument is the value get should return if the key is not in the dictionary:

>>> matrix.get((1, 3), 0)
0

get definitely improves the semantics of accessing a sparse matrix. Shame about the syntax.

Counting letters

In the exercises in Strings we wrote a function that counted the number of occurrences of a letter in a string. A more general version of this problem is to form a frequency table of the letters in the string, that is, how many times each letter appears.

Such a frequency table might be useful for compressing a text file. Because different letters appear with different frequencies, we can compress a file by using shorter codes for common letters and longer codes for letters that appear less frequently.

Dictionaries provide an elegant way to generate a frequency table:

>>> letter_counts = {}
>>> for letter in "Mississippi":
...     letter_counts[letter] = letter_counts.get(letter, 0) + 1
...
>>> letter_counts
{'M': 1, 's': 4, 'p': 2, 'i': 4}

We start with an empty dictionary. For each letter in the string, we find the current count (possibly zero) and increment it. At the end, the dictionary contains pairs of letters and their frequencies.

It might be more appealing to display the frequency table in alphabetical order. We can do that with the items and sort methods:

>>> letter_items = list(letter_counts.items())
>>> letter_items.sort()
>>> print(letter_items)
[('M', 1), ('i', 4), ('p', 2), ('s', 4)]

Notice in the first line we had to call the type conversion function list. That turns the promise we get from items into a list, a step that is needed before we can use the list's sort method.

Glossary

call graph

A graph consisting of nodes which represent function frames (or invocations), and directed edges (lines with arrows) showing which frames gave rise to other frames.

dictionary

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

immutable data value

A data value which cannot be modified. Assignments to elements or slices (sub-parts) of immutable values cause a runtime error.

key

A data item that is mapped to a value in a dictionary. Keys are used to look up values in a dictionary. Each key must be unique across the 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 abstract data type.

mutable data value

A data value which can be modified. The types of all mutable values are compound types. Lists and dictionaries are mutable; strings and tuples are not.

References