Build 6 — Profile and Optimize a Slow Program

# Build 6 — Profile and Optimize a Slow Program ## The brief Given a slow Python program, profile it, identify the bottleneck, fix it. Goal: 10x or more speedup. ## The slow program ```python # slow.py import random import time def find_duplicates(arr): """Find duplicates in arr.""" duplicates = [] for i, x in enumerate(arr): for j, y in enumerate(arr): if i != j and x == y and x not in duplicates: duplicates.append(x) return duplicates def count_word_freq(text): """Count word frequencies.""" words = text.split() freq = {} for w in words: count = 0 for w2 in words: if w == w2: count += 1 freq[w] = count return freq def find_pairs_summing_to(arr, target): """Find pairs that sum to target.""" pairs = [] for i, x in enumerate(arr): for j, y in enumerate(arr): if i < j and x + y == target: pairs.append((x, y)) return pairs def main(): # Test data arr = [random.randint(1, 1000) for _ in range(5000)] text = " ".join(random.choice(["foo", "bar", "baz", "qux"]) for _ in range(10000)) start = time.time() dups = find_duplicates(arr) print(f"find_duplicates: {time.time() - start:.2f}s ({len(dups)} duplicates)") start = time.time() freq = count_word_freq(text) print(f"count_word_freq: {time.time() - start:.2f}s ({len(freq)} unique words)") start = time.time() pairs = find_pairs_summing_to(arr, 1000) print(f"find_pairs_summing_to: {time.time() - start:.2f}s ({len(pairs)} pairs)") if __name__ == "__main__": main() ``` Run it. You should see times like: - find_duplicates: ~10s - count_word_freq: ~3s - find_pairs_summing_to: ~10s Total: 20-30 seconds. Goal: under 1 second. ## Step 1: Profile (10 min) ```bash python -m cProfile -o profile.out slow.py python -c "import pstats; pstats.Stats('profile.out').sort_stats('cumulative').print_stats(20)" ``` You'll see: - Most time in `find_duplicates` and `find_pairs_summing_to`. - Inner loops dominate. ## Step 2: Identify the bottleneck per function ### find_duplicates: O(N²) nested loop + O(N) in-list check ```python # Bottleneck: nested loops + `x not in duplicates` for i, x in enumerate(arr): for j, y in enumerate(arr): if i != j and x == y and x not in duplicates: # 3 O(N) operations duplicates.append(x) ``` Complexity: O(N²) outer, O(N) for `not in duplicates` = O(N³). Catastrophic. ### count_word_freq: O(N²) nested counting ```python for w in words: for w2 in words: # O(N²) for each word ... ``` Complexity: O(N²). Should be O(N) with a hashmap. ### find_pairs_summing_to: O(N²) nested ```python for i, x in enumerate(arr): for j, y in enumerate(arr): if i < j and x + y == target: # check every pair ``` Complexity: O(N²). Possible to do O(N) with a hashmap. ## Step 3: Optimize (20 min) ### Optimized find_duplicates Use sets: ```python def find_duplicates_fast(arr): seen = set() duplicates = set() for x in arr: if x in seen: duplicates.add(x) else: seen.add(x) return list(duplicates) ``` O(N) instead of O(N³). 1000x faster on 5000 elements. ### Optimized count_word_freq Use Counter: ```python from collections import Counter def count_word_freq_fast(text): return dict(Counter(text.split())) ``` O(N) instead of O(N²). 5000x faster. ### Optimized find_pairs_summing_to Use hashmap: ```python def find_pairs_summing_to_fast(arr, target): seen = {} pairs = [] for i, x in enumerate(arr): complement = target - x if complement in seen: pairs.append((complement, x)) seen[x] = i return pairs ``` O(N) instead of O(N²). 5000x faster. (Note: the optimized version uses values as keys; works because we only need values, not indices. If indices mattered, use a multimap.) ## Step 4: Measure improvement (10 min) ```python # fast.py import time import random from collections import Counter def find_duplicates_fast(arr): seen = set() duplicates = set() for x in arr: if x in seen: duplicates.add(x) else: seen.add(x) return list(duplicates) def count_word_freq_fast(text): return dict(Counter(text.split())) def find_pairs_summing_to_fast(arr, target): seen = set() pairs = [] for x in arr: complement = target - x if complement in seen: pairs.append((complement, x)) seen.add(x) return pairs def main(): arr = [random.randint(1, 1000) for _ in range(5000)] text = " ".join(random.choice(["foo", "bar", "baz", "qux"]) for _ in range(10000)) start = time.time() dups = find_duplicates_fast(arr) print(f"find_duplicates_fast: {time.time() - start:.4f}s ({len(dups)} duplicates)") start = time.time() freq = count_word_freq_fast(text)