Algorithms & Data Structures
the bound is a claim, and it is checkable
Theme

The thread: The order is the algorithm

The recurrence is the easy half. Which cells are evaluated, in what order, and which are kept afterwards is where correctness and cost both live — and a table that cannot tell an unfilled cell from a cell holding zero reports neither.
—bcab—abca6388328188632571322513518753111111one unit = one invocation of the recurrence481 calls, 25 distinct subproblems When the algorithm is a table

The cost is the number of subproblems

The edit-distance recurrence, written down literally, makes 29,737 calls on a six-letter word and a seven-letter word. Written down with a table beside it, it makes 56. Nothing about the arithmetic changed, and the class did.

 —sitting—kitten012345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455one unit = one subproblem given a value56 cells, filled in row order When the algorithm is a table

The same table, filled two ways

Top-down and bottom-up compute identical cells and return identical answers. One of them asks the table half a million questions and recurses four hundred frames deep; the other asks none and recurses none — and on a knapsack it fills twenty-two times as many cells as anything can reach.

 —abrocadabro—abracadabra012101221012210122112222123321233212332123321233212322one unit = one subproblem given a value54 of 144 cells, 90 skipped When the algorithm is a table

A band as wide as the answer

If two strings are close, the optimal route stays near the diagonal and nine cells in ten cannot be on it. A band of three finds the right answer on a pair 300 characters long — and a band of thirty-two is needed before anything can prove it.

 keytruthfoldedtreereversed16,3626,8666,8696,86923,0743,5783,5813,58131,9632,4672,4702,47041,3731,9021,9071,95451,0981,6021,6051,60569351,5121,4711,46377691,2801,2851,30686561,1601,1631,16395661,1001,1011,095105101,0511,0361,029shaded rows are keys whose count depends on the order aloneSpace-Saving, k = 32 · 8 shards · hashed37 keys move with the order Structures

The order nobody fixed

The same eight summaries, combined pairwise in a tree or folded in one at a time, produce tables that differ on forty keys — the largest by 964 arrivals. Nothing in a deployment fixes which shape is used, and both answers are inside the guarantee.

 10010³10³10⁴10⁵10⁶10⁷Vcounted workTopological order, one passDijkstra, binary heapBellman–Ford, all passesV from 64 to 2048, directed, acyclicwork = scans + visits + relaxations + queue comparisons Two parameters

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.

 —agcacacggatcag—ccagggagta09101112131415161718192021229110101212141416171819192122101021011121314151718191920221110113101212141516171920192112121012411131314151718202119131312111351214131416181921211414131312146131413151719202115141514131314714151316181921161614161514141571416141719191717171517161515168151615182018171818151816161617816171519one unit = one subproblem given a value495 cells across three tables, 980 transitions When the algorithm is a table

A cell that has to know where it is

A gap of four characters is usually one event, not four. No recurrence over a single table can charge it that way, because the price of a gap character depends on how the cell above it was reached and a cell holding one number has thrown that away. The repair is three tables, and it costs exactly three times the cells.

 —execution—intention87777776569888888765one unit = one subproblem given a value100 cells computed, 20 held at once The other axis

The table nobody has to keep

A million-cell table, computed cell for cell in the same order, holding two thousand cells at its peak instead of a million. The saving is exactly (n+1)/2, it costs nothing on any operation counter, and what it buys is paid for with the one thing the table was for.

 —execution—intention0136101521283645247111622293746555812172330384756649131824313948576572141925324049586673792026334150596774808527344251606875818690354352616976828791944453627077838892959754637178848993969899one unit = one subproblem given a value100 cells, filled in diagonal order When the algorithm is a table

The order that has a depth

One hundred cells, filled in three orders, producing one table. Row order takes ninety-one steps and anti-diagonal order takes nineteen. Nineteen is not a property of the order — it is the longest chain of cells in the recurrence itself, no schedule can get under it, and every count taken until now was a total that could not see it.

 —execution—intention0123456789112345667822234567773333455678434345667854444567776555555678766666656787777776569888888765one unit = one subproblem given a value110 cells for one divide step, 30 held The other axis

