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

The thread: The structure decides the count

The same traversal over the same graph, laid out two ways, examines exactly the same edges and misses cache three and a half times as often. What an algorithm costs is decided as much by where its data is as by what it does.
10010³10³10⁴10⁵10⁶10⁷Vcounted workBreadth-firstDijkstra, binary heapDijkstra, all V queuedBellman–Ford, all passesV from 64 to 2048, sparse, fixed average degreework = scans + visits + relaxations + queue comparisons Two parameters

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.

 0$abracadabra1a$abracadabr2abra$abracad3abracadabra$4acadabra$abr5adabra$abrac6bra$abracada7bracadabra$a8cadabra$abra9dabra$abraca10ra$abracadab11racadabra$aball 12 rotations of "abracadabra$", sorted0 character comparisons The index that replaces the text

A search that runs backwards

Twenty-three occurrences of a six-character pattern in sixteen thousand characters, found in twelve rank queries and zero character comparisons. Not few comparisons — none. The algorithm never asks whether two symbols are equal, and it knows how many matches there are before it has located one.

 313roundconc 0.14536hashedconc 1.00309blockedconc 0.14how the arrivals were partitionedworst error over the top keysone summary, k = 32one summary, k = 256the merge of 8Space-Saving · stationary Zipf · 40,000 arrivals8 shards One pass, and no room

The partition the analysis did not mention

Space-Saving and Misra-Gries are the same structure under a stream, related by subtracting one number. Sharded eight ways and merged, one of them is wrong by 313 where the other is wrong by 927 — and swapping how the arrivals were assigned to machines reverses which is which.

 adjacency scansrelaxationsqueue comparisonsvisitsKosaraju, two passes5,632Tarjan, one pass2,560V = 1024, E = 1,536, directed, components plantedevery segment counted exactly Two parameters

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.

 10³10³10⁴Vmodelled missesadjacency listCSR array96% miss27% miss64 lines × 8 elements, fully associative, LRU3.6× between two layouts of one graph Two parameters

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.

 8 patterns of 10 characters over four symbols02,0004,0006,0008,00010,00012,00014,00016,00018,000one cell = 10 positions · shade = fraction read61.6% of the text The data that is not a number

The shift a set of patterns allows

Aho-Corasick reads every character of the text exactly once, whatever the number of patterns. Commentz-Walter reads backwards inside a window and steps over what it can, and on eight patterns of ten characters it looks at sixty-two per cent of a twenty-thousand-character text. The rule that does the skipping is not the one everybody implements.

 each row is one rotation · the table is sorted · the transform is the last columnfirstlast◇the-order-is-the-message-is-the-message◇the-order-message◇the-order-is-the-order-is-the-message◇the-the-message◇the-order-isage◇the-order-is-the-messder-is-the-message◇the-ore◇the-order-is-the-message-message◇the-order-is-the-order-is-the-message◇ther-is-the-message◇the-ordessage◇the-order-is-the-mge◇the-order-is-the-messahe-message◇the-order-is-t… 11 further rotationsmeasured on 8,192 symbols of the same source:H₀ of the text3.899 bitsH₀ of the last column3.899 bitsH₀ after move-to-front, before4.156 bitsH₀ after move-to-front, after1.802 bitsmodel: order 0, before and after a permutationmean run 1.01 → 3.38 The data that is not a number

The transform that emits nothing

The Burrows–Wheeler transform outputs exactly the characters it was given, in a different order. Its zeroth-order entropy is therefore identical to its input's, to fifteen decimal places, and by that measure it has done nothing at all. A Huffman coder handed the result spends 1.935 bits per symbol where the same coder on the same data spends 4.209, and the difference is entirely in the order.

 busiest vertexuniform pairsbusiest 16 · Σd² 43,104 · degeneracy 4attachmentbusiest 114 · Σd² 90,296 · degeneracy 4pairs of neighbours examineduniform pairs — every pair18,480uniform pairs — oriented4,090attachment — every pair42,076attachment — oriented3,339V = 1,024, E = 3,072 on both30 triangles and 249 — the answers, which also differ Two parameters

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.

 roothseirhesssolid: a transition on a character · dashed: a suffix or failure link10 states for 12 pattern characters The data that is not a number

One pass for every pattern at once

Sixty-four patterns, one text, twenty thousand characters read. Running this site's KMP once per pattern reads 1,595,445 — and an implementation missing one kind of link finds fewer occurrences, reads exactly as much, and looks better on every counter.

 1,00010,00010⁴10⁵characters in the collectionbitsFM-index, plainFM-index, compressedrun-length indexsample one in 64 · divergence 0 · r = 22411,900 bits at 32 copies The index that replaces the text

