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

The thread: Measured, not assumed — page 11

Page 11 of 12, continuing the same thread in the same order.
0.010.11101001000QuicksortQuicksortQuicksortShellsortHeapsortMerge sortMerge sort with a cutoffInsertion sortBubble sortSelection sortn²time × space, as a multiple of n²n = 8,192 · light: auxiliary slots · dark: the input counted toonone under n² What a bound is

A floor under a product

Every lower bound written here so far puts a floor under one quantity. The published time–space bound for sorting puts one under a product: T·S is Ω(n²), so buying time with space and space with time cannot both be done. Measured, heapsort's product is 0.0028 n² — four hundred times under a bound nothing can beat. The bound is not wrong. It is stated in a model where the input may not be written, and every sort here writes to the input, which is where its working memory actually is.

 one text16 short documentsprosecopies of one baseprose, one textr/n 0.2996z/n 0.1273prose, many short documentsr/n 0.3053z/n 0.1301copies of one base, run togetherr/n 0.0638z/n 0.0354one copy per documentr/n 0.0768z/n 0.04188,192 characters throughoutthe outlined cell is the one that was empty What the libraries do

A collection is a construction

The same characters, arranged as one copy per document or cut across the copies, give a different run count, a different boundary cost and a different answer about which structure to build. Which one a benchmark used is usually not recorded.

 range minimum and chain838,797255.0%range minimum, no chain285,46086.8%one descent over D119,97236.5%the document array, the chain and a range minimumthe document array, a range minimum and one bit per documentthe document array, in a wavelet tree64 documents · 16,447 characters14.3% of the published apparatus The other axis

The apparatus, three times smaller again

Eight hundred and thirty-nine thousand bits became two hundred and eighty-five thousand, and now a hundred and twenty thousand. The listing apparatus is fourteen per cent of what it was and holds one array, which is the only part of it that was ever information.

 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.

 equal lengths5.00 bits100.0%lengths as one over rank4.15 bits83.4%a few long, many short4.31 bits86.7%one document holding most of the text1.69 bits39.5%log₂ 3232 documents · 8,192 characters100.0% to 39.5% What is taught wrongly

A saving quoted without its collection

A check asking whether a compressed document array is smaller than the plain one passes on the rounding whenever the document count is not a power of two. It would report a saving of nothing as sixteen per cent, on a collection that has no redundancy at all.

 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.

 02040255075100125one sampled position in every …of the index, per centplain marks: 18.5%Elias-Fano: 3.8%16,384 characters14.9% off at one in 32 The index that replaces the text

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.

 a loop over the alphabet1,478,400the compound walk, inside the loop134,40011xone descent per node18,91678x6 patterns · 1 error · sigma 2155.8% of the extensions were dead The index that replaces the text

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.

 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.

 020405101520queries answeredfile-equivalents read and written, in allevery query from nothingthe counts keptparts of equal widthparts the counts balanceuniform keys, 2²² keys, 8K wordsevery answer checked against a sort What a bound is

A file written once for the queries after

An exact selection against a file of four million keys counts the whole file into a thousand or more pieces on its first pass, keeps the one piece holding its rank, and throws the rest away. Kept, those counts save every later query one full read of the file, from the second query on. Written out as parts, the file makes each later query read a fraction of it — but a pass that counts 3,582 pieces can write only seven, because each part needs a buffer. On a heavy tail, parts of equal width never pay; parts cut where the counts say the keys are pay by the second query and bring twenty-three selections from 69 reads of the file to 9.

 02040608000.50011.502errors permittedbranches that find nothing, per cent5.75x6.98x9.22xthe label is thesaving at that budget8 patterns · 8 characters31.3% to 74.9% What the libraries do

A looser budget wastes a larger share

More errors permitted means more work, and the fraction of that work which was never going to help rises with it — from thirty-one per cent at no errors to seventy-five at two. The saving is worth most where the search is most expensive.

 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.

 acdefghijklmnopqrstuvwyzroot24 of 26 symbols present54 ranks · 51 nodes What is taught wrongly

A walk that does not prune

Remove the emptiness test and the descent visits every node of the tree, returns exactly the same symbols with exactly the same intervals, and costs sixty per cent more. No test of the answer can see it.

 plain bit vector19,475compressed blocks4,55723.4%Elias–Fano3,90520.1%positions, priced as Elias–Fano3,59118.4%16,385 rows · one in 32 markedElias-Fano at 20.1% Structures

A position split in two

Write each sorted position as a high part and a low part. Store the low parts packed and the high parts as a bit vector in which the k-th one sits at position (p >> w) + k. A select on that vector and a low read recover any position.

 both halves locate250,584100.0%the reverse half counts only226,50490.4%and its marks are Elias-Fano210,93484.2%the saving spent on sampling241,47596.4%16,384 characters · one in 3284.2% smaller, or the same size and faster The other axis

The ladder, and the rung that spends

Two hundred and fifty thousand bits, then two hundred and twenty-six, then two hundred and eleven. The fourth rung takes the whole saving and buys a four-times denser sampling with it, landing at ninety-six per cent of where it started and locating several times faster.

 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.

 "t than"8 found · set 8 · frontier 4"of her"7 found · set 7 · frontier 4" that "16 found · set 16 · frontier 11" every"31 found · set 31 · frontier 19"the ev"8 found · set 8 · frontier 4"o of c"8 found · set 8 · frontier 5" than "15 found · set 15 · frontier 9"ime ra"7 found · set 7 · frontier 4the visited set, pale; the sweep's frontier, dark17,715 phrases examined either way1.67x on what is held The index that replaces the text

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.

 124816326410step width, cellscache lines a stepstored by diagonalsby diagonals, each line-alignedstored by rows512 × 512, lines of 8 cellsone step of an anti-diagonal What the machine does

