Index
Contents
Chapter 3 · Solutions

Containers: Solutions

1. Timing deque vs. list at different sizes

In deque_timing.py, change n from 20_000 to 2_000, change the printed comparison to deque_time < list_time, and run the timing again. Does deque_time < list_time still hold? Change n to 200_000 and try again. The list version takes several seconds at that size, and much longer on a slow machine. Explain what changes about the comparison as n grows.

Where to look

deque compares the cost of operations at the left end of a list and of a deque. Time a loop of insert(0, x) and pop(0) calls against appendleft() and popleft(), once at each size. Count how many elements each left-end operation on a list must move, and compare that with the deque version as n grows.

The shape
# The shape of exercise_1.py
from collections import deque
from timeit import timeit
from benchmark import report

def list_left_ops():
    ...

def deque_left_ops():
    ...
Done when

your modified deque_timing.py prints True at n = 2_000 and again at n = 200_000, and your explanation says how many elements one left-end operation moves in each container as n grows, and what that does to the gap between the two times.

Solution
# exercise_1.py
from collections import deque
from timeit import timeit
from benchmark import report

n = 2_000  # then 200_000

def list_left_ops():
    items = []
    for i in range(n):
        items.insert(0, i)
    while items:
        items.pop(0)

def deque_left_ops():
    items = deque()
    for i in range(n):
        items.appendleft(i)
    while items:
        items.popleft()

list_time = timeit(list_left_ops, number=1)
deque_time = timeit(deque_left_ops, number=1)
report(list_ops=list_time, deque_ops=deque_time)
print(deque_time < list_time)
#: True

deque_time < list_time holds at n = 2_000, 20_000, and 200_000. But the margin grows with n. Each list.insert(0, x) or list.pop(0) shifts every remaining element, so the whole loop costs O(n²). Each deque operation is O(1), so the deque loop costs O(n). At a handful of items the constant-factor overhead of a deque makes the two times nearly equal, though by n = 2_000 the deque finishes several times faster. At large n the list’s quadratic term dominates, so the list falls further behind the deque as n grows.

Before you move on, name what separates your attempt from this one: a different design, a detail, or an equivalent alternative.

2. defaultdict(int) for counting

In defaultdict.py, replace defaultdict(list) with defaultdict(int), change the loop to count occurrences of each kind instead of collecting names, and print the result.

Where to look

defaultdict shows a factory called to create a missing value. The factory here is int, so ask what int() returns when called with no arguments. With that default, the loop can add to a key before it exists.

Done when

your file prints {'dog': 2, 'cat': 1} (or defaultdict(<class 'int'>, {'dog': 2, 'cat': 1}) if you print the defaultdict directly), and your loop increments each count with no check for whether the key exists yet.

Solution

If you start the tally from an empty dict, the first counts[kind] += 1 raises a KeyError for 'dog', because += reads the key before it writes it. The solution uses defaultdict(int), which supplies the 0 that the first read needs.

# exercise_2.py
from collections import defaultdict

pets = [("dog", "Rex"), ("cat", "Felix"), ("dog", "Fido")]
counts = defaultdict(int)
for kind, name in pets:
    counts[kind] += 1
print(dict(counts))
#: {'dog': 2, 'cat': 1}

The 0 that defaultdict(int) supplies for a missing key comes from int(), which returns 0 when called with no arguments. With that default, counts[kind] += 1 works with no “does this key exist yet” check. In defaultdict.py, defaultdict(list) removes the same check from the grouping loop, with a fresh empty list as the default.

Before you move on, name what separates your attempt from this one: a different design, a detail, or an equivalent alternative.

3. Set operations across three sets

In set_methods.py, add a set d = {1, 5, 9} and print a.union(b, d) and a.intersection(b, d).

Where to look

Sets lists the set operators, and set_methods.py shows the method forms of the same operations. The methods union() and intersection() take several arguments at once. Pass b and d in a single call to each.

Done when

your file prints {1, 2, 3, 4, 5, 9} and then set(), each from a single method call that receives both b and d, and you can say why the intersection is empty.

Solution
# exercise_3.py
a = {1, 2, 3}
b = {3, 4, 5}
d = {1, 5, 9}
print(a.union(b, d))
#: {1, 2, 3, 4, 5, 9}
print(a.intersection(b, d))
#: set()

union() and intersection() accept any number of arguments, unlike the | and & operators, which take two operands at a time. The three-way intersection is empty because no single value is a member of all three sets.

Before you move on, name what separates your attempt from this one: a different design, a detail, or an equivalent alternative.

4. Why a list cannot join a set of frozensets

In frozen_containers.py, add a line that tries groups.add([1, 2]) (a plain list, not a frozenset) and catch the exception it raises. Explain, in terms of hashability, why a frozenset works as a set member but a list does not.

