Data Structures: Advanced

Count, group, and queue with one import

The collections module provides specialized container datatypes that extend Python's built-in list, dict, tuple, and set. Each solves a specific problem more elegantly and efficiently than the general-purpose alternatives. Learning these tools means writing less code that runs faster.

A Counter is a dictionary subclass designed for counting hashable objects. Instead of manually building a dict with counts, Counter does it in one line. It also provides methods for finding the most common elements, arithmetic between counters, and more.

Counter is invaluable for log analysis, frequency distributions, and any scenario where you need to tally occurrences. It accepts any iterable and counts elements automatically. Accessing a missing key returns 0 instead of raising a KeyError, which is a subtle but important improvement over regular dicts.

A defaultdict automatically creates a default value when you access a missing key. Instead of checking if a key exists before using it, you just use it. This eliminates the setdefault() pattern entirely and makes grouping code much cleaner.

The factory function you pass to defaultdict determines the default value type. Pass list for grouping, int for counting, set for unique collections, or any callable that returns the default value you want.

from collections import defaultdict
counts = defaultdict(___)
for char in "hello":
    counts[char] += 1
print(counts["l"])
print(___(counts))

A deque (pronounced "deck") supports O(1) append and pop from both ends. Lists are fast at the right end but slow at the left because inserting at position 0 requires shifting every element. Deques solve this with a doubly-linked list implementation.

The maxlen parameter creates a bounded deque that automatically discards old items when full. This is perfect for sliding windows, recent activity logs, and any scenario where you only care about the last N items. No manual size management needed.

from collections import deque
recent = deque(maxlen=3)
for x in [1, 2, 3, 4, 5]:
    recent.___(x)
print(list(recent))
print(___(recent))

A namedtuple creates an immutable record type with named fields. It uses the same memory as a regular tuple but lets you access fields by name instead of index. This dramatically improves code readability while keeping the memory efficiency of tuples.

Named tuples are ideal for representing fixed records like database rows, CSV records, or API response objects. They are hashable (so they can be dictionary keys), immutable (so they are thread-safe), and self-documenting (so the code is readable).

Build memory-efficient record types

The @dataclass decorator automatically generates __init__, __repr__, and __eq__ methods from your type-annotated fields. Add frozen=True for immutability, or order=True for comparison operators.

Notice the field(default_factory=list) for the tags field. This avoids the mutable default argument bug from the intermediate lesson. Each instance gets its own fresh list instead of sharing one across all instances.

Adding frozen=True makes a dataclass immutable and hashable, combining the safety of tuples with the readability of named fields. Frozen dataclasses are ideal for configuration objects, cache keys, and any data that should not change after creation.

from dataclasses import dataclass

@dataclass(___frozen=Trueorder=True)
class DbConfig:
    host: str
    port: int

c = DbConfig("localhost", 5432)
print(type(___hash(c)c))

By default, Python objects store attributes in a __dict__ dictionary, which is flexible but memory-hungry. Declaring __slots__ tells Python to allocate a fixed amount of memory for each instance, eliminating the per-instance dict. For millions of objects, this saves gigabytes.

The real savings come from eliminating the __dict__ overhead. For classes with few attributes that you create millions of times, __slots__ can reduce memory by 40-50%. Modern dataclasses also support slots=True in Python 3.10 and later.

dataclass

Auto-generated methods, type hints, defaults. Best for most record types.

namedtuple

Immutable, lightweight, hashable. Best for read-only records.

__slots__

Memory-optimized classes. Best for millions of identical small objects.

TypedDict

Type hints for dicts without runtime overhead. Best for JSON-shaped data.

Measure time and memory trade-offs

Choosing the right data structure requires understanding their actual performance characteristics. Theoretical Big-O complexity tells you the growth rate, but real-world performance depends on constant factors, cache behavior, and memory allocation patterns. Python provides tools like timeit and sys.getsizeof() to measure both time and memory so you can make informed decisions.

