--- title: 'Specialized Collections' source: 'https://academia.sh/en/courses/python-data-structures/specialized-collections' course: 'Data Structures and Functional Tools' language: en updated: '2026-08-17T18:10:25+00:00' license: 'CC BY-SA 4.0' --- # Specialized Collections Writing the same grouping with setdefault creates 320 containers, with a defaultdict 100; on a thousand-item stream, all three spellings produce 1000 objects but held is 1000 against 5, and rotating builds three containers with a list against none with a deque. The previous lesson's last line wrote the question a set cannot answer: **how many times.** A set holds only membership; it does not keep the count, because it does not have to. Anyone who wants that number writes the same pattern by hand — open a dict, increment if the key exists, start at one if not. Other patterns get written by hand the same way: sorting records into bins by key, holding only a stream's last few items, moving one end of a sequence to the other. This lesson looks at these patterns' ready-made counterparts in the standard library and puts each side by side with its hand-written equivalent. Two numbers get measured: **how many lines**, and **how many objects**. ## A Pattern's Two Prices Writing a pattern by hand has two separate, independent costs. The first is **lines**: code written, read, tested, and capable of being written wrong. The second is **objects**: what the pattern creates and holds while running. One spelling can cut lines while raising objects; one of the three grouping spellings measured here does exactly that. The theory behind structures like stacks, queues, and linked lists was built in the **Data Structures** course and is not repeated here. What's measured here is which container Python delivers that queue through, and how many lines and objects it saves against its hand-written counterpart. Line count is not counted by hand: each spelling is a function body, and its non-blank line count is read from the function's own source. The number is therefore a finding from the run, not a claim. - **CO52** — Body lines are read from the function's source; **the def line and blank lines are not counted.** Every spelling is a function indented the same way, doing the same job. - **CO53** — Three counting spellings and three grouping spellings work on the **same data**; the data carries 320 records and 100 distinct keys, with one key deliberately appearing more often. - **CO54** — The correctness column compares the result against the first, hand-written spelling's result; the hand-written pattern is the oracle. - **CO55** — In grouping, a box is an object counted at each creation; what gets counted is boxes, not the records put into them. - **CO56** — The counter resets right before each spelling; building the data does not enter the measurement. ```python """Counting and grouping: hand-written pattern side by side with its ready-made counterpart.""" import inspect from collections import Counter, defaultdict COUNTER = {"created": 0} class Item: def __init__(self, value): COUNTER["created"] += 1 self.value = value def __repr__(self): return f"Item({self.value})" def reset(): COUNTER["created"] = 0 def created(): return COUNTER["created"] DATA = [f"a{i % 100:02d}" for i in range(300)] + ["a07"] * 20 def body_lines(f): """Non-blank line count of a function's body; the def line is not counted.""" lines = inspect.getsource(f).splitlines()[1:] return sum(1 for s in lines if s.strip()) def manual_count(data): counts = {} for key in data: if key in counts: counts[key] += 1 else: counts[key] = 1 return counts def get_count(data): counts = {} for key in data: counts[key] = counts.get(key, 0) + 1 return counts def use_counter(data): return Counter(data) def manual_group(data): boxes = {} for i, key in enumerate(data): if key not in boxes: boxes[key] = Item([]) boxes[key].value.append(i) return boxes def setdefault_group(data): boxes = {} for i, key in enumerate(data): boxes.setdefault(key, Item([])).value.append(i) return boxes def defaultdict_group(data): boxes = defaultdict(lambda: Item([])) for i, key in enumerate(data): boxes[key].value.append(i) return boxes EXPECTED_COUNT = manual_count(DATA) EXPECTED_GROUP = {k: v.value for k, v in manual_group(DATA).items()} print(f"{'counting spelling':<24s}{'body lines':>11s}{'created':>10s}" f"{'result correct':>16s}") for label, method in (("manual check", manual_count), ("with get", get_count), ("counter", use_counter)): reset() result = method(DATA) print(f"{label:<24s}{body_lines(method):>11d}{created():>10d}" f"{str(dict(result) == EXPECTED_COUNT):>16s}") print() print(f"{'grouping spelling':<24s}{'body lines':>11s}{'created':>10s}" f"{'result correct':>16s}") for label, method in (("manual check", manual_group), ("with setdefault", setdefault_group), ("defaultdict", defaultdict_group)): reset() result = method(DATA) correct = {k: v.value for k, v in result.items()} == EXPECTED_GROUP print(f"{label:<24s}{body_lines(method):>11d}{created():>10d}" f"{str(correct):>16s}") print() print(f"data {len(DATA)} records | distinct keys {len(EXPECTED_COUNT)} | " f"counts seen {sorted(set(EXPECTED_COUNT.values()))}") print(f"counter's two most common: {Counter(DATA).most_common(2)}") ``` ``` counting spelling body lines created result correct manual check 7 0 True with get 4 0 True counter 1 0 True grouping spelling body lines created result correct manual check 6 100 True with setdefault 4 320 True defaultdict 4 100 True data 320 records | distinct keys 100 | counts seen [3, 23] counter's two most common: [('a07', 23), ('a00', 3)] ``` ## Cheap Lines, Not Cheap Objects The upper table only measures the line side, and only in one direction. Manual counting takes **7** lines, `get` **4**, and **Counter** just **1**. All three give the correct result, and all three create **0** objects — counts are integers, not containers. What's gained is only lines; but lines are a cost too, since handling a key's first appearance separately means one more branch and one more place to get wrong. `Counter`'s extra gift shows in the last line: giving the most common keys already sorted. By hand, that means sorting the dict by value and taking the first two. What a ready-made container offers is not just the pattern itself, it is the work around it. The lower table is the real measurement, and its two columns work in opposite directions. Manual grouping creates **6** lines and **100** boxes: one for each distinct key. The `setdefault` spelling drops to **4** lines — but creates **320** boxes. The difference is in the spelling itself: `setdefault` is a **call**, and its argument gets evaluated **before** the call, without checking whether the result will be used. If the key already exists, the box created is never used and gets thrown away right there. Three hundred twenty records build three hundred twenty boxes, two hundred twenty of them for nothing. **`defaultdict`** drops to the same **4** lines with **100** boxes. Because there, what builds the box is not the caller, it is the container itself: the producer is called only if the key is **actually missing**, otherwise not. Same line count, less than a third the objects. The rule that follows looks not at spelling but at **evaluation timing**: a default value written as an argument gets created on every call; given as a producer, only when needed. Two spellings, same length, same result; where they diverge is exactly the axis this course measures. ## Holding Only the Stream's Tail The second measurement looks at a container's **holding** side. On a thousand-item stream, every item gets created — there is no escaping that, since the container is not what produces the items. What can change is **how many** of them the container keeps. The third container in this measurement is a **deque**: an ordered container that can take and give items from either end, and can be given a length cap when built. - **CO57** — All three spellings build the same thousand-item stream; items are created during the measurement, and the counter resets before each spelling. - **CO58** — The window is five items, and the last item is printed for all three spellings, confirming all three consumed the stream to the end. - **CO59** — In the rotation measurement, containers built is read **from the container-building expressions in the code**: two slices plus a concat make three, in-place rotation builds none. Container count is also confirmed with `is`. - **CO60** — The two rotation results are compared for being in the **same order**; this line shows the two spellings' equivalence. - **CO61** — Item sharing is tested by searching every result item in the pool with `is`. ```python """Deque: a bounded window and rotation, alongside their hand-written counterparts.""" import inspect from collections import deque COUNTER = {"created": 0} class Item: def __init__(self, value): COUNTER["created"] += 1 self.value = value def __repr__(self): return f"Item({self.value})" def reset(): COUNTER["created"] = 0 def created(): return COUNTER["created"] def body_lines(f): lines = inspect.getsource(f).splitlines()[1:] return sum(1 for s in lines if s.strip()) STREAM, WINDOW = 1000, 5 def list_untrimmed(): container = [] for i in range(STREAM): container.append(Item(i)) return container def list_trimmed(): container = [] for i in range(STREAM): container.append(Item(i)) if len(container) > WINDOW: del container[0] return container def with_deque(): container = deque(maxlen=WINDOW) for i in range(STREAM): container.append(Item(i)) return container print(f"{'spelling':<24s}{'body lines':>11s}{'created':>10s}" f"{'held':>8s}{'last item':>12s}") for label, method in (("list, untrimmed", list_untrimmed), ("list, manual trim", list_trimmed), ("deque", with_deque)): reset() container = method() print(f"{label:<24s}{body_lines(method):>11d}{created():>10d}" f"{len(container):>8d}{str(container[-1]):>12s}") print() POOL = [Item(i) for i in range(5)] K = 2 lst = list(POOL) reset() left, right = lst[K:], lst[:K] rotated = left + right print(f"rotating with a list: created {created()} | containers built 3 " f"(two slices and a concat)") print(f" result {rotated} | rotated is lst -> " f"{rotated is lst}") dq = deque(POOL) before = dq reset() dq.rotate(-K) print(f"rotating with a deque: created {created()} | containers built 0") print(f" result {list(dq)} | dq is before -> {dq is before}") print(f" both results in the same order -> {list(dq) == rotated}") print(f" items shared -> " f"{all(any(x is y for y in POOL) for x in dq)}") ``` ``` spelling body lines created held last item list, untrimmed 4 1000 1000 Item(999) list, manual trim 6 1000 5 Item(999) deque 4 1000 5 Item(999) rotating with a list: created 0 | containers built 3 (two slices and a concat) result [Item(2), Item(3), Item(4), Item(0), Item(1)] | rotated is lst -> False rotating with a deque: created 0 | containers built 0 result [Item(2), Item(3), Item(4), Item(0), Item(1)] | dq is before -> True both results in the same order -> True items shared -> True ``` ## Created the Same, Held Different The "created" column is the same in all three rows: **1000**. That this column does not change is the measurement's most important finding. Changing the container does not change how many objects get produced — items are not produced by the container. The only thing the container chooses is how many of the produced ones **stay held**. The "held" column diverges: the untrimmed list holds **1000** items, the manually trimmed list **5**, the deque **5**. All three consume the stream to the end, and all three end on the same last item. If only the last five items are needed, the untrimmed list holds nine hundred ninety-five objects for no reason at all. The lines column gives the second difference: manual trimming needs **6** lines, the deque **4**. The two extra lines are a condition and a delete. In the hand-written spelling, the window limit is something checked **inside the loop**, on every turn; in the deque, it is part of the container's **definition**. The lower block measures rotation and confirms the two results are **in the same order**. Rotating with a list creates **0** items but builds **3** containers: the right part's slice, the left part's slice, and the concatenation of the two. The result is a new container, and `rotated is lst` is **False**. Rotating with a deque creates **0** items and builds **0** containers; the result is the same container, and `dq is before` is **True**. Items come from the pool in both spellings. The gap between three containers and zero looks small, but if rotation sits inside a loop, every turn builds three. **The hand-written pattern usually gives the correct result; what it costs is not the result itself, it is the intermediate containers built along the way.** ## A Missing Key and a Preserved Count Both specialized containers are dicts, and both diverge from a plain dict on a missing key — but they also diverge from each other. The third measurement repeats bracket access on three containers and checks how many keys remain **after** the access. - **CO62** — All three containers are built with a single key, the same value; the only thing measured is the result of accessing a key that **does not exist**. - **CO63** — Key count is read **after** the access; whether the access changed the container shows in this number. - **CO64** — Counter arithmetic is done with two small counters; results are printed sorted by key, since what's measured is the preserved count, not order. ```python """Three containers do three different things with a missing key; a Counter computes while preserving 'how many'.""" from collections import Counter, defaultdict PLAIN_DICT = {"a07": 3} DEFAULT = defaultdict(int, {"a07": 3}) COUNT = Counter({"a07": 3}) print(f"{'container':<20s}{'d[missing] result':<19s}{'keys after'}") for label, container in (("dict", PLAIN_DICT), ("defaultdict", DEFAULT), ("Counter", COUNT)): try: result = str(container["missing"]) except KeyError as e: result = type(e).__name__ print(f"{label:<20s}{result:<19s}{len(container)}") print() LEFT = Counter("aabbbcc") RIGHT = Counter("abbdd") print(f"left counter {dict(sorted(LEFT.items()))}") print(f"right counter {dict(sorted(RIGHT.items()))}") print(f"{'operation':<22s}{'result'}") for label, result in (("counter intersection", LEFT & RIGHT), ("counter union", LEFT | RIGHT), ("counter difference", LEFT - RIGHT)): print(f"{label:<22s}{dict(sorted(result.items()))}") print(f"{'set intersection':<22s}{sorted(set(LEFT) & set(RIGHT))}") print(f"{'set union':<22s}{sorted(set(LEFT) | set(RIGHT))}") print() print(f"a Counter is a dict -> {isinstance(LEFT, dict)} | " f"total records {sum(LEFT.values())} | distinct keys {len(LEFT)}") print(f"intersection total {sum((LEFT & RIGHT).values())} | " f"set intersection item count {len(set(LEFT) & set(RIGHT))}") ``` ``` container d[missing] result keys after dict KeyError 1 defaultdict 0 2 Counter 0 1 left counter {'a': 2, 'b': 3, 'c': 2} right counter {'a': 1, 'b': 2, 'd': 2} operation result counter intersection {'a': 1, 'b': 2} counter union {'a': 2, 'b': 3, 'c': 2, 'd': 2} counter difference {'a': 1, 'b': 1, 'c': 2} set intersection ['a', 'b'] set union ['a', 'b', 'c', 'd'] a Counter is a dict -> True | total records 7 | distinct keys 3 intersection total 3 | set intersection item count 2 ``` Three containers do three different things. The dict raises an exception and does not change: key count stays at **1**. The defaultdict gives **0** and key count rises to **2** — an access meant only for reading has added a **permanent entry** to the container. The Counter gives **0** and key count stays at **1**: it says zero for a missing key but does not record it. This distinction is a direct result of the grouping measurement. Calling the producer on a missing key was the behavior wanted in grouping; the same behavior is an **unwanted side effect** in an access meant only to look. In a defaultdict, "is this key here" is not asked with brackets; it is asked with membership testing or `get`. The lower block answers the previous lesson's closing question. In data handed to a set, "how many times" was lost. A Counter does the same arithmetic while **preserving** the count: intersection gives the **smaller** of the two counts per key, union the **larger**, and difference gives the subtraction result — a key that drops below zero never appears in the result. A set on the same two pieces of data gives only the keys. The last line sums up the difference with one pair: the set intersection has **2** items, the counter intersection's total is **3**. Same two keys, two different levels of information. ## Summary - A pattern has two separate prices — lines and objects — and they can move independently: the `setdefault` spelling drops lines from **6** to **4** while raising created containers from **100** to **320**. - A default written as an **argument** gets created on every call; given as a **producer**, it is called only when the key is missing — `defaultdict` builds **100** containers with the same **4** lines. - On the counting side, the gain is only in lines: **7**, **4**, and **1** line spellings all give the same result and create **0** objects. - On a thousand-item stream, all three spellings create **1000** objects; the container decides only what's **held** — **1000** in an untrimmed list, **5** in a manually trimmed list and a deque. - Rotation builds **3** intermediate containers with a list and returns a new one, **0** with a deque and turns the same container in place; both results are in the same order and share items. - On a missing key, a dict raises `KeyError`, a defaultdict gives **0** and **adds** the key (**1** to **2**), a Counter gives **0** without adding it; a Counter also computes intersection and difference while preserving counts. ## Next Step This lesson's rotation measurement took two slices, and the result was a new container. A slice passed here as a detail; on its own, though, it is this course's most misunderstood operation. The next lesson looks at nothing else and carries a single question all the way through: when a slice is taken, **what** gets copied? The container itself, its contents, or both? The answer gets measured in a nested list, and the numbers will speak for themselves.