The alignment that fits in one line

Compute the table twice and hold three rows of it. The factor of two is a geometric series and is predicted exactly; measured, it comes down from 2.269 to 2.052 as the strings grow, and the peak is 3(m+1) cells on the nose.

 24816326410⁵10⁶components the graph is built fromcounted workcomponents firstBellman–Ford, early exitBellman–Ford, every passV = 1,024, negative arcs between componentsvertices relabelled at random Two parameters

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.

 —ttacgggacgtaccagt—acgt000000000000000000111011110111011011222101221012101112333210122101211212433321123210122221one unit = one subproblem given a value90 cells, top row zero, answer read from the last row The data that is not a number

The row that starts at zero

The same 1,413 cells, filled by the same recurrence in the same order, answer 148 and 0. One line of initialisation decides which question the table was asked, and only one of the two answers is about whether the pattern is there.

 0231436845165232shards mergedkeys whose count movedthree orders:folded in one at a timecombined pairwise, in a treefolded in, last shard firstMisra-Gries, k = 32 · hashedworst gap 298 arrivals What a bound is

What a fold charges per level

Thirty-two counter tables folded in a chain come out wrong by 323 where the same thirty-two combined pairwise are wrong by 148, and the quantile summaries prefer the chain by exactly as much in the other direction. What is being charged in each case is the depth of the fold, and the two families are charged on opposite ones.

 01234567801234567891724303539424410182531364043111926323741122027333813212834142229152316one unit = one subproblem given a valueeach number is a storage offset, of 45 slots When the algorithm is a table

A triangle stored in a square

An interval table has a cell for every range of keys and nothing below its diagonal, and it can be stored as a square array, as packed rows, or as packed diagonals — the last matching the order it is filled in. On sixty-four keys, with every read replayed through a small cache, the square misses 39.7% of its reads, packed rows 38.8%, and packed diagonals 78.4%. Storing a table in the order it is written is storing it in the order it is not read.

 cache misses per split point consideredsquare array, by length1.1063,128,465 missestwo copies, by rows0.212598,455 missessquare array, split scans0.095268,386 missesfully associative · 32 lines × 8 elements · LRU256 keys, 32,896 cells When the algorithm is a table

The split scan cut into blocks

Every way of filling an interval table one cell at a time stops at about one cache miss per split point considered once the table outgrows the cache — 1.01 at 128 keys, whether the cells go by length, by rows, or in a recursive tiling. Cut each cell's scan into blocks instead, and apply a block of split points to a block of cells whose inputs are all in hand, recursively at every scale, and the same 357,760 split points cost 0.094 misses each. The fill is told nothing about the cache, blocks of one and of four do equally well, and it needs no extra memory, where storing the table twice gets to 0.151 by doubling it.

 1632649612810³10⁴10⁵table sizesplit points appliedevery splitbounded per blockbounded per cell, by lengthweights satisfying the quadrangle inequalityall three compute the same table When the algorithm is a table

The bound a block can and cannot have

Knuth's condition turns an interval table's cubic fill into a quadratic one by bounding each cell's best split between its two neighbours'. A blocked fill cannot use it a cell at a time, and the two cells that bound a block lie outside the block — one to its left, one below it. The schedule has finished both for ten per cent of the blocks, the bound then removes eleven per cent of the splits, and it removes half a per cent of the cache misses, because the splits it skips are the ones already in the cache.

 occurrences reportedin text order16from the right2 — 14 lostevery one it reports is real, so the answer is short rather than wrong1 of them were found by the boundary search and never propagated16 copies · 6-character pattern87.5% lost The floors

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.

 right to left8302.74xleft to right8772.89xone per piece4471.48xthe scheme3031.00xinterval extensionsall four found the same 6 positions15 characters · k = 22.74x apart The data that is not a number

