Every essay — page 5
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 floors
Some work cannot be avoided. The information-theoretic bound on comparison sorting is computable exactly, and the gap between it and each algorithm is a number.
Work that falls as the answer grows
Output-sensitive usually means the cost rises with the answer instead of with the input. A descent over a document array costs five operations per document at an answer of seven and two at an answer of thirty-two, because the paths to many leaves share their tops.
Proportional to the answer, not the alphabet
At a fixed alphabet of thirty-two, a loop costs three hundred and twenty ranks whether one symbol is present or all of them. The descent costs ten and sixty-two. The experiment has to move the answer without moving the alphabet, and the obvious sweep moves both.
From the right, two of sixteen
Run the same sweep in the opposite direction and every occurrence it produces lands behind its own cursor. It reports two of sixteen, every one of them genuinely there, and nothing about the answer says fourteen are missing.
Every pair must be asked
Ask whether a six-vertex graph is connected, one pair of vertices at a time, and the best possible algorithm needs all fifteen questions on its worst graph. The claim that this holds for every monotone property of graphs is a conjecture fifty years old. At four vertices it can be settled completely: all 2,046 properties that do not depend on vertex names need every pair. Name one vertex, and the count drops from ten to four.
The floor a merge cannot reach
Merging two sorted lists of five keys each has 252 possible outcomes, so counting says eight comparisons might do. Solving the game says nine are needed, and on equal lengths the shortfall keeps growing, as half the logarithm of the length. Averaged over random inputs, though, the same count is missed by a tenth of a comparison. The counting floor is nearly exact on average and wrong in the worst case.
The order inside a tie
Sort the rotations of a text by their first four characters rather than by everything that follows, and the output clusters slightly better than the full Burrows–Wheeler transform: 1.780 bits a symbol against 1.802, from 63% of the character reads. It also costs nothing to undo. The prediction that a shorter context leaves ties for the inverse to pay for was wrong. The cost to undo comes from how a tie is ordered, not from how long the context is, and at k = 0 the wrong tie rule is exactly the sort.
A result the size of its own noise
Sorting rotations by their first four characters beat the full Burrows–Wheeler transform by 0.022 bits a symbol. On sixteen streams of the same source the mean difference is 0.004 with a standard deviation of 0.011, and the short context is ahead on ten of them. The 1.2% was one draw. What survives is sharper than the result it replaces: from four characters upwards, every run break either rule makes is at a word boundary, and nothing above four characters decides anything at all.
Where a context stops naming the letter before
A sort of rotations by their first k characters matters only where those k characters fail to decide the character before them, and that share of positions can be counted in one pass with no sorting. It was proposed as a replacement for sweeping k. Counted as proposed, it misses by a factor of four: on a stream of independent words 37% of positions are still ambiguous at four characters, where the sweep has already gone flat. Counted only where the context sits inside a word that goes on past it — the one place more context can still help — it lands within a step of the sweep on four sources of five.
The merge that can say equal
When two sorted lists draw their keys from a few values, equal keys can go on either side of each other, so far fewer answers are needed and the counting floor falls. Merging four keys into four over four values needs only 27 answers, not 70, and the floor falls from seven comparisons to five. A merge whose comparisons answer only 'at most' still needs seven on its worst input, exactly as many as distinct keys, because it can never learn that two keys are equal. A merge whose comparisons can answer 'equal' needs five and meets the floor. Solved exactly over every input, the third answer is the whole difference, and on average it is worth more than an optimal strategy.
The repeats a context cannot see past
Sorting rotations by their first k characters stops losing to the full Burrows–Wheeler transform at four or five characters on four sources and at about ten on a corpus of technical writing. The count proposed to explain the exception — how much a context spanning a word boundary says about the letter before it — cannot be read off its own estimate, which falls on words drawn independently where there is nothing to find. Measured against each text's own shuffled twin, the information the word order carries is real, but it has all arrived by four or five characters, and at eight, twelve and sixteen the two corpora are indistinguishable. What does separate them is repetition. Stream by stream, the share of positions inside a repeated sixteen-character string predicts the technical corpus's loss with a correlation of 0.98.
The deepening the sort was already doing
A sort of rotations by their first k characters loses to the full Burrows–Wheeler transform where a longer string repeats, and a sort deepened only inside the ranges where contexts repeat was proposed to recover those bits at a fraction of the transform's reading. It recovers the bits: on sixteen streams every one lands within 0.006 bits a symbol of the transform, and the most repetitive goes from 0.129 bits worse to 0.001. It reads more characters than the transform, not fewer — 74.5 a symbol against 69.4 on technical writing — because a comparison sort of rotations already reads deep only where rotations agree. The transform was the adaptive sort. The characters a sort by k characters saves are exactly the ones the repeats needed.
The order the column cannot see
A sort of rotations by their first four characters leaves ranges that agree on those four, and the full Burrows–Wheeler transform reads deeper to order them. Given a budget of characters below the transform's, spending it on the ranges whose rotations are preceded by the most different characters was predicted to reach within a hundredth of a bit at two thirds of the transform's reading — and spending it on the longest agreements, as the transform does, to waste it. The price was impossible: the four-character sort alone reads 76% of what the transform reads. The ranking was right on average, and right for a reason that makes the budget unnecessary: a range whose rotations are all preceded by one character writes the same run into the output in any order. Skipping every such range writes the transform's column exactly, on all sixteen streams, and reads 11% less on technical writing — up to 19% on the stream with the longest repeats.
The runs a short list cannot have
A merge whose comparator can say 'equal' meets the counting floor on lists of repeated values, but it takes the gain only when one list's head happens to meet an equal head in the other. Comparing keys inside a list would find runs of equal keys on purpose, and was predicted to leave the worst case alone and help a great deal on average when the values are few. Solved exactly at four keys a list, it leaves the worst case alone and helps by under a hundredth of a comparison: a list of four has no run worth finding, and an equal answer already places two keys at once. On long lists the same idea, galloping over each run before comparing across again, does pay — a twenty-sixth of the textbook merge's comparisons with one value at 1,024 keys a list — and at every length it stops paying at the same place: when a value's run averages fewer than about thirty-two keys a list.
A merge that decides per run whether to gallop
Merging two sorted lists of repeated values, a merge that gallops along every equal run beats the textbook merge while the runs average more than about thirty keys a list and loses below, a rule about the whole input. A merge that learns the runs as it goes was predicted to match the better of the two on uniform values and beat both on skewed ones. The proposal's rule — gallop when the last few runs averaged long — cannot learn a run that has not ended: at one, two or four values it walks every key. Timsort's own rule, applied to equal answers — walk until a bar of consecutive equal answers, then gallop, the bar moving by one as galloping pays or fails — does what was predicted. On uniform values it stays within a hundredth of a comparison a key of the better merge; under Zipf 1, at 4,096 keys a list and 1,024 values, it makes 0.447 comparisons a key against 0.595 walking and 0.594 galloping, a quarter under both.
The question asked at every split
A range of rotations preceded throughout by one character writes the same run into the Burrows–Wheeler column in any order, and a sort that asked that once, of the ranges four characters leave, read 11% less than the transform. Asked at every split of a sort that partitions on one character at a time, it was predicted to read a fifth less on technical writing and an eighth less on the essays. It reads four fifths less — and nearly all of that is the change of sort, which the prediction expected to cost reading rather than save it. The question's own share, measured against the same sort without it, is 29% on technical writing and 14% on the essays.
A sort that infers the order
A radix quicksort that stops at every group of rotations preceded by one character reads about fourteen characters of a text for every symbol of its Burrows–Wheeler transform. Induced sorting, which reads the order of a third of the suffixes and derives the rest, was predicted to read three. It reads 6.1 on all sixteen streams, within 0.14 of each other, and the same at every length from a thousand characters to thirty-two thousand. The question the quicksort asks saves it nothing, as predicted, for a reason the prediction did not give: its last two passes read the transform's column itself, one character for every rotation, in order to sort.
A bar that wins rarely meet
A merge of two sorted lists of repeated values saves most of a textbook merge's comparisons by galloping along a run of equal answers once a bar of them have come in a row, with the bar lowered after a gallop that pays and raised after one that does not. Timsort keeps the same kind of bar for the other kind of stretch, one list winning repeatedly, and a merge of repeated values meets both. One count and one bar for either kind was predicted to save a further tenth under Zipf 1 and change nothing on uniform values. It saves at most 1.0% under Zipf 1, costs up to 1.3% on uniform values, and two separate bars do no better. In two lists drawn from the same distribution a stretch of wins long enough to gallop over is rare: under Zipf 1 at most 18% of the shared bar's gallops are over wins, and where wins dominate the gallops, at a thousand uniform values, the runs of either kind are too short for any gallop to pay.
Two parameters
A graph's cost is in V and E, so no bound here is a comparison until the density is stated. The same two algorithms change places when only the shape of the graph changes.
Counting on a graph
An instrumented array counts comparisons, swaps, reads and writes, and none of those is what a graph algorithm spends its time on. Three new primitives are needed — an adjacency scanned, a vertex first reached, an edge relaxed — and once they exist, breadth-first and depth-first search turn out to be the same algorithm by every count kept on arrays.
Two parameters, one bound, no order
With one size parameter the candidate classes are ordered — n beats n log n beats n², always, and comparing two bounds is reading them. With two, E log V and V² have no order at all, and which one is smaller is a property of the graph. Sweeping V at fixed degree and at fixed density are different experiments, and the same algorithm fits different classes in the two.
The queue decides the class, and the pseudocode does not name it
Dijkstra's algorithm is eleven lines of pseudocode with a priority queue in the middle of them. Which queue is not stated, and it is the difference between 56,973 units of work and 2,118,656 on the same graph. Two of the three queues here also fail to fit the class they are famous for, in a regime each.
The constant that is practically constant
Everywhere else on this site the class is honest and the constant is hiding something. Union–find is the exact inverse — its bound is formally not constant, its growth term reaches four at n = 2,048 and stays there for every input anyone will ever run, and the measured path length is flat at 0.92 pointer hops across a two-hundred-fold range of n.
The precondition that removes the queue
Dijkstra maintains a priority queue to discover which vertex is safe to finalise next, and on a directed acyclic graph 65% of its counted work goes into that queue. The order it is discovering is already known. Relaxing in topological order makes exactly one relaxation per arc — 1,536 arcs, 1,536 relaxations — with no queue at all, and negative weights are fine.
Two passes or one, and what the second one costs
Kosaraju's algorithm and Tarjan's find the same strongly connected components of the same graph, in the same class, and one of them examines three times as many arcs as the other. The extra pass everybody counts is not where the difference is — building the reversed graph is, and no statement of "two depth-first passes" mentions it.
The precondition on a function the caller writes
Dijkstra expands 1,582 cells to find a path of 98 across a fifty-square grid. The same loop, with the straight-line distance to the goal added to each key, expands 405 and finds the same 98. The estimate has to be a function the caller supplies, and the guarantee holds only while that function never overestimates — a condition on somebody else's code, not on the graph.
A list and a block of memory
The same traversal, over the same graph, examining the same edges in the same order, laid out two ways. Twelve thousand two hundred and eighty-eight edge slots either way; 11,812 modelled cache misses against 3,258. This is the site's largest gap between two counts of one run, and it exists because one of the layouts is a pointer chase and the other is a sweep.
Two parameters are not enough either
Two graphs on 1,024 vertices with 3,072 edges each — identical in both numbers every bound in this field is written in. Enumerating every pair of neighbours of every vertex costs 18,480 examinations on one and 42,076 on the other. The quantity that separates them is a third parameter, it is computable in linear time, and it appears in no statement of the problem.
The bound with a precondition
Bellman–Ford is O(V·E), and on a graph of 2,048 vertices it stops after seven passes of the 2,047 the bound allows — a factor of 289 between the bound and the run. Dijkstra is faster and returns a wrong answer on four vertices if one arc is negative. Both facts are about the same clause: the qualifier at the end of the sentence.
A graph is as hard as its largest cycle
Negative arcs rule out Dijkstra's algorithm and leave Bellman–Ford, which on a thousand vertices does three million units of work. Stopping it when a pass changes nothing brings that to 78,496. Finding the strongly connected components first and running it inside each one brings it to 38,549 — and to a quarter of the early-exit cost when the components are small, because every cycle lives inside one.
An estimate borrowed from an easier problem
On a grid where every step costs one, the straight-line distance to the goal cuts a search from 543 cells to 325. On terrain where steps cost between one and nine it cuts 1,572 to 1,550, because it still believes every step costs one. Four exact distance tables, computed once, cut the same search to 252 — and cost 6,328 reads to build, so they pay for themselves on the fifth query.
An estimate is a reweighting
Reprice every arc by the estimate's drop across it and run plain Dijkstra, and it expands the same 325 cells A* does, in the same order, because the two are one algorithm. Replace the estimate with one that is still never too high but drops too fast between neighbours, and 215 arcs go below zero — and on a stated grid the search that refuses to reopen a finished cell returns a path of 178 where the shortest is 169.