Study material generated by AI from this openly licensed book (CC BY-NC 3.0). Not affiliated with or endorsed by the publisher.
Think Python, 2nd Edition, by Allen B. Downey, Green Tea Press, licensed under CC BY-NC 3.0. Read the original free
Chapter 11 · pp. 125–136
A dictionary is a built-in Python type that links keys to values. It is more flexible than a list because its keys are not limited to integers. This chapter shows how to build, search, count with, invert and speed up code using dictionaries. It also covers global variables and some tips for debugging programs that handle lots of data.
A dictionary is a mapping from keys to values. Each key is linked to exactly one value. One key and its value together are called a key-value pair, or an item. In a list the indices must be integers, but dictionary keys can be almost any type (p. 125).
You can make an empty dictionary with dict() or {}. Then add items with square brackets:
eng2sp = dict()
eng2sp['one'] = 'uno'
This maps the key 'one' to the value 'uno'. You can also build one all at once: {'one': 'uno', 'two': 'dos', 'three': 'tres'} (p. 125).
The order of items in a dictionary is unpredictable. When you print it, the pairs may appear in a different order than you typed them, and another computer may show yet another order (p. 126). This does not cause trouble, because you never use a position. You use the key. eng2sp['two'] always gives 'dos'. If you ask for a key that is missing, such as eng2sp['four'], Python raises a KeyError (p. 126).
len returns the number of key-value pairs. For a dictionary with three items, len(eng2sp) is 3 (p. 126).
The in operator checks keys only. 'one' in eng2sp is True, but 'uno' in eng2sp is False, since 'uno' is a value. To test values, call the values method and use in on the result: 'uno' in eng2sp.values() is True (p. 126).
The in operator is much faster on dictionaries than on lists. For a list, Python checks the elements one at a time, so the search time grows in proportion to the length. A dictionary uses a hashtable, so in takes about the same time however many items it holds. Looking up a word among 100,000 dictionary keys is no slower than among 100 (p. 126).
Suppose you want to count how often each letter appears in a string. You could use 26 separate variables or a 26-element list. A dictionary of counters is better, because you do not need to know ahead of time which letters will appear. You only store the ones that do (pp. 126–127).
The histogram function does this. It starts with an empty dictionary and loops over the string. For each character c:
c is not yet in d, set d[c] = 1 (first sighting).d[c] += 1.For 'brontosaurus' the result has 'o': 2 and 'b': 1 (p. 127).
The method get(key, default) returns the key's value if the key exists, and the default if it does not. With h = {'a': 1}, h.get('a', 0) gives 1 and h.get('c', 0) gives 0, with no error. Because of this, get(c, 0) + 1 works for new and old characters alike, so histogram can be written without an if statement (pp. 127–128).
A for loop over a dictionary visits its keys. In print_hist, for c in h gives each key, and h[c] gives the matching value. The order is arbitrary. To go through keys in order, loop over sorted(h). For 'parrot' this prints the keys as a, o, p, r, t (p. 128).
A lookup finds a value from a key: v = d[k]. A reverse lookup goes the other way, finding a key from a value. There are two problems. Several keys may share the same value, and there is no simple syntax, so you must search (p. 128).
reverse_lookup loops over every key k and returns the first one where d[k] == v. If the loop ends with no match, the function uses raise LookupError() to signal failure. You may add a message, such as LookupError('value does not appear in the dictionary') (pp. 128–129). In histogram('parrot'), reverse_lookup(h, 2) returns 'r', while reverse_lookup(h, 3) raises an error. A reverse lookup is much slower than a forward lookup, so avoid it on big dictionaries or when you need it often (p. 129).
Lists can be values in a dictionary. This is useful for inverting a dictionary: the old values become the new keys, and each new value is a list of the old keys. Lists are needed because several old keys may share one value (pp. 129–130).
For each key in d, look at its value val. If val is not in inverse, create the entry with a singleton list [key]. Otherwise append key to the list already there. Inverting the histogram of 'parrot' gives {1: ['a', 'p', 't', 'o'], 2: ['r']} (p. 130).
A hash is a function that turns a value into an integer. A dictionary uses this hash value to decide where to store a pair and where to find it again (p. 130). Keys must therefore be hashable. Immutable types such as integers, floats, strings and tuples are hashable. Mutable types such as lists and dictionaries are not. Trying d[[1,2,3]] = 'oops' gives a TypeError (pp. 130–132).
Some students think a list could be a key if they promise not to change it. The rule exists because Python cannot trust that promise. If a stored key changed, its hash would point to a different place. The dictionary might then hold two entries for the same key, or be unable to find one. Lists and dictionaries can still be values, and a tuple can replace a list when you need a sequence as a key (pp. 130–131).
The plain recursive fibonacci repeats work. The call graph for n=4 shows fibonacci(2) being computed more than once, and the repeats multiply as n grows, so the run time rises quickly (p. 131).
Memoization fixes this by storing results already computed. Each stored result is a memo. The memoized version begins with known = {0: 0, 1: 1}. When called, it returns known[n] if n is a key. Otherwise it computes fibonacci(n-1) + fibonacci(n-2), stores it in known[n], and returns it. This version is much faster (pp. 131–132).
A variable created outside any function lives in the __main__ frame and is called global. Any function can read it. Local variables disappear when their function ends, but globals persist between calls (p. 132). A common use is a flag, a boolean such as verbose = True that controls whether a function prints extra detail (p. 132).
Assigning to a global inside a function does not change it by default. In been_called = True, Python makes a new local variable, and the global stays False. The fix is to write global been_called first (p. 132). Similarly, count = count + 1 without a declaration causes an UnboundLocalError, because Python treats count as local and reads it before it has a value. Declaring global count fixes it (pp. 132–133).
If a global holds a mutable value, you can change its contents without a declaration. For example, known[2] = 1 works. Reassigning the name, as in known = dict(), needs global known (p. 133). Too many globals that change often make programs hard to debug (p. 133).
When data is large, checking output by hand does not work well. Four strategies help (pp. 133–134):
pprint module displays built-in types in a more readable way.d['x'] when 'x' is not a key in d? What does 'x' in d do instead?c in a dictionary d, using get and no if statement.'parrot' use lists as values?total = total + 5 is used on a global variable total and causes an error. Why, and how do you fix it?