The search that starts in the middle

The same pattern, the same six occurrences, the same index — and 830 interval extensions, or 303, according to which end the search begins at. A pattern cut into three pieces has an error-free one, and only a search with two ends can start there.

 folded in one at a time2,616 tuples17 ranks outcombined pairwise, in a tree3,637 tuples17 ranks outfolded in, last shard first2,615 tuples17 ranks outtuples kept, and worst rank error against a promise of 10032 shards · ε = 0.01 · high-biased · round1.39× the space, 0 ranks of answer Structures

The shape that moves the bill

Thirty-two quantile summaries combined pairwise keep 3,637 tuples and the same thirty-two folded in one at a time keep 2,616, for answers that differ by nothing at all. The counter tables measured for the same thing do the opposite — their order moves the answer and leaves the space alone.

 1,00010⁴10⁵10⁶charactersoperationscharacter comparisonstransitions and linksrepetitive · 8 copies346 phrases at 8,192 The data that is not a number

The parse in one pass of the text

The same parse, phrase for phrase, from 1,324,336 character comparisons or from 25,420 transitions and suffix-link steps. One of those numbers grows with the text and the other grows with its square, and the difference is why every measurement about a depth cap here was taken on a few thousand characters.

 50%60%70%80%90%100%0%1%2%5%10%25%50%share of keys arriving latemean leaf filleven splitsrightmost-split rulesibling first, two into threeln 2131,072 keys, leaves of 64late keys arrive at a random later point When it does not fit

The sibling a full leaf asks first

The rule databases use to fix ascending inserts fills their leaves completely and collapses to 53.4% when one key in a hundred arrives late. A leaf that offers a key to a sibling before it splits, and splits two full leaves into three when neither will take one, holds 84.2% on the same stream — and is better with a trickle of late keys than without one, because a perfectly ascending stream has no sibling with room.

 weighted path lengthΣ wᵢdᵢ — what Huffman minimisescuts takenΣ over the mergesdamageworst error leftchaintreesmallest-firstlargest-first543k147k123k738k309254259388323148183403Misra-Gries · 32 shards · hashedleast path smallest · least damage balanced Structures

The fold that minimises the wrong thing

A fold charges per level and a survivor pays the cuts on its path, so the bill looks like a weighted external path length — and Huffman's construction minimises that quantity by proof. Built and measured on thirty-two uneven shards it does minimise it, 181,407 against a balanced tree's 200,000, and leaves more damage than the tree does.

 counter tablesworst error, ratio to bestquantile summariestuples kept, ratio to bestchain2.18× (323)1.10× (2,807)tree1.00× (148)1.26× (3,211)smallest-first1.24× (183)1.28× (3,278)largest-first2.72× (403)1.00× (2,556)32 shards · hashed · k = 32each column against its own best shape Structures

The shape one structure will not fold

Folding thirty-two shards largest-pair-first keeps 2,556 quantile tuples against a balanced tree's 3,211 — a fifth of the space saved. The same fold on the counter tables beside them leaves 403 counts of error against the tree's 148. A deployment holding both cannot fold once and be right twice.

 6080100how far a full leaf looks for room, in siblingsmean leaf fill, per cent12481664randomascendingdescendingascending, 1% late131,072 keys · leaves of 64 · fan-out 64a reach of 1 is the adjacent-sibling rule When it does not fit

A key passed along the row

A full B+-tree leaf that offers a key to its immediate neighbours before splitting leaves an ascending stream 67.2% full. Let it look one sibling further and the same stream fills its leaves completely, 2,048 leaves where there were 3,048, for about the same key moves. On random keys each doubling of the reach adds a few points of fill and more writes than it saves, and at the whole parent a key travels sixteen leaves on average. On a stream that is mostly in order the same reach costs almost nothing.

 errors, by piecetaken by(0, 0, 0)1(0, 0, 1)1(0, 0, 2)1(0, 1, 0)1(0, 1, 1)1(0, 2, 0)3(1, 0, 0)2(1, 0, 1)2(1, 1, 0)3(2, 0, 0)30 of 10 covered more than once · the numbers are the searchesk = 2 · 3 pieces10 distributions What is taught wrongly

