deque vs. list at different sizesIn
deque_timing.py, changenfrom20_000to2_000, change the printed comparison todeque_time < list_time, and run the timing again. Doesdeque_time < list_timestill hold? Changento200_000and try again. The list version takes several seconds at that size, and much longer on a slow machine. Explain what changes about the comparison asngrows.
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 of exercise_1.py
from collections import deque
from timeit import timeit
from benchmark import report
def list_left_ops():
...
def deque_left_ops():
...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.
# 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)
#: Truedeque_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.
defaultdict(int) for countingIn
defaultdict.py, replacedefaultdict(list)withdefaultdict(int), change the loop to count occurrences of eachkindinstead of collecting names, and print the result.
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.
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.
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.
In
set_methods.py, add a setd = {1, 5, 9}and printa.union(b, d)anda.intersection(b, d).
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.
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.
# 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.
list cannot join a set of
frozensetsIn
frozen_containers.py, add a line that triesgroups.add([1, 2])(a plain list, not afrozenset) and catch the exception it raises. Explain, in terms of hashability, why afrozensetworks as a set member but alistdoes not.
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.
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.
# 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 elementA 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.
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.
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.
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.
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.
defaultdict(int) in place of
CounterRewrite
counter.py’s tally using adefaultdict(int)and noCounter. Which parts ofCounterdid you write yourself?
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.
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.
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.
heterogeneous.py as a
namedtupleRewrite
heterogeneous.pywith anamedtuple. Show that the unpacking line still works unchanged.
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.
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.
# 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 strThe 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.
dictGiven
pairs = [("a", 1), ("b", 2), ("c", 3)], build adictfrom 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?
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.
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.
# 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.
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 whya, b = rowraises aValueErrorwhilea, *b = rowsucceeds.
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.
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.
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.
frozendict as a dictionary keyBuild a
frozendictfrom the pairs[("host", "localhost"), ("port", 8080)], then use it as a key in adictthat maps a configuration to a connection name. Look the connection name up again with a separately built, equalfrozendict. Catch theTypeErrorthat assigning to one of its entries raises. Finally, build afrozendictwhose value is alist, try to hash it, and explain the result in terms of shallow immutability.
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.
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.
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.