Where to look

Immutability explains that a frozenset is hashable, so it works as a set member or a dictionary key. A set must hash each element when it adds it. Wrap the groups.add() call in a try, catch TypeError, and relate the message to what a list allows you to do after creation.

Done when

your except clause catches a TypeError whose message begins cannot use 'list' as a set element and ends (unhashable type: 'list'), and your explanation ties the hash a set computes at insertion to what a list lets you do after creation and a frozenset does not.

Solution
# exercise_4.py
groups = {frozenset({1, 2}), frozenset({3, 4})}
try:
    groups.add([1, 2])
except TypeError as e:
    print(type(e).__name__)
    print(str(e).partition(" (")[0])
#: TypeError
#: cannot use 'list' as a set element

A set hashes each element once, at insertion, so every element must be hashable. frozenset is hashable because it is immutable. Its contents stay the same after creation, so its hash stays valid. A list is mutable, so the list class sets __hash__ to None. A set member or a dictionary key needs a hash, so a list can be neither.

Before you move on, name what separates your attempt from this one: a different design, a detail, or an equivalent alternative.

5. Four slices of one list

Given xs = [10, 20, 30, 40, 50], write one slice expression for each of: the last two items, everything but the first and last, and a reversed copy of the middle three.

Where to look

Indexing and Slicing covers start, stop, and step, and the way negative values count from the end. You can slice a slice to reverse a copy. A negative step also reverses in a single slice, but then start and stop swap roles.

Done when

three single expressions on xs print [40, 50], [20, 30, 40], and [40, 30, 20], none of them uses len(), and xs prints [10, 20, 30, 40, 50] afterward. For a further check, produce [40, 30, 20] with one slice that has a negative step.

Solution

If you fold xs[1:4][::-1] into one slice as xs[1:4:-1], you get an empty list. A negative step counts down from start, and index 1 is less than the stop at 4, so the slice ends before it takes an item. The one-slice form in the solution swaps the bounds to xs[3:0:-1].

# exercise_5.py
xs = [10, 20, 30, 40, 50]
print(xs[-2:])  # The last two items
#: [40, 50]
print(xs[1:-1])  # Everything but the first and last
#: [20, 30, 40]
print(xs[1:4][::-1])  # The middle three, reversed
#: [40, 30, 20]
print(xs[3:0:-1])  # The same three, in one slice
#: [40, 30, 20]

A negative start counts from the end, so xs[-2:] stands in for xs[len(xs) - 2:].

The one-slice form is harder to read because the bounds swap roles. 3 is now the first index visited and 0 is the stop, which the slice excludes, so the slice ends at index 1.

Before you move on, name what separates your attempt from this one: a different design, a detail, or an equivalent alternative.

6. defaultdict(int) in place of Counter

Rewrite counter.py’s tally using a defaultdict(int) and no Counter. Which parts of Counter did you write yourself?

Where to look

Counter lists what Counter provides beyond a tally, and defaultdict shows the factory that creates missing entries. Write the counting loop with defaultdict(int). Then reproduce most_common() with sorted() and a key function, and notice what reading a missing key does to each container.

Done when

your file, with no Counter import, prints {'a': 3, 'cat': 2, 'sat': 1, 'on': 1, 'mat': 1} and [('a', 3), ('cat', 2)], matching counter.py’s most_common(2); counts["dog"] prints 0; and you can say how your container differs from a Counter after that read.

Solution

The solution counts with defaultdict(int) and rebuilds most_common() with sorted():

# exercise_6.py
from collections import defaultdict

words = "a cat sat on a mat a cat".split()
counts = defaultdict(int)
for word in words:
    counts[word] += 1
print(dict(counts))
#: {'a': 3, 'cat': 2, 'sat': 1, 'on': 1, 'mat': 1}
print(counts["dog"])  # Missing keys still read as zero
#: 0
print(sorted(counts.items(), key=lambda kv: -kv[1])[:2])
#: [('a', 3), ('cat', 2)]

Count each word. First, you write the loop yourself. Counter(words) counts an iterable inside its constructor, while defaultdict(int) removes the “does this key exist yet” check and leaves the counting to you.

Default a missing key to zero. Both containers read a missing key as 0. A Counter leaves its contents as they were, while defaultdict(int) stores a 0 for "dog", so their contents differ after the counts["dog"] line.

Rebuild the reporting. The rest rebuilds two of the things Counter supplies after the tally. most_common() becomes a sorted() call with a key function and a slice, and the Counter({...}) repr becomes a dict() conversion.

If you leave the minus sign out of the key function, sorted() ranks the lowest counts first, so the slice prints [('dog', 0), ('sat', 1)]. Reading counts["dog"] earlier stored that 0 under 'dog'. The minus sign negates each count, so sorted() puts the largest count first, matching most_common(), which ranks from the highest count down.

