6. Collections: list, tuple, dict, set, and comprehensions

6.1 The four built-ins and their costs

The most common performance bug in Python scripts is if x in big_list inside a loop. Convert the list to a set once and the loop goes from O(n·m) to O(n):

blocked = ["10.0.0.%d" % i for i in range(10_000)]
blocked_set = set(blocked)          # build once: O(n)
print("10.0.0.9999" in blocked_set) # O(1)

A list stores pointers to objects, not the objects. That is why it can hold mixed types, and why it is slow for numeric work compared with a NumPy array, which stores raw numbers contiguously (Ch 53). The DSA guide covers the underlying structures.

6.2 Lists and slicing

xs = [5, 3, 8, 1]
xs.append(9); xs.extend([2, 7]); xs.insert(0, 0)
print(xs[1:4], xs[-2:], xs[::-1], xs[::2])   # slices create new lists
xs.sort()                       # in place, returns None
ys = sorted(xs, reverse=True)   # new list
print(xs.pop(), xs)             # remove and return the last item
first, *middle, last = [1, 2, 3, 4, 5]
print(first, middle, last)      # 1 [2, 3, 4] 5

xs.sort() returns None. Writing xs = xs.sort() replaces your list with None, a classic beginner bug.

For a queue, use collections.deque; list.pop(0) is O(n).

6.3 Tuples: records and multiple return values

point = (3, 4)
x, y = point                        # unpacking
def min_max(xs: list[int]) -> tuple[int, int]:
    return min(xs), max(xs)         # returns a tuple
lo, hi = min_max([4, 1, 9])
a, b = 1, 2
a, b = b, a                         # swap without a temp

Tuples are immutable and hashable (if their contents are), so they can be dict keys: distances[("BLR", "SFO")] = 13_970.

6.4 Dicts

ports = {"http": 80, "https": 443}
ports["ssh"] = 22
print(ports.get("ftp"), ports.get("ftp", 21))   # None 21
print("http" in ports)                          # checks keys
for name, port in ports.items():
    print(name, port)
merged = ports | {"dns": 53}                    # new dict (3.9+)
ports |= {"smtp": 25}                           # update in place
print(list(ports))                              # keys, in insertion order

Dict keys must be hashable: immutable built-ins, tuples of hashables, and objects that define __hash__ consistently with __eq__ (Ch 16). Since Python 3.7, dicts preserve insertion order as a language guarantee.

collections has three dict variants you will use weekly:

from collections import Counter, defaultdict

words = "the cat and the hat and the bat".split()
print(Counter(words).most_common(2))        # [('the', 3), ('and', 2)]

by_len: defaultdict[int, list[str]] = defaultdict(list)
for w in words:
    by_len[len(w)].append(w)                # no KeyError: missing keys get list()
print(dict(by_len))

6.5 Sets

a = {"read", "write"}
b = {"write", "admin"}
print(a & b, a | b, a - b, a ^ b)   # intersection, union, difference, symmetric
print({"read"} <= a)                # subset
seen: set[str] = set()              # {} is an empty dict, not a set

6.6 Comprehensions

squares = [n * n for n in range(10) if n % 2 == 0]
by_name = {u["name"]: u for u in [{"name": "ada", "id": 1}, {"name": "linus", "id": 2}]}
exts = {p.rsplit(".", 1)[-1] for p in ["a.py", "b.py", "c.md"]}
total = sum(len(w) for w in ["alpha", "beta"])   # generator expression: no list built
print(squares, list(by_name), exts, total)

A comprehension is faster and clearer than the equivalent loop with append. Stop at one for and one if. Nested comprehensions with several conditions are harder to read than a loop.