Every essay — page 14
What a bound is Counting The floors What the machine does Structures Two parameters The other axis When the algorithm flips a coin What the libraries do When it does not fit One pass, and no room The data that is not a number When the algorithm is a table The index that replaces the text What is taught wrongly Ladders Objects Search
What is taught wrongly
The comparisons that are made without units, the averages quoted without their distributions, and the bounds treated as predictions of speed.
Where the sparse representation loses
At every row marked, Elias–Fano costs twice the plain vector. The crossing is at one row in four, which is a sampling rate a real index uses — so the choice between the two is a choice, not an improvement.
A price with no structure under it
A class in this collection has charged Elias–Fano's price for several strands and stores an array of positions searched by binary search. The accounting is right about space to a bit per thousand and wrong about one operation by a factor of eight.
Two factors that do not multiply
Eleven times and seventy-eight times against the same baseline, so an index with both should be eight hundred and sixty. It is seventy-eight, and the shortfall is eleven — the first factor, exactly, because the second operation already contains it.
A constant factor, not a term
The substitution was expected to remove a quantity proportional to the answer. Both traversals hold a quantity proportional to the answer, and what it removes is a factor of 1.6 that shrinks as the collection grows.
A cache below the reachable set
A lazy machine with a cache of two hundred and fifty-six states costs fifty-one operations a character and a plain non-deterministic simulation costs fifty-three. At five hundred and twelve it costs eleven. The line is flat across two orders of magnitude and then falls off a cliff.
The folklore is about a matcher
Four million steps against three hundred and twenty-nine, on a twenty-character expression matched against twenty characters. One of the two machines doubles with every character of the input and the other does not, and only one of them is what a regular expression is.