Before you move on, name what separates your attempt from this one: a different design, a detail, or an equivalent alternative.

7. heterogeneous.py as a namedtuple

Rewrite heterogeneous.py with a namedtuple. Show that the unpacking line still works unchanged.

Where to look

namedtuple builds a tuple subclass with named fields. Because each instance is still a tuple, the unpacking from Tuples and Unpacking works by position. Create the class with namedtuple(), keep the unpacking line as it was, and add a line that reads a field by name.

Done when

the line name, age, height = person appears in your file unchanged from heterogeneous.py and still prints Alice 30 1.65, and another line reads a field by name rather than by position and prints its value, such as Alice.

Solution
# exercise_7.py
from collections import namedtuple

Person = namedtuple("Person", ["name", "age", "height"])
person = Person("Alice", 30, 1.65)
# Unchanged from the tuple version
name, age, height = person
print(name, age, height)
#: Alice 30 1.65
# Now also reachable by name
print(person.name, person.height)  # [1]
#: Alice 1.65
print(person[0], type(person[0]).__name__)
#: Alice str

The unpacking line stays the same, because a namedtuple is a tuple subclass and unpacks by position like any other tuple.

In line [1], person.height names the field that person[2] reads by position. Unpacking and person[0] still work beside the names, so code written for the tuple runs unchanged.

A heterogeneous tuple that passes between functions is usually better as a namedtuple or a data class, because each function then reads a field by name instead of by position.

Before you move on, name what separates your attempt from this one: a different design, a detail, or an equivalent alternative.

8. Building and merging a dict

Given pairs = [("a", 1), ("b", 2), ("c", 3)], build a dict from it, then print its keys, its values, and the result of merging it with {"c": 30, "d": 4}. Which value ends up under "c", and why?

Where to look

Dictionaries shows the dict constructor and the merge operators in dict_ops.py. The dict() constructor accepts an iterable of pairs. The | operator builds a new dict. To decide which operand supplies the value when both hold the same key, compare | with update(), which writes its argument’s entries over the dictionary’s own.

Done when

your merge prints {'a': 1, 'b': 2, 'c': 30, 'd': 4}, your keys and values hold ['a', 'b', 'c'] and [1, 2, 3], and your answer says which operand supplies 30 and what the merge gives if you swap the two operands.

Solution
# exercise_8.py

pairs = [("a", 1), ("b", 2), ("c", 3)]
counts = dict(pairs)
print(counts)
#: {'a': 1, 'b': 2, 'c': 3}
print(list(counts.keys()), list(counts.values()))
#: ['a', 'b', 'c'] [1, 2, 3]
print(counts | {"c": 30, "d": 4})
#: {'a': 1, 'b': 2, 'c': 30, 'd': 4}
print(counts)  # The merge built a new dict
#: {'a': 1, 'b': 2, 'c': 3}

Build the dictionary. dict() accepts any iterable of two-item pairs, so a list of tuples becomes a dictionary in one call. dict_ops.py feeds the same constructor from two parallel sequences, as dict(zip("abc", [1, 2, 3])).

Resolve the collision. 30 ends up under "c", because | resolves a collision in favor of the right operand. A merge holds one value per key, and the two dictionaries hold different values for "c", so the merge must drop one of them. The right operand wins because a | b reads as “start from a, then apply b,” the same order a.update(b) has always used.

Build a new dictionary. | builds a new dictionary and leaves the left operand alone. |= updates the left dictionary in place.

Letting the right operand win makes | on dictionaries depend on operand order. a | b and b | a differ when the two dictionaries hold different values for a shared key. With this exercise’s operands swapped, {"c": 30, "d": 4} | counts gives {'c': 3, 'd': 4, 'a': 1, 'b': 2}. "c" keeps 3. The keys follow the left operand’s order, so "c" and "d" come first. On sets, a | b and b | a are the same set. The two uses share one operator because both mean “combine,” but the set version alone commutes.

Before you move on, name what separates your attempt from this one: a different design, a detail, or an equivalent alternative.

9. Unpacking without indexing

Using one unpacking assignment each, and no indexing, pull the first element, the last element, and everything in between out of row = [1, 2, 3, 4, 5]. Then explain why a, b = row raises a ValueError while a, *b = row succeeds.

Where to look

Tuples and Unpacking shows a starred target collecting the leftover items into a list. Put the star on the target that should collect the middle, or at either end. For the explanation, compare how many items an unstarred target list requires with how many a starred one allows.

Done when

your file subscripts row nowhere, its assignments print 1 [2, 3, 4, 5], [1, 2, 3, 4] 5, and 1 [2, 3, 4] 5, catching the exception from a, b = row prints too many values to unpack (expected 2, got 5), and your explanation says how many items each of the two target lists accepts.

