Three real anti-patterns, each with a naive baseline, an optimized fix, tests proving they're behaviorally identical, and a benchmark proving the optimized version is actually faster — with real measured numbers, not estimates.
Naive checks every element against every other element (O(n²)). Optimized tracks what's been seen in a set and does one pass (O(n)).
| n items | naive (s) | optimized (s) | speedup |
|---|---|---|---|
| 500 | 0.0026 | 0.0000 | 122x |
| 2,000 | 0.0521 | 0.0001 | 446x |
| 8,000 | 0.7486 | 0.0004 | 1967x |
Naive calls list.count() once per unique item — each call is its own O(n) scan, so total work is O(n·u) where u is the number of unique items. Optimized builds all frequencies in one O(n) pass with Counter, then finds the top k in O(n log k) with heapq.nlargest instead of sorting every unique item.
| n items | naive (s) | optimized (s) | speedup |
|---|---|---|---|
| 1,000 | 0.0002 | 0.0001 | 3.2x |
| 10,000 | 0.0022 | 0.0003 | 7.9x |
| 100,000 | 0.0221 | 0.0032 | 6.9x |
This one's less obvious, and worth reading closely. CPython specifically optimizes s += x to resize the string in place when s has a reference count of 1 — so the textbook "+= in a loop is O(n²)" claim doesn't actually hold up in a plain loop on modern CPython. It only becomes O(n²) again once something else keeps a reference to the string alive on each iteration (breaking the refcount-1 fast path), which is exactly what happens in a common real pattern: building a report while also keeping an audit trail of every intermediate version, e.g. audit_trail.append(report). That one extra reference forces a full copy on every line.
The optimized version keeps a list of parts and joins once at the end, and stores the part count in the audit trail instead of a full string snapshot — so a historical version can be reconstructed on demand instead of being copied unconditionally on every line.
| n lines | naive (s) | optimized (s) | speedup |
|---|---|---|---|
| 1,000 | 0.0006 | 0.0001 | 6.8x |
| 5,000 | 0.0184 | 0.0004 | 50x |
| 20,000 | 0.2949 | 0.0028 | 105x |
(Numbers above are from a single local run on this machine — see "Reproducing the numbers" below. Absolute timings will vary by machine; the trend — naive getting relatively worse as n grows, optimized staying roughly linear — is the point.)
pip install pytest
pytest -v # 7 tests: proves naive and optimized always agree
python benchmarks/bench.py # regenerates the tables aboveperfopt/
naive.py # baseline implementations, with anti-patterns documented inline
optimized.py # fixed implementations
tests/
test_equivalence.py # naive and optimized must return identical results on randomized input
benchmarks/
bench.py # times both versions at increasing input sizes