Eight cells at once

The anti-diagonal fill order exists because its cells do not depend on one another, and every table filled here has been walked one cell at a time anyway. Computed eight at a time, a step touches 5.71 cache lines on the layout that stores the table by diagonals and 10.87 on the one that stores it by rows — and per cell the first keeps falling to 0.42 while the second stops at 1.27. The prediction that a diagonal step would touch three or four lines was wrong, and line-aligning each diagonal only takes it to 4.94.

 01e+42e+43e+44e+450100one sampled position in every …bitsplain, one bit a rowcompressed blocksElias-Fano16,384 rowscrosses at one in 4 What is taught wrongly

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.

 bits heldthe model3,591the structure3,905one rank, in operationsbinary search10 stepsselect and walk1 select + 0.7016,385 rows · one in 32 marked14x on the operation What is taught wrongly

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.

 0102030100200one sampled position in every …of both halves saved, per centplain marks: 13.5%Elias-Fano: 1.8%16,384 characters17.6x against 2.3x What the libraries do

The floor was the marks

A saving reported as about a sixth of a bidirectional index, falling to an eighth and levelling off. Represent one array properly and it falls to a fiftieth instead — most of what was being dropped was a badly encoded bit vector.

 factor against the published loopthe compound walk11xthe enumeration78xthe two, multiplied860xnothing measures thisan index with both78xthe shortfall is 11x, and the walk's factor is 11x6 patterns · 1 error · sigma 21the larger of the two, not the product What is taught wrongly

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 loop over the alphabet107.9the compound walk10.0the cheapest hereone descent per step19.016 exact patterns of 12ranks per step · sigma 21 What the libraries do

The saving that is a loss

An operation that is seventy-eight times cheaper on a branching search costs twice as much on an exact one. It reports every symbol present in order to hand back the one that was asked for, and a search that knows its character needs none of the rest.

 020406080255075100125one sampled position in every …of the plain index, per centsize: 84.7%67.5 steps16,384 characters · 8-character patternssize falls, the walk lengthens Structures

Bits and steps on one frame

The size falls from ninety-nine per cent to eighty-six as the sampling thins, and the walk to a sampled position rises from two and a half steps to sixty-four. Neither line is the answer; the answer is a point on the pair.

 phrase lengths2,71222.6%phrase sources2,71222.6%phrase literals1,1309.4%boundary orders5,42445.3%three permutations of 226 elements: 1,808 bits each, and one is the inverse of another226 phrases · 4,096 characters45.3% in the orders The other axis

Half an index is three permutations

A phrase index stores a length, a source and a literal per phrase — and three orderings of its boundaries, at forty-five per cent of the structure. One of the three is the inverse of another, and nothing needs both at once.

 0a1b2split3split4a5a6b7split8a9b10split11a12b13split14accept9 character tests · 5 splits · 1 accepting(a|b)*a(a|b)(a|b)(a|b)15 states Structures

Two states per operator

Thompson's construction adds a bounded number of states per rule and no rule copies a sub-machine, so the machine is linear in the expression and is built in linear time. Every exponential in this field is somewhere else.

 a second hash, unordered0.054 entries read on an absent key14.435.79 storedthe bits below the bucket, unordered0.059 entries read on an absent key14.435.79 storedthe bits below the bucket, sorted0.057 entries read on an absent key8.975.21 storedthe bucket's own bits, sorted5.743 entries read on an absent key11.275.80 storedtag comparisons an absent key's lookup makes8,192 slots · buckets of 8 · 8-bit tags38% fewer What the machine does

A tag that answers more than yes

A byte of hash in front of each entry has one bit of output per slot: this tag matches or it does not. Cut it from an ordered field instead and a bucket's tags can be kept sorted, so a lookup stops at the first tag above its own — 8.97 comparisons for an absent key instead of 14.43, for 3.55 tag-byte shifts an insertion. The obvious ordered field is the trap. Take the tag from the bucket index's own bits and every key in a bucket shares them: 5.74 entry reads on an absent key instead of 0.054, a hundred and seven times more.

 50%30%10%3%1%0.050.10.20.512share of queries outside the top 2% of rankscost over parts balanced by keysbalanced by past queriessize × queries equal(∫√q)², predictedseven parts, fifty past queriesdotted: parts balanced by keys What a bound is

Parts cut where the questions are

A file of four million keys, written once as seven parts so that each later selection reads only its own part, can be cut where the keys are or where the questions are. When nine queries in ten ask about the top 2% of ranks, parts balanced by keys cost 1,170 block transfers a query. Parts that each serve an equal share of past queries cost about as much, and a little calculus says they must, on average. Parts cut so that each one's size times its share of queries is equal cost 290, which is the optimum's square-root law, measured to within a third at every concentration tried. The saving lasts exactly as long as the questions stay where they were counted: moved a percentile and a half, the fitted parts cost more than the plain ones.

 rounding of ⌈log₂ d⌉skew of the lengthsthe estimate, 17%source files10.5% · d 222essay paragraphs11.5% · d 522technical paragraphs11.9% · d 179revision paragraphs16.5% · d 30whole essays9.1% · d 12whole technical documents2.1% · d 8share of the plain array's bitssource files at one version The index that replaces the text

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.

 0100200300400102030copies of the basebits held during one querythe visited set: 420the frontier: 2666-character patterns20x to 1.58x What is taught wrongly

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.

All threads