Eighteen Reads Instead of a Quarter of a Million
Last timeThe Cost of Reading Everything
Sorting a file turns finding a row from a quarter of a million reads into eighteen. Then somebody inserts a row, and the whole of the rest of the course follows.
The previous lesson ended with a question: what is the cheapest change to the
layout of a table that makes finding a row cost less than reading all of it?
The answer is to put the rows in order, and it is worth seeing exactly how much
that buys before seeing what it costs.
Halving the search
Take the quarter of a million pages from the first lesson and suppose they are
in order by the column being searched. Read the middle page. Either the row is
on it, or the row is in the half above, or the row is in the half below. In one
read, half of the file has been eliminated.
Repeat. Each read halves what remains, so the question is how many times a
quarter of a million can be halved before one page is left.
- number of page reads a search costs
- number of pages in the file
| step | read | pages still possible | page examined | outcome | what happened |
|---|---|---|---|---|---|
| 1 | 1 | 244000 | 122000 | target is above | One read has eliminated 122,000 pages. Nothing clever happened: the file was in order, so a single comparison settled an entire half. |
| 2 | 5 | 15250 | 129625 | target is below | After five reads the field is down to fifteen thousand pages. The halving is relentless and it does not care how large the file was to begin with. |
| 3 | 12 | 119 | 122440 | target is above | Twelve reads in, a hundred and nineteen pages remain out of a quarter of a million. |
| 4 | 18 | 1 | 122451 | row found | Eighteen reads. Doubling the size of the table would make it nineteen, which is the property that makes this worth building a course around. |
Eighteen reads is still eighteen scattered reads, each with its own latency, so
it is not eighteen times nothing. It is around two milliseconds against a
couple of seconds, which is the comparison that matters.
The lesson stops here
4 more paragraphs to go
You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.
The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.
See the planThe contentsThis is the reading half
Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.
The contents