Python Lists, Dictionaries, and the collections Module
I worked through Python's core containers, list, dict, set, and the collections helpers, choosing structures by their Big-O behaviour. Replacing list membership scans with set/dict lookups cut a hot path from O(n) to O(1).
Objective & Context
Picking the wrong container is a common performance trap. This lab maps operations to complexity, list append O(1), list in O(n), dict/set lookup O(1), and uses Counter and defaultdict to simplify aggregation in automation scripts.
Learning Objectives
- Aggregate and count with collections.Counter instead of manual loops.
- Replace O(n) list membership scans with O(1) set lookups.
- Group items cleanly with collections.defaultdict.
- Predict container performance using Big-O for common operations.
- Pick the right container for aggregation, membership, and grouping tasks.
Environment & Prerequisites
Prerequisites
Python 3.11with the standard librarycollectionsmodule- A small dataset to aggregate (log lines or the sample strings used here)
timeitfor comparing lookup performance- Assumed skill: loops, conditionals, and basic Big-O intuition
Step-by-Step Execution
1. Aggregate with Counter
python -c "from collections import Counter; print(Counter('mississippi').most_common(2))"Expected output:
[('i', 4), ('s', 4)]What this teaches: Counter does the counting loop in C and most_common() returns ranked results; the manual version needs a dict, a loop, and a sort.
2. O(1) membership with a set
python -c "allow={'a','b'}; print('a' in allow)"Expected output:
TrueWhat this teaches: Set membership is a hash lookup, so it stays constant time as the collection grows, while list membership scans every element.
3. Group with defaultdict
from collections import defaultdict
events = [("203.0.113.5", 80), ("203.0.113.5", 443), ("198.51.100.7", 22)]
groups = defaultdict(list)
for ip, port in events:
groups[ip].append(port)
print(dict(groups))Expected output:
{'203.0.113.5': [80, 443], '198.51.100.7': [22]}What this teaches: defaultdict removes the if-key-not-present boilerplate, so grouping loops read as pure intent: append each item to its group. Converting to a plain dict for the print keeps the output readable; the grouping itself works identically either way.
How It Works
How It Works
Big-O describes how cost grows with input size. Scanning a list for membership is O(n): double the list, double the worst-case scan. A set or dict lookup hashes the key and jumps straight to the bucket, which is O(1) on average regardless of size.
That difference compounds. Checking 10,000 allow-list entries against a 100,000-item list costs up to a billion comparisons; the same checks against a set cost 10,000 hash lookups. Choosing the container is often the entire optimization.
Counter and defaultdict are dict subclasses with convenience behaviour layered on. Counter adds counting and ranking; defaultdict auto-creates missing values via a factory. Because they are dicts, everything you know about dict performance and methods still applies.
Validation & Testing
Benchmark list in versus set in on a large collection and confirm the set is dramatically faster. Pass criteria: correct aggregation output and measured O(1) lookup advantage for the set/dict path.
Advanced: Troubleshooting
- Slow membership: repeated
x in listis O(n); convert to a set once. - KeyError: use
dict.getordefaultdictfor missing keys. - Unhashable key: only immutable types can be dict keys or set members.
Troubleshooting
| Symptom | Likely cause | Fix |
|---|---|---|
| Counter on unhashable items raises TypeError | lists or dicts cannot be dict keys | convert to a hashable form first, e.g. tuples |
| defaultdict creates entries on read | accessing groups[key] inserts the default | use .get() or check membership when probing without inserting |
| set lost the ordering | sets are unordered by design | use dict.fromkeys() or a list plus a seen-set when order matters |
| dict lookup still slow | keys with expensive or colliding __hash__ | profile the hash; prefer small immutable keys like ints, strings, tuples |
| memory grew unexpectedly | Counter/defaultdict kept every distinct key of a huge stream | aggregate in bounded windows or spill to disk for unbounded streams |
Key Results
- Cut a membership-check hot path from O(n) to O(1) with a set.
- Simplified aggregation using Counter and defaultdict.
- Mapped 4 container types to their complexity profiles.
- Documented when each structure is the right choice.
Key Takeaways
- Choose containers by Big-O: sets and dicts give O(1) average lookups.
- Counter replaces hand-rolled counting loops with ranked results in one call.
- defaultdict eliminates key-existence boilerplate in grouping code.
- Membership testing is the classic O(n) to O(1) win: use a set.
- All three helpers are dicts underneath, so dict semantics still apply.
Practice Challenges
Challenge 1: Hot path audit
Goal: Take a script that checks membership against a list in a loop, convert it to a set, and benchmark both with timeit on 10k items.
Hint: Build the set once outside the loop; measure only the lookup loop.
Challenge 2: Log grouper
Goal: Group web log lines by status code with defaultdict(list), then rank codes with Counter.
Hint: Parse each line once into (code, line), then feed codes to Counter separately.