Lesson 16 of 16

Working with Large Data

A correct algorithm with a reasonable operation count can still be slow. Consider whether data fits in memory, which work can happen simultaneously, and how much communication costs.

Split independent work

A large sum can be computed by adding separate segments and combining their totals. Work that depends on earlier results cannot be split arbitrarily.

Suppose 80% is parallelizable and 20% remains sequential. Even with perfect balance and no communication cost, four processors take 0.2 + 0.8/4 = 0.4 of the original time: a 2.5-fold speedup, not fourfold. This is the limit described by Amdahl’s law.

Real systems also pay for splitting work, moving data, and synchronization. Dividing small tasks too finely can make execution slower.

Sort data larger than memory

A large file may not fit in a single in-memory list. External sorting can:

1. Read a chunk that fits in memory.
2. Sort each chunk and save it.
3. Merge the sorted chunks while reading only small portions at a time.

This adapts merging to storage constraints. Disk reads and writes matter alongside comparison counts. Structures such as B-trees also group keys into nodes to reduce block accesses.

Final exercise: Choose a method

For a new problem, write down:

• Inputs, outputs, exceptional cases, and boundaries.
• A straightforward correct solution and its cost.
• Whether that cost is practical at the input size.
• Repeated work, unnecessary candidates, and reusable ordering or indexes.
• Why the method works, and counterexamples that break its assumptions.

Check your understanding

You need only the maximum value in a large unsorted file. Must you sort it or load everything into memory?