Concepts Examples

Example: choosing a representation

Suppose a program needs to check whether a username is banned.

If the banned users are stored as a list:

banned = ["alice", "bob", "charlie"]
"bob" in banned

lookup scans through entries, so the cost grows roughly with the number of banned users. If the list has millions of users, this becomes painful.

If the banned users are stored as a set:

banned = {"alice", "bob", "charlie"}
"bob" in banned

lookup is usually close to constant time. Same information, different representation, very different scaling. i.e. HashMaps are O(1) time instead of O(N), which won’t most of the time until N >>>> 1

Example: invariant thinking

For a sorted array, a useful invariant is:

for every i < j: array[i] <= array[j]

If a binary search fails, check this invariant before staring at the search code. If the array was never sorted, the binary search is not the villain; it is faithfully applying an assumption that the caller violated.

Example: interface contract

A function contract might say:

input: non-empty list of numbers
output: arithmetic mean
side effects: none
errors: raises ValueError for empty list

Without the empty-list rule, callers and implementers guess different behaviours: return 0, return NaN, raise an error, or silently divide by zero. Clear contracts remove that ambiguity.

Current local links

• Concepts Key concepts
• Concepts Equations and definitions
• Concepts Common pitfalls
• Concepts index

Example: debugging by changing one assumption

If a program is slow, do not only ask “which line is slow?” Ask which concept is wrong: representation, algorithm, I/O pattern, cache behaviour, or interface contract. Changing a list to a set, batching file reads, or removing hidden state can beat micro-optimising a single line.