PHASE 4Beginner ~26 min· topic 10 of 11

Topic 4.10

The collections Toolbox

In one line

The standard library module collections adds specialised containers: Counter for counting, defaultdict for grouping, deque for fast work at both ends, namedtuple for records, OrderedDict for order-aware dictionaries and ChainMap for layered lookups.

Think of it like this

A kitchen drawer of special tools. A knife does everything badly; a peeler, a whisk and a grater each do one job very well. The built-in list, dict and set are the knives. The collections module is the drawer of specialised tools you reach for when the job is counting, grouping, queueing, or layering settings. To take a tool out of the drawer you write a line like from collections import Counter, which means "fetch the tool named Counter from the toolbox named collections". Topic 6.1 teaches import in full; for now copy that first line as it is.

Words you'll meet

New words in this topic, in plain English. Come back here whenever one feels fuzzy.

Counter: A special kind of dictionary for counting items. Its keys must be hashable (Topic 4.5).
defaultdict: A dictionary that makes a default value for a missing key by calling a factory such as list or int.
deque: A double-ended queue: fast to add or remove at either end.
Queue (FIFO): First in, first out, like people waiting in a line.
namedtuple: A tuple whose positions also have names.
OrderedDict: A dictionary with move_to_end and order-sensitive equality.
ChainMap: A view over several dictionaries that searches them in order.
Factory: A callable (like list) that creates a new default value when needed.

Step by step

01Counter: count in one line

Counter takes any iterable (anything you can loop over, such as a string or a list). most_common(2) gives the two highest as (item, count) pairs, with ties in the order the items were first seen. A missing item counts as zero.

main.pywhole filepython

from collections import Counter

counts = Counter("banana")
print(counts)                  # Counter({'a': 3, 'n': 2, 'b': 1})
print(counts.most_common(2))   # [('a', 3), ('n', 2)]
print(counts["z"])             # 0

02defaultdict: group without the ceremony

Group the words by their length. For a new length, the factory list is called and returns []; then we append. Compare with setdefault (Topic 4.4): the same result, less noise.

main.pywhole filepython

from collections import defaultdict

by_length = defaultdict(list)
for word in ["pen", "book", "bag", "desk"]:
    by_length[len(word)].append(word)
print(dict(by_length))   # {3: ['pen', 'bag'], 4: ['book', 'desk']}

03deque: both ends, and a fixed window

With maxlen, appending to a full deque pushes the oldest item out the other end. popleft is the constant-time way to take from the front, which a list does slowly with pop(0).

main.pywhole filepython

from collections import deque

recent = deque(maxlen=3)
for n in [1, 2, 3, 4]:
    recent.append(n)
print(recent)            # deque([2, 3, 4], maxlen=3)

line = deque(["Asha", "Ravi"])
line.appendleft("VIP")
print(line.popleft())    # VIP

deque: both ends, and a fixed windowdiagram

Rendering diagram…

04namedtuple: a record with names

Named tuples cost the same as tuples but read better. _asdict() converts one to a dictionary; _replace makes a changed copy, because the original cannot change.

main.pywhole filepython

from collections import namedtuple

Point = namedtuple("Point", ["x", "y"])
p = Point(3, 4)
print(p.x, p[1], p)
print(p._replace(x=10))      # a NEW Point(x=10, y=4)

05OrderedDict: reorder and strict equality

move_to_end is the building block of an "oldest first" cache. A plain dict says two dicts with the same pairs are equal in any order; an OrderedDict does not.

main.pywhole filepython

from collections import OrderedDict

d = OrderedDict([("a", 1), ("b", 2), ("c", 3)])
d.move_to_end("a")
print(list(d))                          # ['b', 'c', 'a']
print(OrderedDict(a=1, b=2) == OrderedDict(b=2, a=1))   # False

06ChainMap: layered lookups

The three dictionaries are not merged; the ChainMap just asks them in order. Changing a layer later is visible through the ChainMap.

main.pywhole filepython

from collections import ChainMap

cli = {"color": "red"}
env = {"color": "blue", "size": 12}
defaults = {"color": "black", "size": 10, "lang": "en"}
settings = ChainMap(cli, env, defaults)
print(settings["color"], settings["size"], settings["lang"])   # red 12 en

ChainMap: layered lookupsdiagram