The index that stores the runs

A compressed self-index over thirty-two copies of a text is 30,557 bits, because its size follows an entropy that cannot see a copy. An index that stores the transform as its runs is 11,900 — and at a single copy it is the larger of the two, which is what makes the comparison a claim about repetition rather than about size.

 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.

 levels on the path (outline) · transfers actually paid (filled)B = 411 levels · 6.99 transfers · 16,384 blocks residentB = 166 levels · 3.23 transfers · 4,096 blocks residentB = 644 levels · 1.99 transfers · 1,024 blocks residentB = 2563 levels · 1.30 transfers · 256 blocks residentB = 10243 levels · 1.01 transfers · 64 blocks residentbinary search over the same 4,194,304 keys: 20 transfersB = 1024, M = 65,536 (M/B = 64)20× between binary search and the widest tree Structures

A tree with nodes the size of a block

A B-tree is a binary search tree that has read the hardware manual. Its node holds as many keys as fit in one transfer, so the height falls from log₂ n to log_B n — and the measured cost falls further still, to 1.01 transfers over four million keys, because the top of the tree is small enough to stay in memory. The comparison count goes up.

 cells expandedreads building the estimateNo estimate1,572 expanded · path 356Straight-line estimate1,550 expanded · path 356A*, landmarks252 expanded · path 356 · 6,328 reads to buildV = 2,500, steps cost one to nine, seed 20260910shortest path 356 Two parameters

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.

 11010010⁴10⁵queries answeredcharacter comparisons, cumulative5 queriesScan each timeIndex, then queryone unit = one character comparison · 4 doubling roundsbreak-even at 5 queries Structures

The index that is the text

A suffix array sorts all 4,097 suffixes of a text — 8.4 million characters of string, in total — and examines exactly zero characters doing it. It then answers a search in 91 characters where a scan costs 1,472, and the whole thing pays for itself at six queries. Both halves of that are worth the same amount of attention, and the first is the one that is usually skipped.

 text position iphi(i)anchor: a run start25 of thema text that repeats itself · 4 copies of 32r = 26 · pieces 24 What the machine does

A function with r pieces

Computed at every one of eight thousand positions across four texts, a function defined on the whole suffix array agrees exactly with r−1 anchors and one addition. Anchor it at the successor instead of the predecessor — one character of code — and it disagrees at 506 of 800 positions while still returning plausible numbers.

 HyperLogLog1024/1024 identicalCount-Min256/256 identicalbottom-k128/128 identicalMisra-Gries20/36 identicalfraction of the state that merged to the identical value→ 1,974→ 10,291→ 2,322→ 8,766two streams of 30,000 · 2,007 distinct keys in the union3 of 4 merge exactly Structures

The summaries that add

Two sketches built over two streams and merged are, for three of the four structures here, byte for byte the summary the concatenated stream would have produced. For the fourth the guarantee survives and the state does not, and calling both properties mergeability hides the difference that matters.

 —1234152abcbcbccbsolid: a transition on a character · dashed: a suffix or failure link8 states ≤ 9, 9 transitions ≤ 11 Structures

Every substring, in fewer states than substrings

A text of 512 characters has 129,416 distinct substrings. A machine that recognises every one of them, and nothing else, needs 831 states — and the bound it is under, 2n − 1, is reached exactly by a string one line long.

 1,8103,6205,4297,239010,00020,00030,00040,000arrivals so farcount of key 1 in the last 4,096Misra-Gries, no clockblocks of Misra-Griesthe truth, and the ring buffera heavy hitter that stops · sampled every 5006,493 claimed, 0 true Structures

The count that outlives its arrivals

A Misra-Gries counter holding six thousand is not a record of six thousand arrivals. It is a number that has been added to and taken from, and nothing in the structure says when any of it happened — so when the key stops arriving the counter stays, and goes on reporting a key with nothing in the window as the heaviest thing in it.

 1M2M4M16M64Mmean run length, in memoriesrandom33 runssorted1 runreversed64 runssorted, 1% arriving late2 runssorted, 10% arriving late7 runs262,144 records, 4,096 in memorydashed: two memories When it does not fit

Runs twice as long as memory

