performant-code

# Performant Code How to write code that won't timeout on large inputs. ## Think About Scale First Before writing code, ask: how big is the data? | Data size | Approach | |-----------|----------| | < 1 MB | Load into memory, any approach works | | 1-100 MB | Load into memory, but use efficient algorithms | | 100 MB - 1 GB | Stream/mmap, avoid loading entirely into memory | | > 1 GB | Streaming only, chunk-based processing | ## I/O Optimization ### Large files - **mmap** (C: `mmap()`, Python: `mmap.mmap()`) — map file into memory, OS handles paging - **Buffered binary reads** — `fread()` in C, `open(f, 'rb').read(chunk)` in Python - **NEVER** read a 500MB file line-by-line with `fgets()` when you need random access ### Writing output - Buffer writes — don't call `write()` for every byte - Use `fwrite()` or `sys.stdout.buffer.write()` for binary output - Flush only when needed ## Algorithm Complexity - **O(n)** beats **O(n log n)** beats **O(n²)** — always - Nested loops on large data = timeout. Restructure to single pass + hash map - Sorting is O(n log n) — only sort if you need to - Use hash maps/sets for lookup instead of linear search - Pre-compute what you can outside loops ## Language-Specific Tips ### C - Use `mmap()` for large file access - `-O2` or `-O3` for compiler optimizations - Avoid `malloc()`/`free()` in tight loops — pre-allocate - Use `memcpy()` instead of byte-by-byte copying - Integer arithmetic > floating point when possible ### Python - Use `numpy` for numerical work (100x faster than pure Python loops) - `collections.Counter`, `defaultdict` — avoid manual counting - List comprehensions > explicit loops - `struct.unpack()` for binary parsing - `subprocess.run()` > `os.system()` - For heavy computation: consider writing a small C program instead ### General - Profile before optimizing — find the actual bottleneck - If a program hangs, it's likely: infinite loop, deadlock, or I/O bound on huge data - If a program is slow, check: algorithm complexity, I/O pattern, memory allocation ## Constraints Awareness - If the task says "< 5000 bytes" — count your bytes, use `wc -c` - If there's a time limit — test with actual data, not toy inputs - If there's a memory limit — don't load everything into RAM - Always verify constraints BEFORE declaring done