Python performance advice often starts too low. Replace a loop with a comprehension. Cache a bound method. Avoid an extra function call. Such changes can matter in a proven hot loop, but none rescues an algorithm that scans the same 10,000 records for each of 20,000 events.
The durable question is not "which spelling makes this operation faster?" It is "why does this operation happen so many times?" A useful data structure, index, batch boundary, or precomputed result can remove orders of magnitude of work while leaving straightforward Python behind.
Test environment. All recorded measurements used
.venv/bin/python, CPython 3.14.7, arm64, macOS 26.5.2, traditional GIL enabled, optimization level 0, and a non-debug build. The machine had ordinary background activity. Timings and constant-factor crossover points will vary; growth, equivalent outputs, and commands are the reproducible evidence.
Every experiment below uses fixed inputs and repeated timings. Run complete listings from the repository root. The best repeat is reported as a lower bound, while the commands retain all repeats for inspection.
Complexity needs the actual workload
Big-O describes how resource use grows, not how many milliseconds Python promises. Let n be stored records and q be queries. Scanning a list once is O(n). Scanning it for every query is O(qn). Building a set costs expected O(n) and each membership query is expected O(1), making the whole phase expected O(n + q).
Those statements omit constants, memory, hash and equality costs, input distributions, and worst cases. They also omit semantics. A set removes duplicates and requires hashable elements; a sorted list preserves duplicates and supports ordered traversal; a dictionary associates keys with values. Choose a valid structure before timing one.
Python-aware analysis also counts expensive callbacks. sorted(records, key=parse_date) calls the key once per record, but a comparison function adapted through cmp_to_key may be called O(n log n) times. Dictionary lookup is expected constant time only when hashing and equality behave well. A "constant-time" lookup whose custom key hashes a megabyte is not constant with respect to key size.
Experiment 1: observe growth, not one size
Compare absent membership at three sizes:
.venv/bin/python - <<'PY'
import timeit
for size in (10, 1_000, 100_000):
values = list(range(size))
index = set(values)
missing = -1
list_runs = timeit.repeat(lambda: missing in values, number=1_000, repeat=5)
set_runs = timeit.repeat(lambda: missing in index, number=1_000, repeat=5)
print(
size,
f"list={min(list_runs) / 1_000 * 1e9:.1f}ns",
f"set={min(set_runs) / 1_000 * 1e9:.1f}ns",
)
PY
Our list results grew from about 124 ns to 9.02 us to 1.012 ms. Set lookups stayed around 27 to 36 ns. The 100,000-element set lookup was about 27,700 times faster than the absent list scan, but that sentence deliberately excludes set construction.
Absent lookup is the list's full scan. A hit at index zero behaves differently; random hits scan about half the list on average under a uniform distribution. Benchmark production hit rates and positions. Fix PYTHONHASHSEED when cross-process hash layout could add noise, but do not mistake a fixed seed for portable timing.
Experiment 2: include construction and find the reuse boundary
Converting to a set for one tiny query can add work. Time the entire decision:
.venv/bin/python - <<'PY'
import random
import timeit
rng = random.Random(42)
values = list(range(10_000))
for query_count in (1, 10, 100, 1_000):
queries = [rng.randrange(20_000) for _ in range(query_count)]
def scan():
return [query in values for query in queries]
def indexed():
lookup = set(values)
return [query in lookup for query in queries]
assert scan() == indexed()
scan_runs = timeit.repeat(scan, number=1, repeat=7)
index_runs = timeit.repeat(indexed, number=1, repeat=7)
print(query_count, min(scan_runs), min(index_runs))
PY
The important result is the crossover, not a universal number. Construction is O(n), so an index pays when enough repeated queries amortize it. If callers reuse the same immutable dataset for thousands of requests, build once at that lifecycle boundary rather than once per function call. If data changes, include index maintenance and consistency in the design.
Memory is also part of the choice. Sets maintain a sparse hash table and usually occupy more shallow storage than a list of the same references. Measure complete process behavior when millions of indexes are plausible.
Experiment 3: choose membership semantics deliberately
The same-looking in operator can ask different questions:
allowed_list = ["read", "write", "read"]
allowed_set = {"read", "write"}
owners = {"report-7": "alice", "report-8": "bob"}
assert "read" in allowed_list
assert "read" in allowed_set
assert "report-7" in owners # dictionary keys
assert "alice" in owners.values() # linear scan of values
print("[state] list preserves duplicates:", allowed_list)
print("[state] set keeps unique permissions:", sorted(allowed_set))
print("[check] dictionary membership checks keys:", "report-7" in owners)
print("[check] value lookup scans values:", "alice" in owners.values())
List and tuple membership use equality while scanning in order. Set and dictionary-key membership use hashing and equality, with expected constant-time lookup. dict.values() does not gain a reverse index merely because it belongs to a dictionary.
Do not replace a list with a set if duplicate count or order is required. Do not create a reverse dictionary unless values are unique or collisions have defined handling. Complexity cannot repair changed behavior.
Custom equality can dominate every structure:
class UserKey:
def __init__(self, tenant, name):
self.tenant = tenant
self.name = name
def __hash__(self):
return hash((self.tenant, self.name))
def __eq__(self, other):
return (
isinstance(other, UserKey)
and (self.tenant, self.name) == (other.tenant, other.name)
)
Hashes must remain stable while stored, and equal objects must have equal hashes. Pathological collisions can degrade hash-table lookup toward linear behavior. Expected O(1) is a design model, not a latency guarantee for adversarial keys.
Experiment 4: sort once, not once per query
Repeatedly sorting inside a query is a structural bug:
.venv/bin/python - <<'PY'
import bisect
import random
import timeit
rng = random.Random(42)
values = list(range(20_000))
rng.shuffle(values)
queries = [rng.randrange(25_000) for _ in range(5_000)]
def repeated_sort():
return [query in sorted(values) for query in queries]
def sorted_once():
ordered = sorted(values)
found = []
for query in queries:
position = bisect.bisect_left(ordered, query)
found.append(position < len(ordered) and ordered[position] == query)
return found
def set_once():
lookup = set(values)
return [query in lookup for query in queries]
assert repeated_sort() == sorted_once() == set_once()
for candidate in (repeated_sort, sorted_once, set_once):
runs = timeit.repeat(candidate, number=1, repeat=3)
print(candidate.__name__, [round(t, 4) for t in runs])
PY
Our best times were 10.74 seconds, 0.00336 seconds, and 0.000605 seconds. Repeated sorting costs roughly O(q * n log n). Sorting once and binary searching costs O(n log n + q log n). Building a set and querying it costs expected O(n + q).
The set wins this exact membership-only workload. The sorted list supports range queries, nearest-neighbor positions, ordered output, and duplicates; it may be the better product design. If values are already sorted, do not sort again. If updates are frequent, account for insertion or rebuild costs rather than benchmarking a read-only snapshot.
Experiment 5: compute sort keys once
Python's sort accepts a key function specifically to avoid repeated comparison work:
.venv/bin/python - <<'PY'
from functools import cmp_to_key
import timeit
records = [f"item-{number:05d}" for number in range(5_000, 0, -1)]
def parse(record):
return int(record.removeprefix("item-"))
key_calls = 0
def key(record):
global key_calls
key_calls += 1
return parse(record)
comparison_calls = 0
def compare(left, right):
global comparison_calls
comparison_calls += 1
return (parse(left) > parse(right)) - (parse(left) < parse(right))
by_key = sorted(records, key=key)
by_comparison = sorted(records, key=cmp_to_key(compare))
assert by_key == by_comparison
print("key calls:", key_calls)
print("comparison calls:", comparison_calls)
print(timeit.repeat(lambda: sorted(records, key=parse), number=20, repeat=5))
print(timeit.repeat(lambda: sorted(records, key=cmp_to_key(compare)), number=20, repeat=5))
PY
The key is evaluated exactly once per input element. A comparison callback can run many times and this example parses both sides repeatedly. CPython's Timsort may exploit existing order, so comparison counts depend on input shape; that variability strengthens the rule to use key when sorting by a derived value.
Precomputation is not automatically memoization. The temporary key array belongs to the sort and is discarded afterward. Persistent caching introduces invalidation, memory, and concurrency questions that a local sort key avoids.
Experiment 6: batching removes boundary costs
Batching cannot improve complexity when both versions remain linear, but it can remove repeated Python calls, network round trips, transactions, or serialization boundaries. Start with a local demonstration:
.venv/bin/python - <<'PY'
import timeit
values = list(range(100_000))
def square(value):
return value * value
def individual():
return [square(value) for value in values]
def batched():
return [value * value for value in values]
assert individual() == batched()
for candidate in (individual, batched):
runs = timeit.repeat(candidate, number=10, repeat=5)
print(candidate.__name__, min(runs) / 10)
PY
We observed about 4.67 ms versus 3.97 ms. That modest 15% difference is only Python call overhead and is exactly the kind of micro-optimization not worth architectural complexity by itself.
Now imagine each call is a 5 ms database round trip. One thousand sequential calls have about five seconds of latency before useful work; one bulk query can eliminate most boundaries. Real batching has limits: maximum request size, memory, transactions, partial failures, backpressure, and tail latency. Measure representative batch sizes rather than making "one giant batch" the new rule.
Experiment 7: precompute an invariant, with ownership
Suppose requests repeatedly normalize the same catalog names:
def search_slow(catalog, query):
normalized_query = query.casefold()
return [
item for item in catalog
if normalized_query in item["name"].casefold()
]
def build_search_rows(catalog):
return [(item["name"].casefold(), item) for item in catalog]
def search_precomputed(rows, query):
normalized_query = query.casefold()
return [item for normalized, item in rows if normalized_query in normalized]
Both searches remain O(n) per query, but the second removes repeated normalization. The index has a lifecycle: build it when the catalog snapshot is accepted, publish it with that snapshot, and replace both atomically. Mutating catalog items behind the index creates stale answers.
Precompute when a value is expensive, reused, and based on stable inputs. Do not precompute everything "just in case." Build time can hurt startup, retained data consumes memory, and invalidation can be harder than the original calculation. Often a dictionary keyed by the exact query field changes the algorithm more than caching normalized strings does.
Experiment 8: a realistic event-to-user join
An analytics job needs spending from professional users. The direct translation searches all users for every event:
.venv/bin/python - <<'PY'
import random
import timeit
rng = random.Random(42)
users = [
{"id": user_id, "tier": "pro" if user_id % 5 == 0 else "free"}
for user_id in range(10_000)
]
events = [
{"user_id": rng.randrange(10_000), "amount": rng.randrange(1, 100)}
for _ in range(20_000)
]
def nested_scan():
total = 0
for event in events:
user = next(user for user in users if user["id"] == event["user_id"])
if user["tier"] == "pro":
total += event["amount"]
return total
def indexed_join():
users_by_id = {user["id"]: user for user in users}
return sum(
event["amount"]
for event in events
if users_by_id[event["user_id"]]["tier"] == "pro"
)
assert nested_scan() == indexed_join() == 198_563
for candidate in (nested_scan, indexed_join):
runs = timeit.repeat(candidate, number=1, repeat=3)
print(candidate.__name__, [round(t, 4) for t in runs])
PY
Our best nested scan took 2.990 seconds. The indexed join, including dictionary construction, took 0.00250 seconds: about 1,200 times faster with the same total.
Let u be users and e events. The scan is O(eu) in the worst case. The indexed version is expected O(u + e) and retains O(u) extra references. Moving the dictionary comprehension outside the function could save more when the user snapshot serves many batches, but only if its owner updates it correctly.
Production rules need explicit error semantics. next(...) raises StopIteration for an unknown user while dictionary indexing raises KeyError. The generated data guarantees matches, but a real refactor must preserve or deliberately change missing-user handling, duplicate user IDs, ordering, and authorization behavior.
Algorithm before micro-optimization
After selecting the indexed algorithm, you could compare sum() with an explicit accumulator, cache dictionary lookups in local variables, or adjust comprehension spelling. Those changes compete over fractions of 2.5 ms. The algorithm removed nearly three seconds.
Amdahl's law supplies a useful ceiling. If a hot function is 20% of runtime, making it infinitely fast improves the whole program by at most 1.25x. Removing a repeated outer scan can change the fraction itself. Profile first, model operation counts, then optimize the largest removable term.
Use this decision sequence:
- Define required outputs, ordering, duplicates, errors, and update behavior.
- Name input dimensions and count repeated operations in terms of them.
- Look for scans inside loops, repeated sorting, repeated parsing, and remote calls.
- Choose a structure or boundary that removes work without changing semantics.
- Include construction, maintenance, memory, and invalidation at their real lifecycle.
- Assert equivalent outcomes on representative and adversarial inputs.
- Benchmark the complete boundary and remeasure end to end.
- Consider local micro-optimizations only if meaningful time remains there.
Exercises
- Repeat membership measurements for hits at the beginning, middle, and end of a list. Build a weighted result using your application's hit distribution.
- Find the query-count crossover where building a set beats repeated scans for sizes 100, 10,000, and 1,000,000. Include shallow memory measurements with
sys.getsizeof()and state their exclusions. - Extend the sorting experiment with range queries. Explain why a sorted list can become preferable even when a set wins exact membership.
- Modify the event join to support unknown users and duplicate user records. Define semantics before selecting the index representation.
- Find a repeated I/O boundary in an application and design a bounded batch. List partial-failure and backpressure behavior before benchmarking it.
Keep this model
Complexity is an operation-counting tool tied to named input dimensions, not a slogan attached to a container. Python's fast built-ins improve constants; sets, dictionaries, one-time sorting, batches, and precomputed indexes can remove whole dimensions of work. Include their construction and lifecycle, preserve semantics, and verify the result on realistic inputs.
The fastest membership test, comparison, parser call, or network request is the one a better algorithm never needs to perform.