Specialized Collections

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.

"""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.

"""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.

"""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.