Feed 262,144 random records through a heap that holds 4,096 and the sorted runs that come out average 1.94 memories — the snowplow's famous factor of two. At a fan-in of 63 that saves a merge pass at 262,144 records, and at two of fourteen sizes in all. Feed the same heap a sorted file with one record in a thousand out of place and it writes two runs instead of sixty-four. And it spends 19 comparisons a record doing so, on every input, where sorting the chunks spends five on sorted data. The factor of two is the least of what the method does.

 2585167741,032020,00040,000arrivals so farcountSpace-Saving's floorMisra-Gries's decrementsboth 93840,000 prefixes, 0 disagreementsk = 32 against k = 31 What is taught wrongly

Two structures that are one

Space-Saving never underestimates and Misra-Gries never overestimates, and they are taught as rival structures with opposite failure modes. Subtract one number from every Space-Saving counter and what is left is the Misra-Gries table, key for key and count for count, at all twenty thousand prefixes of a stream and at every table size tried.

 2·0·1·20101206·7·3·25·012012201012102rowsdocumentfirstpattern " was t" · 30 occurrences · 7 documentsA filled row is the first of its document. Reporting one costs a range minimum;reading every row costs one visit per occurrence.English-like · 8 documents30 rows · 7 documents The index that replaces the text

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.

 0%25%50%75%100%ln 2mean leaf fillrandom, even splits2,906 leavesrandom, rightmost-split rule2,949 leavesascending, even splits3,971 leavesascending, rightmost-split rule2,048 leavesdescending, even splits4,095 leavesdescending, rightmost-split rule4,095 leavesbulk-loaded from sorted keys2,048 leaves131,072 keys, leaves of 64each bar names its rule When it does not fit

The keys that arrive late

Insert 131,072 keys into a B+-tree in random order and its leaves end up 70.5% full; in ascending order, 51.6%; in descending order, 50.0%. The rule databases use to fix ascending inserts — split a full leaf at its right-hand end — fills them completely, and it does nothing for descending keys. Let one key in a hundred arrive late in an otherwise ascending stream and the rule's leaves fall from 100% to 53.4% full. How much of an index is empty is decided by the order its keys arrived in, and a trickle of disorder undoes the fix.

 1234567characters addedoccurrencesgrown leftwardsgrown rightwards"tgatatt"4,000 characters · four symbols1 occurrences The index that replaces the text

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.

 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.

 11010³cap on the depthphrases9.8% more phrasesevery occurrence consideredthe earliest only4,096 charactersworst at cap 4 What a bound is

The cap an automaton cannot see

A state of a suffix automaton stands for a set of occurrences and hands back one of them. So a capped parse driven by it can ask whether the earliest occurrence is shallow enough and cannot ask whether any occurrence is — which costs up to 9.8% of the phrases, and only at the caps that bind.

 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.

 24816326412825510⁶10⁷average out-degreecounted workBellman–Ford from every sourceJohnson's reweightingFloyd–Warshall256 vertices, every answer comparedwork: relaxations + heap comparisons Two parameters

One Bellman–Ford buys every Dijkstra

A directed graph of 256 vertices with a third of its arcs negative needs shortest paths between every pair. Running Bellman–Ford from every source costs 25.8 million counted operations on the densest graph drawn; running it once, repricing every arc by what it found, and then running Dijkstra from every source costs 13.1 million, and the one Bellman–Ford is under one per cent of that. Floyd–Warshall's 16.8 million is never the cheapest count on the plate. On the sparsest graphs the repeated Bellman–Ford wins, because its early exit makes nine passes rather than 255.

 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.

 0200400600800cells expanded per query, meanno landmarks897four near the centre423four at random209farthest-first141the corners1268 maps × 150 queriesdots: each map's mean Two parameters

Where the landmarks stand

Four tables of exact distances, each from a chosen cell, turn a straight-line estimate that barely helps on rough terrain into one that cuts a search by a factor of six. Averaged over 1,200 queries on eight maps, the same four tables expand 126 cells a query when their cells are the map's corners and 423 when they are near its centre. The standard choice, each landmark as far as possible from the ones before, expands 141 and loses to the corners on all eight maps. Moving four landmarks to the right places buys more than doubling their number.

 125102050100200100observed queries the selection sawcells expanded, meanon fresh querieson the sample it was chosen fromthe cornersfarthest-first8 maps × 150 fresh queriesflat lines read no queries Two parameters

What the queries know that the map does not

A greedy rule that chooses landmark cells by rerunning a sample of past queries needs two hundred of them to draw level with a rule that reads only the map — and what it finally chooses, on map after map, is the four corners. Give the queries a destination instead of scattering them, and twenty are enough to beat the corners by 29% on eight maps out of eight. A query log is worth reading exactly to the extent that it is not uniform.

All threads