Week 89 of 125
TAOCP 5.4.8 and 5.4.9
Sign up or sign in to tick these off and give this week a due date.
-
What you can do with only two tapes, and why it is so much harder than with three or more.
Time About 2 hours this week
Why it matters
Mostly of theoretical and historical interest. 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
- 5.4.1 Multiway Merging
How to approach it
Skim.
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.
-
External sorting on random-access devices like disks: how seek time, rotational delay and block sizes change the best strategy compared with tapes.
Time About 5 hours this week
Why it matters
Much more relevant than the tape sections: disk-based thinking (minimize seeks, read large sequential blocks) still matters for databases, even on SSDs.
Before you start
- 5.4.1 Multiway Merging
- 5.4.6 Practical Considerations
How to approach it
Read with modern storage in mind. Ask at each point: what changes for an SSD? What stays the same?
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.
Traps
- Taking 1970s timing numbers literally.