S008 · Data Structures — list, tuple, dict, set (when to use what)

"""s008_data_structures.py — the built-in menu, in action."""
from __future__ import annotations
from collections import Counter, defaultdict, deque, namedtuple, ChainMap
import time
 
# =========================
# Part 1 · O(n) list search vs O(1) set search
# =========================
print("--- Part 1 · perf ---")
 
N = 100_000
big_list = list(range(N))
big_set = set(big_list)
probe = N - 1                              # worst case for the list
 
t = time.perf_counter()
for _ in range(1000):
    _ = probe in big_list
list_ms = (time.perf_counter() - t) * 1000
 
t = time.perf_counter()
for _ in range(1000):
    _ = probe in big_set
set_ms = (time.perf_counter() - t) * 1000
 
print(f"list  1000 checks: {list_ms:.1f} ms")
print(f"set   1000 checks: {set_ms:.3f} ms")
print(f"set is ~{list_ms/set_ms:.0f}× faster for membership")
 
# =========================
# Part 2 · Counter — tally in one line
# =========================
print("\n--- Part 2 · Counter ---")
 
sentence = "the quick brown fox jumps over the lazy dog the fox is quick"
word_counts = Counter(sentence.split())
print(word_counts.most_common(3))
 
# Multiset math for free
bag_a = Counter("aabbc")
bag_b = Counter("abcd")
print("intersect:", bag_a & bag_b)   # min of each
print("sum:      ", bag_a + bag_b)   # add counts
print("diff:     ", bag_a - bag_b)   # subtract (min 0)
 
# =========================
# Part 3 · defaultdict — grouping without KeyError
# =========================
print("\n--- Part 3 · defaultdict ---")
 
rows = [("engineer", "ada"), ("engineer", "linus"), ("cook", "julia"), ("engineer", "grace")]
 
# BAD — verbose
groups_bad: dict[str, list[str]] = {}
for role, name in rows:
    if role not in groups_bad:
        groups_bad[role] = []
    groups_bad[role].append(name)
 
# GOOD — defaultdict does the ‘if missing’ for you
groups: dict[str, list[str]] = defaultdict(list)
for role, name in rows:
    groups[role].append(name)
 
print(dict(groups))
 
# =========================
# Part 4 · deque — O(1) at both ends
# =========================
print("\n--- Part 4 · deque ---")
 
# BFS queue — a canonical use
def bfs_levels(root: dict, children_key: str = "children") -> list[list]:
    queue = deque([(root, 0)])
    levels: dict[int, list] = defaultdict(list)
    while queue:
        node, level = queue.popleft()               # O(1) — list.pop(0) is O(n)
        levels[level].append(node["name"])
        for child in node.get(children_key, []):
            queue.append((child, level + 1))
    return [levels[i] for i in sorted(levels)]
 
tree = {
    "name": "root",
    "children": [
        {"name": "a", "children": [{"name": "a1"}, {"name": "a2"}]},
        {"name": "b", "children": [{"name": "b1"}]},
    ],
}
print(bfs_levels(tree))
 
# Ring buffer — the last N events, in constant memory
recent = deque(maxlen=5)
for i in range(20):
    recent.append(i)
print("last 5:", list(recent))
 
# =========================
# Part 5 · namedtuple — tiny records
# =========================
print("\n--- Part 5 · namedtuple ---")
 
Point = namedtuple("Point", "x y")
p = Point(3, 4)
print(p, p.x, p.y)
print("as dict:", p._asdict())
print("with replacement:", p._replace(y=99))
# Note: namedtuples are hashable and can be dict keys or set elements.
seen: set[Point] = {Point(0, 0), Point(1, 1), Point(0, 0)}
print("unique points:", seen)
 
# For anything larger than 3 fields, prefer @dataclass (S014).
 
# =========================
# Part 6 · ChainMap — layered config
# =========================
print("\n--- Part 6 · ChainMap ---")
 
cli   = {"log_level": "DEBUG"}
env   = {"log_level": "INFO", "port": 8080}
defaults = {"log_level": "WARNING", "port": 80, "workers": 4}
 
config = ChainMap(cli, env, defaults)                # left-most wins
print("log_level:", config["log_level"])              # DEBUG (from cli)
print("port     :", config["port"])                   # 8080 (env, since cli lacks it)
print("workers  :", config["workers"])                # 4    (defaults)
 
# =========================
# Part 7 · Sets and set algebra
# =========================
print("\n--- Part 7 · set algebra ---")
 
writers = {"ada", "linus", "grace"}
speakers = {"grace", "hopper", "guido"}
 
print("both:      ", writers & speakers)
print("either:    ", writers | speakers)
print("writers only:", writers - speakers)
print("xor:       ", writers ^ speakers)
 
# Dedup while preserving order (3.7+ dicts are ordered)
def dedup(items):
    return list(dict.fromkeys(items))
print("dedup:", dedup([3, 1, 4, 1, 5, 9, 2, 6, 5, 3]))
 
# =========================
# Part 8 · When you need immutability — frozenset
# =========================
print("\n--- Part 8 · frozenset ---")
 
flag_sets = {
    frozenset({"admin", "read"}): "admin-role",
    frozenset({"read"}):          "reader-role",
}
print(flag_sets[frozenset({"read", "admin"})])   # order-independent lookup
# A regular set can't be a dict key: TypeError: unhashable type: 'set'