Rendering diagram…

Try it yourself

1
Count your own text
In the first example, replace the sentence with a line you choose. Which word wins? What does most_common() with no number return?
2
Slide the window
In the second example, change maxlen=3 to maxlen=2 and predict the output of "last three" before you run it.

Code & diagrams

Counter and defaultdict New tab

Replace the sentence with your own and see which word is most common.

Expected output

counts: Counter({'to': 3, 'be': 3, 'or': 1, 'not': 1, 'that': 1, 'is': 1, 'the': 1, 'question': 1})
top 2: [('to', 3), ('be', 3)]
'to' appears: 3 | 'zebra' appears: 0
after update: 2
letters: Counter({'a': 3, 'n': 2, 'b': 1})
by length: {3: ['pen', 'bag', 'ink'], 4: ['book', 'desk']}
tally: {'m': 1, 'i': 4, 's': 4, 'p': 2}

deque, namedtuple, OrderedDict and ChainMap New tab

Expected output

last three: deque([3, 4, 5], maxlen=3)
first in line: VIP | left: ['Asha', 'Ravi']
rotated: ['Ravi', 'Asha']
point: Point(x=3, y=4) | x: 3 | as dict: {'x': 3, 'y': 4}
moved: Point(x=10, y=4)
reordered: ['b', 'c', 'a']
settings: red 12 en
cli changed later: 99

Analyse a stream of events New tab

A tiny version of what real services do with logs and analytics: count what happened, group it by user, and keep only the latest few events.

Expected output

actions: [('login', 3), ('search', 3), ('logout', 1)]
per user: {'asha': ['login', 'search', 'logout'], 'ravi': ['login', 'search', 'search'], 'meena': ['login']}
last three events: [('ravi', 'search'), ('meena', 'login'), ('ravi', 'search')]
busiest user: [('asha', 3)]

Break it on purpose

Errors are the best teachers. Make each change, read the error, guess what went wrong, then reveal the answer.

Break #1

Change a namedtuple

Assign to a field of a named tuple.

main.pywhole filepython

from collections import namedtuple

Point = namedtuple("Point", ["x", "y"])
p = Point(3, 4)
p.x = 10

terminal

$ python main.py

── what you'll see ──

Traceback (most recent call last):

File "main.py", line 5, in <module>

p.x = 10

^^^

AttributeError: can't set attribute

Break #2

Slice a deque

Take a slice of a deque as you would from a list.

main.pywhole filepython

from collections import deque

d = deque([1, 2, 3, 4])
print(d[1:3])

terminal

$ python main.py

── what you'll see ──

Traceback (most recent call last):

File "main.py", line 4, in <module>

print(d[1:3])

~^^^^^

TypeError: sequence index must be integer, not 'slice'

Myth vs fact

Myth

OrderedDict is needed to keep order.

Fact

All dictionaries keep insertion order since Python 3.7. OrderedDict adds move_to_end and order-sensitive equality.

Myth

deque is just a list with a different name.

Fact

It is fast at both ends but slow to index in the middle. A list is the opposite.

Myth

Reading from a defaultdict never changes it.

Fact

Reading a missing key creates it with the default value. Use key in d or d.get(key) to look without creating.

Pro corner

Extra depth for experienced readers. New to this? Skip it for now and come back later.

▸
deque is a doubly linked list of fixed-size blocks, which gives O(1) at both ends and O(n) in the middle. It is also thread-safe for append and popleft, which is why it is the usual in-memory queue between threads. queue.Queue adds blocking and waiting on top.
▸
Counter is a dict subclass, so its keys must be hashable. Counter arithmetic (+, -, &, |) keeps only positive counts. counts.total() (Python 3.10) sums all counts, and counts.elements() repeats each item by its count.
▸
OrderedDict still differs from dict in three ways: move_to_end(key, last=True) and popitem(last=False) (pop from the front), which make an LRU cache easy; equality between two OrderedDicts is order-sensitive, but OrderedDict == dict ignores order; and it is a little slower and bigger. ChainMap reads search the layers in order, but writes and deletes touch only the first map, and new_child() pushes a fresh empty layer, which is how nested scopes are modelled. Counter.subtract() keeps zero and negative counts, while + and - between Counters drop them.
▸
A defaultdict's factory is called with no arguments only when a missing key is read with []; get does not call it. Setting default_factory to None makes it behave like a normal dict. Printing it shows defaultdict(<class 'list'>, {...}), so convert with dict(d) before you print or send it as JSON.
▸
In AI and data code you will use Counter for token and word frequencies, defaultdict(list) to group documents by label, and deque(maxlen=n) for a sliding window of recent messages. Be aware that a long chat history must also be trimmed by tokens, not only by message count (Phase 16).

