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