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

Space — the series

14 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. peak slots held at once, logarithmic18645124096Insertion sort11Selection sort11Bubble sort11Heapsort11Shellsort11Quicksort, median of three22log nQuicksort, random pivot28log nQuicksort, first-element29log nMerge sort with a cutoff4,106nMerge sort4,110nn = 4,096, random inputone slot = one array element or one stack frame

    Measuring what an algorithm keeps

    Four counters measure what an algorithm does and none of them measures what it holds. An in-place sort and an out-of-place one with identical comparison counts are different algorithms, and until this phase the site had no way to say so. Two primitives close the gap, and the second of them counts something no array counter can ever see.

    part 1 · space
  2. 10010³1010010³nstack framesa stack of 512 framespivot: first-elementpivot: median of threepivot: random pivotMerge sortalready sorted input, n from 64 to 4,096one frame charged as one slot

    The stack nobody counts

    Merge sort makes 8,192 calls to sort 4,096 elements and holds fourteen of them at once. Depth-first search on a grid holds twelve vertices, or sixty-six, or a hundred and forty-four, depending on which of three equally standard implementations is running. The stack is a resource, it is the one that fails hard rather than slowly, and nothing that watches the data can see it.

    part 2 · space
  3. peak slots held at once, logarithmic18645124096Insertion sort11Selection sort11Bubble sort11Heapsort11Shellsort11Quicksort, median of three14log nQuicksort, random pivot32log nQuicksort, first-element4,097nMerge sort with a cutoff4,106nMerge sort4,110nn = 4,096, already sorted inputone slot = one array element or one stack frame

    In place is a claim, and it is usually wrong about quicksort

    Heapsort holds one slot at its peak. Quicksort holds twenty-two at n = 4,096 on random input and 4,097 on a sorted one. Merge sort holds 4,110. All three are described with the same two words, one of the three descriptions is false, and the false one is the algorithm the phrase is most often attached to.

    part 2 · wrong
  4. 10⁵10⁶10⁷11010010³10⁴comparisonspeak auxiliary slotsInsertion sortSelection sortBubble sortMerge sortHeapsortQuicksortQuicksortQuicksortShellsortMerge sort with a cutoffn = 8,192, random input5 on the frontier, 5 dominated

    The frontier between time and space

    The question of which sorting algorithm to use has an honest answer, and it is a shape rather than a name. Comparisons on one axis, peak auxiliary space on the other, and five of the ten algorithms here are on the Pareto frontier while five are dominated — beaten on both counts at once, so that no weighting of the two costs makes them the right choice. Heapsort is one of the five that lose.

    part 3 · space
  5. pale: total slots ever allocated · dark: peak held at onceone buffer, allocated once16,38416,400peak 100% of na buffer per merge229,37616,386peak 100% of nn = 16,384, random input208,687 comparisons each — identical in time

    The space the model does not see

    A slot is not a byte, a frame is not a slot, sixteen thousand allocations are not one allocation of the same size, and none of these numbers includes the input. The space counters are the newest instrument here and the honest account of what they miss is longer than the account of what they measure — including one bound this phase set out to demonstrate and could not.

    part 3 · space
  6. ε = 0.0515 → 29 (1.93×)ε = 0.0238 → 73 (1.92×)ε = 0.0177 → 136 (1.77×)ε = 0.005152 → 270 (1.78×)ε = 0.002397 → 674 (1.70×)reportedoccupied at the peak20,000 arrivals · lognormalpeak = resident + period, to 14%

    The tuples a summary does not report

    A Greenwald–Khanna summary at ε = 0.01 answers `tuples` with seventy-seven. Watched through the run it holds a hundred and thirty-six. The gap is the compression period, it is 1.70 to 1.93 times across every tolerance measured, and it is the number a deployment has to allocate.

    part 4 · space
  7. 4,097 rows · one in 32 marked3.1% of the rows

    The array that says where is twice the samples

    An index keeps one suffix-array value in every thirty-two, and a bit vector over all n rows saying which. The vector is sixteen thousand bits and the values it points at are seven thousand — the index of the samples is twice the samples.

    part 5 · space
  8. 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%

    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.

    part 6 · structures
  9. 05e+31e+41.5e+40246bits kept in the low partbits⌊log₂(n/m)⌋ = 2low partshigh vector2,049 marks in 16,385 positions1 bits between the two roundings

    The flat bottom of a shallow curve

    The low width is chosen as the floor of log of the universe over the count. Rounding it up instead costs one bit on five thousand, because the total is m·w plus n over two to the w and the minimum is where those two are equal.

    part 7 · bounds
  10. 01e+42e+43e+44e+450100one sampled position in every …bitsplain, one bit a rowcompressed blocksElias-Fano16,384 rowscrosses at one in 4

    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.

    part 8 · wrong
  11. 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

    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.

    part 9 · wrong
  12. 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

    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.

    part 10 · indexes
  13. 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

    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.

    part 11 · practice
  14. 01e+42e+43e+44e+450100one sampled position in every …bitsplain, one bit a rowcompressed blocksElias-Fano16,384 rowscrosses at one in 4

    Twenty bits apart

    Two representations of one sparse set, six thousand seven hundred and forty-five bits against six thousand seven hundred and sixty-five. One exploits sparsity and the other exploits runs, and on this set at this density they price identically.

    part 12 · machine

All series