Transform code to reduce time and space complexity while maintaining correctness. Focus on proven optimization patterns across C++, Java, and Python.
Core principle: Measurably improve complexity, verify behavior unchanged.
Use for ANY performance-related work:
Use ESPECIALLY when:
| Symptom | Likely Issue | Quick Fix |
|---|---|---|
| --------- | -------------- | ----------- |
| Nested loops over same data | O(N^2) | Hash table or two pointers |
| Lookup in unsorted list | O(N) per lookup | Convert to set/hash |
| String concat in loop | O(N^2) memory churn | StringBuilder/reserve |
| Repeated sorting | O(N log N) each | Sort once, cache sorted |
| Recursion explosion | Exponential | Memoization/DP |
| Vector growth without reserve | Multiple allocations | Pre-allocate capacity |
Follow these steps for every optimization:
Optimization Progress:
- [ ] Step 1: Identify current complexity
- [ ] Step 2: Analyze bottleneck source
- [ ] Step 3: Select optimization strategy
- [ ] Step 4: Implement minimal change
- [ ] Step 5: Verify complexity improvement
- [ ] Step 6: Confirm behavior unchanged
Step 1: Identify current complexity
Step 2: Analyze bottleneck source
| Pattern | Likely Bottleneck |
|---|---|
| --------- | ------------------- |
| Nested iteration over same data | O(N^2) from double loop |
| Lookup in unsorted list/array | O(N) per lookup |
| Repeated sorting | O(N log N) per sort |
| String concatenation in loop | O(N^2) from repeated copies |
| Recursion without memoization | Exponential branching |
| Large object creation in loop | Memory pressure + GC overhead |
Step 3: Select optimization strategy
See Algorithm Selection Decision Tree below.
Step 4: Implement minimal change
Step 5: Verify complexity improvement
Step 6: Confirm behavior unchanged
digraph algorithm_selection {
rankdir=TB;
"Nested loops identified?" [shape=diamond];
"Lookup operation?" [shape=diamond];
"Hash Table\n(O(1) lookup)" [shape=box, style=filled, fillcolor="#ccffcc"];
"Range query?" [shape=diamond];
"Tree/Heap\n(O(log N) query)" [shape=box, style=filled, fillcolor="#ccffcc"];
"Sliding pattern?" [shape=diamond];
"Two Pointers/Window\n(O(N))" [shape=box, style=filled, fillcolor="#ccffcc"];
"Subproblem reuse?" [shape=diamond];
"DP/Memoization\n(Polynomial)" [shape=box, style=filled, fillcolor="#ccffcc"];
"Ordering needed?" [shape=diamond];
"Pre-sort once\n(O(N log N))" [shape=box, style=filled, fillcolor="#ccffcc"];
"Keep nested loops\n(document constraint)" [shape=box, style=filled, fillcolor="#ffcccc"];
"Nested loops identified?" -> "Lookup operation?";
"Lookup operation?" -> "Hash Table\n(O(1) lookup)" [label="yes"];
"Lookup operation?" -> "Range query?";
"Range query?" -> "Tree/Heap\n(O(log N) query)" [label="yes"];
"Range query?" -> "Sliding pattern?";
"Sliding pattern?" -> "Two Pointers/Window\n(O(N))" [label="yes"];
"Sliding pattern?" -> "Subproblem reuse?";
"Subproblem reuse?" -> "DP/Memoization\n(Polynomial)" [label="yes"];
"Subproblem reuse?" -> "Ordering needed?";
"Ordering needed?" -> "Pre-sort once\n(O(N log N))" [label="yes"];
"Ordering needed?" -> "Keep nested loops\n(document constraint)" [label="no - inherent O(N^2)"];
}
Decision explanations:
| Decision | Condition | Strategy | Result |
|---|---|---|---|
| ---------- | ----------- | ---------- | -------- |
| Hash Table | Repeated lookup needed | Replace list lookup with set/map | O(N) -> O(1) per lookup |
| Tree/Heap | Need min/max/range queries | Use ordered structure | O(N) -> O(log N) per query |
| Two Pointers | Contiguous range pattern | Replace nested loop with pointers | O(N^2) -> O(N) |
| DP/Memo | Same subproblems calculated | Cache results | O(2^N) -> O(N) or O(N^2) |
| Pre-sort | Ordering enables simpler logic | Sort once, use sorted property | Varies |
| Anti-Pattern | Detection Signal | Impact | Fix |
|---|---|---|---|
| -------------- | ------------------ | -------- | ----- |
| List lookup in loop | in list inside for | O(N^2) | Use set() |
| String concat in loop | += on strings in loop | O(N^2) memory | StringBuilder |
| Unreserved growth | push_back/append only | Multiple allocations | .reserve(N) |
| Repeated sorting | sort() inside loop | O(N log N) each | Sort once |
| Recursion explosion | Recursive call, no memo | O(2^N) | Memoization |
Full anti-pattern details: See references/anti-patterns.md
Optimization patterns library: See references/optimization-patterns.md
Complete examples: See references/examples.md
Complexity formulas: See references/complexity-formulas.md
| Language | Key Optimizations |
|---|---|
| ---------- | ------------------- |
| C++ | reserve(), unordered_map, move semantics, std::span, range-based algorithms |
| Java | StringBuilder with capacity, primitive streams (IntStream), ArrayDeque |
| Python | List comprehensions, collections module, generators, set() for membership |
If you catch yourself thinking:
All of these mean: STOP. Follow the workflow.
| Excuse | Reality |
|---|---|
| -------- | --------- |
| "Issue is simple, no need to analyze" | Simple issues have root causes too. Calculate first. |
| "Just try this fix first" | First fix sets the pattern. Do it right from the start. |
| "Tests pass so optimization works" | Tests pass != complexity improved. Measure. |
| "Multiple optimizations at once" | Can't isolate what worked. One change only. |
| "I'll measure later" | Measurement proves optimization. Do it now. |
DO NOT guess constraints for critical performance code. Ask:
Before claiming optimization success:
Language-specific profiling commands:
C++:
g++ -O2 -pg solution.cpp -o solution
./solution input.txt
gprof solution gmon.out > analysis.txt
Java:
java -Xprof Solution
Python:
python -m cProfile -s tottime solution.py
Scaling test:
for size in 100 1000 10000 100000; do
time ./solution input_${size}.txt
done
# Expected: Linear scaling for O(N), log-linear for O(N log N)
# Warning: Quadratic scaling (2x size -> 4x time) indicates O(N^2)
共 2 个版本