Python Lists & Dictionaries | collections & Big-O

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.

Environment & Prerequisites

Python 3.11 with the standard library collections module.
A dataset to aggregate (for example log lines).
timeit for comparing lookups.

flowchart LR Q[Access pattern?] --> O{Membership / lookup?} O -->|yes| S[set / dict O(1)] O -->|ordered sequence| L[list] Q --> A{Counting?} A -->|yes| C[Counter]

Step-by-Step Execution

1. Aggregate with Counter

python -c "from collections import Counter; print(Counter('mississippi').most_common(2))"

2. O(1) membership with a set

python -c "allow={'a','b'}; print('a' in allow)"

3. Group with defaultdict

from collections import defaultdict
groups = defaultdict(list)
for ip, port in events:
    groups[ip].append(port)

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 list is O(n); convert to a set once.
KeyError: use dict.get or defaultdict for missing keys.
Unhashable key: only immutable types can be dict keys or set members.

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.

Python Lists, Dictionaries, and the collections Module