Code Optimization Prompt Templates

## Performance Analysis

### Current Complexity
- **Time:** O(n²), nested loops comparing every record pair
- **Space:** O(n), storing duplicates list

### Bottleneck Identified

```python
# Current: O(n²) - compares every pair
for i in range(len(records)):
 for j in range(i + 1, len(records)):
 if records[i]['email'] == records[j]['email']: # 2.5B comparisons for 50K
 duplicates.append(records[i])
```

For 50,000 records: ~1.25 billion comparisons.

### Optimizations (by impact)

**1. Use a hash set, O(n²) → O(n)** ⭐ Highest Impact
```python
def find_duplicates(records):
 seen = {}
 duplicates = []
 for record in records:
 email = record['email']
 if email in seen:
 duplicates.append(record)
 else:
 seen[email] = record
 return duplicates
```
- **Time:** O(n), single pass with O(1) hash lookups
- **Space:** O(n), hash table storage
- **Expected:** 50K records in ~10ms

**2. If memory-constrained, sort first**
```python
records.sort(key=lambda r: r['email']) # O(n log n)
for i in range(1, len(records)):
 if records[i]['email'] == records[i-1]['email']:
 duplicates.append(records[i])
```
- **Time:** O(n log n), dominated by sort
- **Space:** O(1) extra (in-place sort)
- **Tradeoff:** Mutates input, slightly slower than hash approach

### Tradeoffs Summary

| Approach | Time | Space | Notes |
|----------|------|-------|-------|
| Current (nested loops) | O(n²) | O(n) | Unusable at scale |
| Hash set | O(n) | O(n) | Best for speed |
| Sort + scan | O(n log n) | O(1) | Best for memory |

**Recommendation:** Use hash set approach. For 50K records:
- Current: ~3,000ms
- With hash set: ~10ms (300x faster)

## Memory Issue Analysis

**Current approach:** Loading entire 2GB file into memory as an array of objects.

**Why it fails:** 
- Raw file: 2GB
- Parsed as JS objects: ~6-8GB (string overhead, object headers, property maps)
- Exceeds 4GB limit

## Optimization Strategies

### 1. Stream Processing (Primary Fix)

Process line by line instead of loading all at once:

```javascript
const fs = require('fs');
const readline = require('readline');
const { pipeline } = require('stream/promises');

async function processCSV(filepath) {
 const stats = {
 count: 0,
 sum: 0,
 //... other aggregations
 };

 const fileStream = fs.createReadStream(filepath);
 const rl = readline.createInterface({
 input: fileStream,
 crlfDelay: Infinity,
 });

 for await (const line of rl) {
 const columns = line.split(',');
 // Process one row at a time
 stats.count++;
 stats.sum += parseFloat(columns[3]);
 // Row is garbage collected after each iteration
 }

 return stats;
}
```

**Memory usage:** ~50MB constant (buffer size) regardless of file size.

### 2. Chunked Processing (If you need batches)

```javascript
async function* readInChunks(filepath, chunkSize = 10000) {
 const rl = readline.createInterface({
 input: fs.createReadStream(filepath),
 });

 let chunk = [];
 for await (const line of rl) {
 chunk.push(parseLine(line));
 if (chunk.length >= chunkSize) {
 yield chunk;
 chunk = []; // Release memory
 }
 }
 if (chunk.length > 0) yield chunk;
}

// Usage
for await (const chunk of readInChunks('data.csv')) {
 await processChunk(chunk); // 10K rows at a time
}
```

### 3. Use Typed Arrays for Numbers

If columns are numeric:

```javascript
// Instead of: const values = [1.5, 2.3, 3.1...]
// Use: Float64Array uses 8 bytes per number vs ~24 for JS number in array
const values = new Float64Array(expectedCount);
```

### 4. Avoid String Retention

```javascript
// Bad: Holds reference to entire line
rows.push({ name: columns[0], value: columns[3] });

// Better: Only keep what you need, explicitly copy
rows.push({ 
 name: columns[0].slice(), // New string, not substring reference
 value: parseFloat(columns[3]) // Number, not string
});
```

### Memory Comparison

| Approach | Peak Memory | Speed |
|----------|-------------|-------|
| Load entire file | 6-8GB (fails) | Fast |
| Stream line by line | ~50MB | Moderate |
| Chunked (10K) | ~200MB | Fast |
| Typed arrays | ~3GB | Fast |

**Recommendation:** Stream processing. You'll use constant memory regardless of file size.

## Algorithm Analysis

**Current approach:** Full sort
- Time: O(n log n) = ~230 million operations for 10M points
- Problem: Sorting all 10M points when you only need 100

## Better Algorithms

### 1. Min-Heap / Priority Queue, O(n log k) ⭐ Recommended

Maintain a max-heap of size k (the k smallest seen so far):

```python
import heapq

def k_closest(points, k):
 # Max-heap of size k (negate distance for max-heap behavior)
 heap = []
 
 for x, y in points:
 dist = -(x*x + y*y) # Negative for max-heap
 
 if len(heap) < k:
 heapq.heappush(heap, (dist, x, y))
 elif dist > heap[0][0]: # Closer than the farthest in heap
 heapq.heapreplace(heap, (dist, x, y))
 
 return [(x, y) for (_, x, y) in heap]
```