Solution

If you index instead, writing first, middle, last = row[0], row[1:-1], row[-1], the program prints the same 1 [2, 3, 4] 5. That line uses the indexing the exercise rules out. The indexed line and the starred unpacking differ on a one-item list. The indexed version prints 1 [] 1, counting the one item as both first and last, while first, *middle, last = [1] raises a ValueError (not enough values to unpack). The solution uses starred targets, because one target list states the shape it expects and Python checks that shape for you.

# exercise_9.py

row = [1, 2, 3, 4, 5]
first, *rest = row
print(first, rest)
#: 1 [2, 3, 4, 5]
*most, last = row
print(most, last)
#: [1, 2, 3, 4] 5
first, *middle, last = row
print(first, middle, last)
#: 1 [2, 3, 4] 5
try:
    a, b = row
except ValueError as e:
    print(e)
#: too many values to unpack (expected 2, got 5)

Collect the remaining items. A starred target collects the remaining items, zero or more, so one assignment reaches any of the three positions without an index. The star may appear anywhere in the target list, so first, *middle, last = row works.

Reject a count mismatch. a, b = row fails because an unstarred target list states an exact count, two, and row holds five. Python raises a ValueError rather than dropping the extras, since a silent drop hides the mismatch. The same error appears in the other direction, as not enough values to unpack, when the list is shorter than the target list.

a, *b = row states a minimum: at least one item for a, and the rest, zero or more, for b. So the assignment accepts a five-item list, a one-item list, and everything between. Only an empty list has too few items. A *args parameter collects a call’s extra positional arguments the same way.

Before you move on, name what separates your attempt from this one: a different design, a detail, or an equivalent alternative.

10. A frozendict as a dictionary key

Build a frozendict from the pairs [("host", "localhost"), ("port", 8080)], then use it as a key in a dict that maps a configuration to a connection name. Look the connection name up again with a separately built, equal frozendict. Catch the TypeError that assigning to one of its entries raises. Finally, build a frozendict whose value is a list, try to hash it, and explain the result in terms of shallow immutability.

Where to look

frozendict shows construction, equality, and the error on assignment, and Shallow Immutability shows how far immutability reaches. A dictionary finds a key by hash and equality, so a separately built, equal frozendict locates the same entry. For the last part, ask what hash() must do with each value, and what happens when one of those values is a list.

Done when

the lookup with your separately built frozendict prints the connection name, the caught assignment prints 'frozendict' object does not support item assignment, and hashing the list-valued frozendict raises a TypeError that prints unhashable type: 'list', which your explanation connects to shallow immutability.

Solution

If you build the configuration with dict(pairs) instead, the program prints {'host': 'localhost', 'port': 8080}. Then connections = {config: "primary"} raises a TypeError: cannot use 'dict' as a dict key (unhashable type: 'dict'). A dict can change, so the dict class sets __hash__ to None. The solution builds a frozendict, whose entries stay the same after creation, so the frozendict is hashable when its values are.

# exercise_10.py

pairs = [("host", "localhost"), ("port", 8080)]
config = frozendict(pairs)
print(config)
#: frozendict({'host': 'localhost', 'port': 8080})
connections = {config: "primary"}
same = frozendict(port=8080, host="localhost")
print(connections[same])
#: primary
try:
    config["port"] = 9090  # type: ignore
except TypeError as e:
    print(e)
#: 'frozendict' object does not support item assignment

nested = frozendict(tags=["a", "b"])
try:
    hash(nested)
except TypeError as e:
    print(e)
#: unhashable type: 'list'

Build the configuration. frozendict takes the same arguments dict does: an iterable of two-item pairs, keyword arguments, or another mapping. So frozendict(pairs) equals frozendict(host="localhost", port=8080).

Look up by an equal key. The lookup with same succeeds because a dictionary finds a key by hash and equality, not by identity. config and same are separate objects built in different entry orders. They hold the same pairs, so they compare equal and hash the same. With a frozendict key, any equal configuration reaches the same entry.

Catch the rejected assignment. Assigning to an entry raises a TypeError at runtime, and the type checker rejects the assignment too. The line carries a # type: ignore because the listing makes the assignment on purpose, to show the runtime exception.

Find the limit of immutability. A frozendict freezes which object sits under each key, not what those objects contain. hash(nested) must hash its list value, and hashing a list raises a TypeError. The immutability is shallow, as it is for the tuple in shallow_immutability.py. Because a frozendict is hashable when its values are, keep its values immutable whenever you use the mapping as a key: a tuple here instead of a list.

Before you move on, name what separates your attempt from this one: a different design, a detail, or an equivalent alternative.