The timeit module runs code snippets thousands of times and reports accurate timing. This eliminates noise from system load and gives reproducible measurements. Always benchmark with realistic data sizes - performance at 100 items may differ dramatically from performance at 1 million.

The difference is staggering. For 100,000 elements with worst-case lookup, sets are thousands of times faster. This is the practical consequence of O(n) versus O(1) that you saw in theory - now you can measure it yourself.

Memory usage is equally important, especially when processing large datasets. Each data structure has different overhead per element. Understanding these costs helps you choose structures that fit within your memory budget. Use sys.getsizeof() to measure actual sizes.

import ___
data = [1, 2, 3, 4, 5]
print(sys.___(data))
print(type(data).__name__)

Remember that sets and dicts trade memory for speed. When memory is the constraint, tuples and frozensets are your allies. When speed is the constraint, hash-based structures like sets and dicts give you O(1) operations.

Understanding these performance characteristics helps you reason about which structure belongs in each part of a pipeline. A sliding window uses a deque, a lookup table uses a dict, and a deduplication pass uses a set.

Cache results to skip repeated work

The simplest caching tool is @lru_cache from functools. It automatically memoizes function results based on arguments. LRU stands for Least Recently Used - when the cache is full, the least recently accessed entry is evicted to make room for new ones.

Notice that the database query message only prints once. The second call returns the cached result without executing the function body. The cache_info() method shows hits, misses, and current size, letting you monitor cache effectiveness.

For more control over caching behavior, you can build a custom LRU cache using OrderedDict. This approach lets you add TTL (time-to-live) expiration, custom eviction logic, and size-based limits that lru_cache does not support.

The move_to_end() method is the key to LRU behavior. Every access moves the item to the end (most recently used). When the cache exceeds capacity, popitem(last=False) removes the first item (least recently used). This gives you O(1) get, put, and eviction operations.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

from collections import OrderedDict
cache = OrderedDict()
cache["a"] = 1
cache["b"] = 2
cache["c"] = 3
_ = cache["a"]
cache["d"] = 4
if len(cache) > 3:
  cache.popitem(last=False)
print(list(cache.keys()))

Cache hit rate is the most important metric. A cache with a 90% hit rate saves nine out of ten expensive computations. Monitor it with cache_info() and adjust maxsize if hit rates are too low.

Architect data layers for production

At scale, data structure choices become architectural decisions. A pipeline processing 10 million records per hour cannot afford O(n) lookups inside a loop. A service handling 10,000 concurrent requests needs thread-safe structures. This section covers the judgment calls that distinguish senior engineers: choosing data structures based on real-world constraints like throughput, concurrency, and memory pressure.

When multiple threads or processes access shared data, you need thread-safe structures or synchronization. Python's GIL protects against data corruption for simple operations, but compound operations like "check then update" still need explicit locking. The queue module provides thread-safe alternatives to lists for producer-consumer patterns.

The Queue class handles all synchronization internally. Multiple threads can safely put() and get() without explicit locks. For priority-based processing, use PriorityQueue which always yields the smallest item first.

Streaming data

Use deque(maxlen=N) for bounded buffers or sliding windows over live feeds.

Aggregation pipelines

Use defaultdict(list) or Counter for grouping and counting in a single pass.

Hot-path caching

Use OrderedDict for LRU caches or lru_cache for pure function memoization.

Concurrent processing

Use queue.Queue for thread-safe producer-consumer patterns between workers.

High-volume records

Use namedtuple or @dataclass(slots=True) to minimize per-record memory.

from collections import ___
buffer = deque(___=5)
for i in range(8):
    buffer.append(i)
print(list(buffer))
print(len(buffer))

The collections module structures - Counter, defaultdict, deque, and OrderedDict - are available in every Python environment without additional dependencies. They are the first tools to reach for when basic types feel cumbersome.

Concurrent systems require thread-safe structures. Queue, PriorityQueue, and asyncio-based approaches eliminate data races without the complexity of manual locking. Choosing the right concurrency primitive is as important as choosing the right data structure.