**Complexity:** O(n log k) = ~66 million operations for n=10M, k=100
**Improvement:** ~3.5x faster than sort

### 2. Quickselect, O(n) average ⭐ Fastest

Partition like quicksort, but only recurse into the side containing k:

```python
import random

def k_closest_quickselect(points, k):
 def distance(point):
 return point[0]**2 + point[1]**2
 
 def partition(left, right, pivot_idx):
 pivot_dist = distance(points[pivot_idx])
 points[pivot_idx], points[right] = points[right], points[pivot_idx]
 store_idx = left
 
 for i in range(left, right):
 if distance(points[i]) < pivot_dist:
 points[store_idx], points[i] = points[i], points[store_idx]
 store_idx += 1
 
 points[right], points[store_idx] = points[store_idx], points[right]
 return store_idx
 
 left, right = 0, len(points) - 1
 while left < right:
 pivot_idx = random.randint(left, right)
 pivot_idx = partition(left, right, pivot_idx)
 
 if pivot_idx == k:
 break
 elif pivot_idx < k:
 left = pivot_idx + 1
 else:
 right = pivot_idx - 1
 
 return points[:k]
```

**Complexity:** O(n) average, O(n²) worst case
**Note:** Modifies input array; not stable

### 3. For Repeated Queries: KD-Tree, O(k log n) per query

If the points are static and you query often:

```python
from scipy.spatial import KDTree

# One-time preprocessing: O(n log n)
tree = KDTree(points)

# Each query: O(k log n)
distances, indices = tree.query([0, 0], k=100)
closest = [points[i] for i in indices]
```

### Comparison

| Algorithm | Time | Space | Notes |
|-----------|------|-------|-------|
| Sort | O(n log n) | O(n) | Simple, stable |
| Heap | O(n log k) | O(k) | Good when k << n |
| Quickselect | O(n) avg | O(1) | Fastest, modifies input |
| KD-Tree | O(n log n) build, O(k log n) query | O(n) | Best for many queries |

**For your case (10M points, k=100, changing data):**
Use Quickselect for best average performance, or Heap if you need stability.

## Caching Strategy Design

### 1. Cache Structure

**Key format:**
```
user:profile:{user_id}
```

**Value format:** JSON string of profile data
```json
{
 "id": "usr_123",
 "name": "Jane Doe",
 "email": "jane@example.com",
 "avatar_url": "...",
 "cached_at": 1705312800
}
```

**Why JSON:** Readable, debuggable, supported by all clients. Consider MessagePack if you need smaller payloads.

### 2. TTL and Eviction

```python
# Set with TTL
redis.setex(
 f"user:profile:{user_id}",
 60, # 60 second TTL (matches staleness tolerance)
 json.dumps(profile)
)
```

**Eviction policy:** `allkeys-lru`
- Given 90% of reads hit 10% of users, LRU naturally keeps hot data
- Cold profiles evict first, hot profiles stay cached

### 3. Invalidation Strategy: Write-Through + TTL

```python
def update_user_profile(user_id, data):
 # Update database
 db.users.update(user_id, data)
 
 # Immediately update cache
 cache_key = f"user:profile:{user_id}"
 redis.setex(cache_key, 60, json.dumps(data))
```

**Why write-through:**
- Low write frequency (50/min) means write cost is acceptable
- Guarantees cache is never stale for updated users
- TTL handles cases where invalidation fails

### 4. Read Pattern: Cache-Aside

```python
def get_user_profile(user_id):
 cache_key = f"user:profile:{user_id}"
 
 # Try cache first
 cached = redis.get(cache_key)
 if cached:
 return json.loads(cached)
 
 # Cache miss: fetch from database
 profile = db.users.find_one(user_id)
 if profile:
 redis.setex(cache_key, 60, json.dumps(profile))
 
 return profile
```

### 5. Cache Warming

For the hot 10% of users (known from analytics):

```python
def warm_cache():
 """Run on deploy or periodically."""
 hot_user_ids = analytics.get_top_users(limit=1000)
 
 for user_id in hot_user_ids:
 profile = db.users.find_one(user_id)
 redis.setex(f"user:profile:{user_id}", 60, json.dumps(profile))
```

### 6. Failure Handling

```python
def get_user_profile_resilient(user_id):
 cache_key = f"user:profile:{user_id}"
 
 try:
 cached = redis.get(cache_key)
 if cached:
 return json.loads(cached)
 except redis.RedisError:
 # Redis down: fall through to database
 logger.warning("Redis unavailable, falling back to DB")
 
 # Database is source of truth
 return db.users.find_one(user_id)
```

**Circuit breaker** for sustained Redis failures:
```python
cache_circuit = CircuitBreaker(failure_threshold=5, reset_timeout=30)

@cache_circuit
def get_from_cache(key):
 return redis.get(key)
```

### Memory Estimation

- Average profile: ~500 bytes
- Hot users (10%): ~100K users
- Memory needed: 100K × 500B = 50MB
- **Well within 1GB budget** (can cache more if needed)

### Expected Performance

| Scenario | Latency |
|----------|--------|
| Cache hit | <5ms |
| Cache miss (DB query) | ~50ms |
| Expected hit rate | 90%+ (hot users) |
| P95 latency | ~10ms |