A schedule nobody writes down

A search scheme is valid when its searches between them cover every way the errors can fall — ten cases at two errors, enumerable in a line. A scheme missing one of them finds seven occurrences of eight, all real, at the right error counts, and reports nothing wrong.

 rounds, if every ready cell ran at oncerow by row65,793column by column65,793anti-diagonal by anti-diagonal513reads that miss the cacherow by row6.3%column by column28.2%anti-diagonal by anti-diagonal31.1%fully associative · 32 lines × 8 elements · LRU263,169 reads and writes per order What the machine does

The order with the best depth

An edit-distance table can be filled row by row, column by column, or one anti-diagonal at a time, and the anti-diagonal order is the one that needs the fewest rounds — 513 against 65,793 on two strings of 256 characters, because every cell on an anti-diagonal is independent of the others. Stored the usual way, row by row, it also misses the cache on 31.1% of its reads, where row order misses 6.3%. The order that is best for parallel work is worst for the memory it runs on.

 bits heldbalanced49,593huffman41,589the answer comes backbalanced: sorted · 26 operationshuffman: sorted · 24 operations32 documents · zipf lengths83.9% of the ordered tree What the libraries do

The smaller tree hands it back unsorted

A frequency-shaped tree is sixteen per cent smaller and returns its documents in code order. A balanced one is larger and returns them sorted. The trade is d log d comparisons against a saving, which is not close — until the answer is truncated.

 extensions attempted9,206 dead7,594 livebit-vector ranksthe loop: 168,000the descent: 24,0868 patterns · 1 error · sigma 2054.8% dead · 6.98x Structures

The branches that find nothing

An approximate search over a twenty-symbol alphabet attempts sixteen thousand eight hundred extensions and nine thousand two hundred of them produce an empty interval. That is a full rank walk whose entire result is the discovery that nothing was there.

 rounds, if every ready cell ran at oncerow order, stored by rows65,793anti-diagonal order, stored by rows513anti-diagonal order, stored by diagonals513reads that miss the cacherow order, stored by rows6.3%anti-diagonal order, stored by rows31.1%anti-diagonal order, stored by diagonals8.7%fully associative · 32 lines × 8 elements · LRU263,169 reads and writes per order What the machine does

The table stored the way it is filled

Store an edit-distance table by anti-diagonals instead of by rows, and the anti-diagonal fill keeps its 513 rounds while its cache misses fall from 31.1% of reads to 8.7%. It does not fall to row order's 6.3%, and the gap is not noise — on caches of four and eight lines the two rates are 9.4% and 6.3%, exactly three to two, because a cell reads from two earlier diagonals and only one earlier row. The same layout turns row order into the order that strides, at 28.3%. How a table is stored and the order it is filled in are one decision, and its price is the number of earlier fronts the recurrence reads.

 a fixed-length codeleaves in order␣acdefghilmnoprstuvwythe best ordered treeleaves in order␣acdefghilmnoprstuvwythe best tree of any shapeleaves in frequency order␣eahnrstdiloucfgmpvwythe symbols, in the order the descent reports them21 symbols in 2,048 positionsone set, 2 of 3 sorted What is taught wrongly

One set, three orders

The symbols an interval holds do not depend on the tree's shape. The order they come out in does, and a search that accumulates a running count as it reads them computes a plausible number that is wrong on eighty per cent of queries.

 01,024120 phrases · 1,024 characters60 drawn, every one pointing right Structures

Every copy points right

A greedy self-referential parse chooses each phrase's source from text already produced, so an occurrence copied from another lies strictly to its right. That one fact removes a visited set from a propagation, exactly as a left-first walk removed an array one strand ago.

All threads