Every essay — page 7
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
The index that replaces the text
Every index measured here before this one was weighed at zero. A suffix array is four times the size of what it indexes and cannot answer without it; a compressed self-index is a third of it and hands the text back on request. The unit is the bit, the primitive is a rank on a bit vector rather than a comparison of two characters, and the text is taken away before any query is allowed to run.
The search that spends a budget
A backward search narrows one interval per pattern character. Give it a budget of three errors and it narrows 39,943 of them instead, finds every occurrence the whole table finds, and reads not one character of the text — 177,046 index ranks against 60,000 table cells and zero characters examined.
The collection decides which index is small
Three compressed self-indexes over one text of five hundred characters measure 3,511, 7,285 and 10,974 bits. Repeat that text thirty-two times and the same three measure 34,615, 8,892 and 17,047 — the ordering has completely reversed, and nothing about any of the structures changed.
The candidates a filter cannot avoid
A phrase index answers a search by intersecting two ranges of boundaries, and it does the intersection by walking the smaller one. On a collection of thirty-two copies that is 4,355 phrase examinations to produce 32 occurrences — 136 examinations each, and rising.
What a ceiling costs in phrases
A cap of sixteen costs one phrase of a hundred and fifty-six and halves the worst chain. A cap of four costs six times the phrases. The curve between them is flat at one end and vertical at the other, and the elbow is where a structure should be built.
A list of documents is not a list of occurrences
A pattern occurring 790 times in eight documents has an answer of size eight. Reading every occurrence to find out costs 790 array reads; the question a collection has that a text does not is the one its index does not answer.
An interval that grows at both ends
A backward search step is two ranks. A bidirectional step is two ranks and the width of the interval for every symbol that sorts before the one being added — 16.5 ranks on four symbols and 138.6 on twenty-six, which is a cost no account of the structure mentions.
A block, a class and an offset
Replacing each block of a bit vector by how many ones it holds and which arrangement it is takes 7.6% off the grid. On a permutation with no structure at all it takes 2.6%, so five of the seven points are the data and two of them are the encoding.
Documents that are not the same length
A separator per document costs a whole bit per character — on a generated collection whose alphabet is 21 symbols, where adding a few crosses 32. Real prose has 87 symbols and sits 41 short of the next power of two, so the same separators cost 0.04%.
Two thousand documents of two hundred characters
Every collection this field has measured has been a dozen documents of ten thousand characters. A real collection is usually the other shape, and the other shape moves every term in a document index — one of them by a factor of seventy.
The half that is never asked where
A bidirectional index is two indexes and one interval. One of them is asked for ranks several hundred times a search and for a position never — and the parts that answer "where" are two of the five it is made of.
Every child at once
A bidirectional extension counts the occurrences of every symbol smaller than the one being added, and this collection did it with one rank per symbol — 139.7 operations an extension on a twenty-six-letter alphabet. One walk down the tree gives the same number.
The array the walk never reads
Document listing compares a chain entry against the start of a range. The comparison is true exactly when the document has not been reported yet — which the walk already knows, because it just wrote it down.
The index that does not notice
Three compressed indexes over the same characters. One is flat at six and a half bits a character however many copies the collection holds; the other two fall by factors of five and six. At one copy the two that fall are the largest of the three.
The tree answers the question
The distinct documents in a range of rows are the distinct symbols of the document array in that range. A wavelet tree enumerates those in one descent, so the range minimum, the chain, the bitmap and the recursion all go at once.
Asking about symbols that are not there
A search extends an interval by every character of the alphabet, and on a deep branch almost all of them produce an empty interval. That is a full rank walk whose entire result is the discovery that nothing was there.
What the locating apparatus becomes
The two parts that answer "where" are half an index at a dense sampling and a fifth at a sparse one, and the fifth does not fall further. Represent the marks properly and it keeps falling, to under four per cent.
Three savings on one structure
A factor of eleven on an extension, a factor of seven on a branching search, and a sixth of the bits. Applied to one bidirectional index they do not give a factor of seventy-seven, and the reason is that two of the three are the same saving.
The same occurrences, less bookkeeping
Two traversals examine identically many phrases and report identically many occurrences. What differs is that one holds every occurrence found so far in a set and the other holds an ordered list and a cursor.
The collections the saving was quoted for
A document array compressed to the entropy of its own symbols saves exactly what the collection's length distribution allows, and the measurements that showed it used four constructed collections. The estimate they ended on — a directory of source files is roughly log-normal, so its array falls about a bit short of the plain one, around 17% — can be checked on a real directory. A project's 222 source files fall short by 0.66 bits and save 10.5%, a fifth of which is only the rounding of ⌈log₂ d⌉. Across six real collections the skew of the lengths is worth between nothing and 0.76 bits, and the log-normal formula overstates it wherever short documents are common.
The shape arrived early and the bytes late
A document array coded by its documents' lengths was predicted to survive a growing collection: fitted once at a quarter of a project's files, it would lose under a tenth of a bit a symbol by the end, because the spread of the sizes is set early. The spread was set early — 0.88 at 56 files, 0.90 at 222. The fitted code loses 0.50 to 2.08 bits all the same, because the files added after the fit hold 43% of the final bytes and every one of their symbols is named through an escape. Rebuilding only the escape's subtree brings it to 0.18.
A count that names every point
A grid that can report the points in a rectangle can be no smaller than log₂(z!) bits, because reporting them recovers the permutation. A grid that only counts them was left open as possibly smaller. Exactly, it cannot be: counts alone decode every point, and on the phrase index's 3,612 points 42,860 count questions recover the whole permutation, so an exact counter pays the same floor of 37,485 bits. Approximately it can — and the rectangles a phrase index asks are where an approximate count is worst. They hold 2.6 points on average and a third of them hold exactly one; the wavelet grid cut to eight of its twelve levels, 8% under the floor, counts 46% of them right.
One doubling late
A document array coded by its documents' lengths and refitted each time a growing directory's files double needs an escape for the files added in between, and the escape's right weight is the share of the characters still to come. Weighting it by the share that arrived since the previous refit was predicted to cut the mean loss below a quarter of a bit a symbol. It cuts nothing: 0.518 bits a symbol, against 0.389 for an escape that always takes half the coding space. The growth seen is the growth to come one doubling late — 71%, 50% and 27% where the doublings that followed brought 50%, 27% and 8% — because this directory's growth slowed at every doubling, and before the first refit there is no growth to read at all. A Huffman code also rounds every weight to a whole number of bits, so being right within a factor of two buys nothing. Started from half, the growth seen averages 0.356, the best a store can know, and the weight nobody can know reaches 0.183.
Refitting when the escape is wrong
A growing directory's document array, coded by a Huffman code over its files' lengths and refitted each time the files double, loses at best 0.356 bits a symbol for 5.65 final arrays of rewriting, and even an escape weighted by the growth still to come loses 0.183. A clock read off the structure — refit when the share of characters named through the escape passes twice the share its code word stands for — was predicted to refit about six times and halve the loss. It refits 25 times, eleven in the first twelve versions, and rewrites 10.6 arrays for a loss of 0.042. Held back until the characters have grown by a quarter since the last refit, it refits 11 times and loses 0.098 bits a symbol for 4.52 arrays: under every doubling schedule on both counts, including the one that reads the future. It sees anything only if the escape starts small: weighted as half the coding space, the escape's code word is one bit, nothing behind it can ever pass twice a half, and the clock never fires.
A test that is the top of the search
A phrase index asked whether a pattern occurs only needs to know, split by split, whether a rectangle of its grid holds a point. Stopping the grid's descent at six of its twelve levels was predicted to turn away nine in ten of the splits that come to nothing, for half the grid's bits. It turns away three in four, and the ones it lets through sit a median of five rows from a point. The test is never wrong, but the existence query had little left for it to save: patterns that occur are settled by their first split 94% of the time, and most patterns that do not occur never reach the grid.
A price that cannot see the array
A growing directory's document array, refitted when the share of characters behind its escape passes twice what the escape's code word assumes and held until the characters have grown by a quarter, loses 0.098 bits a symbol for 4.52 final arrays of reading. A hold set by price instead — refit when the bits wasted since the last refit reach a constant times the characters a refit reads — was predicted to do at least as well, refitting early where refits are cheap. It does worse: about 0.119 at the same reading. The array's size multiplies both sides of the rule, so the price never sees it; what the rule watches is the loss summed over versions, and that refits late in the small, fast-growing early history where the fixed hold refitted often. The price also counts only the refits' reading, while waiting is paid in rebuilds of the escape, so the total reading stops falling at about 4.3 arrays however high the price goes.
The quarter was a lucky number
A growing directory's document array was refitted best by a clock read off its escape and held until the characters had grown by a quarter: 0.098 bits a symbol for 4.52 final arrays read. A price that weighed the refit against the loss alone did worse, because the array's size cancelled and the price left out the reading that waiting costs. Priced with that reading — refit when the escape rebuilds since the last refit, plus the waste a refit would remove at an exchange rate, pass the characters a refit reads — the rule beats the hold wherever both read more than about five arrays: 0.080 for 5.04 against the hold's best 0.088, 0.052 for 6.38 against 0.066. It loses only at the quarter's own point, and the quarter turns out to be a lucky setting: held to 1.2 or to 1.33 the clock is worse on both counts, because two bursts of growth arrive two versions at a time and only a quarter refits after both halves.
What the machine does
The operation count is not the running time. Locality, cache lines and branch behaviour decide the constant, and they rank algorithms differently from the textbook count.
The count is not the time
An operation count is exact, machine-independent, and not a running time. The gap between them is mostly memory, and it is large enough to reorder the rankings. A second count is kept alongside it — modelled cache misses from the same runs — and the two are required to disagree, because if they agreed the second one would carry no information.
The cliff where the data stops fitting
Below the cache's capacity, almost every access hits. A factor of eight above it, almost every access misses. The transition is not gradual and it is not a property of any algorithm — it is a property of how much data there is, and an algorithm's complexity class says nothing about which side of it a program is working on.
Where an algorithm looks
Plotted as index against time, every array access an algorithm makes becomes a picture that no count contains. Merge sort's is a set of sweeps. Heapsort's is a spray. Quicksort's is a narrowing triangle. These shapes decide how fast the algorithms run and they are entirely absent from the analysis that says all three are Θ(n log n).
Where insertion sort actually wins
Every production sorting routine falls back to insertion sort on small subarrays, and the usual explanation is that below some threshold it does fewer comparisons. Measured, it does not — not at sixteen elements, not at eight, not at four. The crossover is real and it is entirely in memory traffic, which is a distinction the usual telling loses.