Skip to content

About

Naive vs. optimized implementations (duplicates, top-k, report building) with tests proving equivalence and real measured benchmarks.

Resources

Stars

0 stars

Watchers

0 watching

Forks

Latest commit

 

History

3 Commits

Folders and files

NameName
Last commit message
Last commit date
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

python-perf-optimization

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.

Case studies

1. find_duplicates: nested loop → single-pass set

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

2. top_k_frequent: list.count() per unique item → Counter + heapq.nlargest

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

3. build_report: aliased string += → list + join

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.)

Running it yourself

pip install pytest
pytest -v                     # 7 tests: proves naive and optimized always agree
python benchmarks/bench.py    # regenerates the tables above

Project structure

perfopt/
  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

About

Naive vs. optimized implementations (duplicates, top-k, report building) with tests proving equivalence and real measured benchmarks.

Resources

Stars

0 stars

Watchers

0 watching

Forks

Releases

Packages

Contributors

Languages