Week 88 of 125
TAOCP 5.4.6 and 5.4.7
Sign up or sign in to tick these off and give this week a due date.
-
Real-world engineering of tape sorts: buffering, overlapping I/O with computation, block sizes and timing estimates.
Time About 4 hours this week
Why it matters
The buffering and overlap ideas transfer directly to disk and network I/O. Honest note: the tape-merging sections describe hardware nobody uses anymore. Knuth himself says much of 5.4 is historical. The ideas (run generation, merge patterns, minimizing passes over slow storage) still apply to external sorting on disks and SSDs, database sort operators and big-data shuffles, so read for those ideas and skim the tape mechanics.
Before you start
- 1.4.4 Input and Output
- 5.4.1 Multiway Merging
How to approach it
Read the buffering and overlap parts carefully, since they map to modern I/O. Skim device timing details.
Exercises
This is a light section. Skim the exercises, do the ones rated 10 or under in your head, and spend the spare time catching up on earlier exercises you skipped.
-
Doing radix sort on data that lives on external storage, distributing into files by digit.
Time About 3 hours this week
Why it matters
Distribution-based external sorts are how many big-data systems partition data (think MapReduce shuffles).
Before you start
- 5.2.5 Sorting by Distribution
How to approach it
Skim and connect it to the shuffle phase of MapReduce or Spark.
Exercises
This is a light section. Skim the exercises, do the ones rated 10 or under in your head, and spend the spare time catching up on earlier exercises you skipped.