Remember this

1
Counter(items) counts how often each item appears and behaves like a dictionary from item to count. Counter("banana") gives {'a': 3, 'n': 2, 'b': 1}. A missing item counts as 0 instead of raising KeyError, most_common(n) returns the n biggest counts, update adds more counts, and you can add and subtract Counters. It replaces the counts[x] = counts.get(x, 0) + 1 loop (Topic 4.4).
2
defaultdict(factory) is a dictionary that creates a missing value for you by calling factory(). defaultdict(list) gives an empty list for a new key, so grouping becomes groups[key].append(item) with no setdefault and no if key not in. defaultdict(int) starts counts at 0. One warning: just reading a missing key creates it.
3
deque (say "deck", short for double-ended queue) is a list-like container that is fast at both ends: append, appendleft, pop, popleft all take constant time, which means the same short time however long the deque is. A list is slow at the front, because every item has to shift. A deque(maxlen=3) automatically drops the oldest item when full, perfect for "the last 3 messages". Reading from the middle of a deque by index is slow, and slices are not supported.
4
namedtuple("Point", ["x", "y"]) creates a new kind of tuple (a class, which Phase 8 teaches) where positions also have names: p.x. It is immutable, unpackable, light on memory, and prints as Point(x=3, y=4). Use it for small, fixed records. For richer records (defaults, methods, type hints) use a dataclass (Topic 8.8) or typing.NamedTuple.
5
OrderedDict is a dictionary that remembers insertion order, which all dictionaries have done since Python 3.7. It remains useful for two things regular dictionaries lack: move_to_end(key) to reorder, and equality that cares about order (two OrderedDicts with the same pairs in different order are not equal). Together they make it handy for small caches that evict the oldest entry.
6
ChainMap(first, second, third) looks up a key in several dictionaries in order, without copying them: the first dictionary that has the key wins. It models layered settings: options typed when the program starts, then settings kept by your computer (environment variables), then built-in defaults. Writes go to the first dictionary only. Seeing the layers separately is its advantage over merging with |.

Explain it without notes

What problem do Counter and defaultdict solve compared with a plain dict?

Why choose deque instead of a list for a queue?

When would you use ChainMap?

How does a namedtuple differ from a regular tuple and from a dictionary?

How would you build a small LRU (least recently used) cache with the standard library?

Practice

Use Counter to find the most common letter in "mississippi" and print it with its count.

Group ["apple", "avocado", "banana", "blueberry", "cherry"] by first letter using defaultdict(list) and print it as a normal dict.

Keep only the last 3 numbers of [1, 2, 3, 4, 5, 6] using a deque with maxlen, and print them as a list.

Trade-offs

↔
Right tool, one more import. Each container is faster or clearer for one job but adds a name to learn. For one-off scripts a plain dict is fine; for counting and grouping the collections version is shorter and safer.
↔
Specialised means restricted. deque gives up cheap indexing and slicing; namedtuple gives up mutation; Counter is for hashable items only. Choose by the operation you do most.

Done when you can

Done when you can count items with Counter and read most_common.
Done when you can group items with defaultdict(list) and explain why reading a missing key creates it.
Done when you can use a deque as a queue and as a sliding window with maxlen.
Done when you can create and use a namedtuple, including _replace.
Done when you can describe what OrderedDict and ChainMap add.

Command Palette

Words you'll meet

Step by step

01Counter: count in one line

02defaultdict: group without the ceremony

03deque: both ends, and a fixed window

04namedtuple: a record with names

05OrderedDict: reorder and strict equality

06ChainMap: layered lookups

Try it yourself

Count your own text

Slide the window

Code & diagrams

Break it on purpose

Change a namedtuple

Slice a deque

Myth vs fact

Pro corner

Remember this

Explain it without notes

Practice

Trade-offs

Done when you can