Chapter 19 of 24 | Python

Data structures and algorithms

Data structures organize values; algorithms transform or query them. Choose based on the operations your program performs, then reason about correctness, time, and memory.

Search and sort

values = [8, 3, 5, 1]
values.sort()  # modifies this list
position = values.index(5)
print(values, position)

Linear search examines items one at a time and takes O(n) comparisons. Binary search takes O(log n) comparisons on sorted data. Python's bisect module supports binary-search positions in sorted lists. Sorting with list.sort modifies the list; sorted returns a new list. Python's sort is stable, so equal keys preserve their relative order.

Maps, sets, queues, and heaps

from collections import deque
import heapq

queue = deque(["first", "second"])
queue.append("third")
next_item = queue.popleft()

tasks = [(3, "write"), (1, "test")]
heapq.heapify(tasks)
priority, task = heapq.heappop(tasks)

Dictionary and set lookup is average O(1), subject to hashing behavior. A deque supports efficient operations at both ends. A heap provides efficient access to the smallest item, but is not a fully sorted list. Use collections.Counter for frequency counts and defaultdict for grouped accumulation.

Complexity and problem decomposition

Big-O describes how work grows with input size: O(1), O(log n), O(n), O(n log n), and O(n²) are common. It hides constants and hardware effects, so it helps compare scaling but does not replace measurement. Analyze nested loops by counting total iterations, and remember that a loop body may itself have a cost that depends on input size.

Recursion can model tree and divide-and-conquer problems naturally, but deep recursion can hit Python's recursion limit. An iterative solution with an explicit stack may be more robust. Dynamic programming stores results of overlapping subproblems; memoization with functools.cache can turn repeated recursion into an efficient computation.

from functools import cache

@cache
def ways_to_climb(steps):
    if steps < 0:
        return 0
    if steps == 0:
        return 1
    return ways_to_climb(steps - 1) + ways_to_climb(steps - 2)

Correctness before speed

State preconditions, output guarantees, and edge cases. A binary search requires sorted input. A heap only guarantees the smallest item at its root. A hash key must have stable hash and equality behavior while stored. Violating these assumptions can produce incorrect results even if typical examples pass.

Beginner-to-master progression

Exercises

  1. Implement linear search and compare its result with in.
  2. Count word frequency, then return the five most common words.
  3. Use a heap to process jobs by priority and explain why it is not fully sorted.
  4. Memoize a recursive solution, measure repeated work, and discuss memory costs.

Amortized analysis and memory costs

Some operations are occasionally expensive but efficient over a long sequence. Appending to a Python list is amortized O(1): most appends are cheap, while an occasional resize copies references into a larger allocation. A dictionary's average O(1) lookup similarly abstracts hashing, collision handling, resizing, and memory use. These are useful complexity models, not exact time guarantees for every input.

Space complexity matters too. A set of n elements may use substantially more memory than a list because it maintains a hash table with spare capacity. A cached recursive algorithm saves repeated computation but retains results. A generator can reduce peak memory by yielding values one at a time, at the cost of being one-pass and potentially recomputing if recreated.

Correctness with invariants

For an algorithm, state what each data structure represents before, during, and after processing. In a frequency table, the count for a key should equal the number of occurrences seen so far. In a heap, each parent must have priority no greater than its children. These invariants help find bugs that a few output examples may miss.

For a greedy algorithm, explain why the locally selected choice can be part of an optimal global result; do not rely on intuition alone. For dynamic programming, define the state, recurrence, base cases, and evaluation order. These explanations are more reusable than memorizing a code template.

Benchmarking without misleading yourself

Use repeated measurements and representative input sizes. Separate data generation from the timed section when appropriate, but also measure end-to-end time if setup is part of real usage. Use timeit for small snippets and cProfile for whole-program hotspots. Report interpreter version, hardware, input distribution, and variance.

For meaningful comparisons, verify both implementations return equivalent results and avoid timing one implementation with warm caches while another includes setup. Keep benchmark code in the project so future changes can reproduce the baseline.

Mastery checkpoint

  1. State the invariant for a heap-based scheduler and test it after each operation.
  2. Compare time and memory for a generator pipeline and a fully materialized list.
  3. Design a benchmark that measures list versus set membership, including construction when relevant.
  4. Explain the recurrence and base cases for a dynamic-programming solution you implement.
0% read