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

Tuning constant — where it appears

A threshold whose shipped value was chosen against one measurement, and which may be wrong for a different count and right for the one it was set by. It may be right for the count it was set by and wrong for a different one, so the measurement that produced it is part of its meaning.

Named by 3 essays across 2 fields — each of them below, with the objects they name alongside it.

1010010B (elements per block)block transfers per searchtuned for B = 64Sorted arrayB-tree tuned for B = 64van Emde Boas — told nothingM = 16,384, B as drawnone layout, 7 block sizes, no parameter

The layout that is told nothing

A B-tree is built around a block size somebody looked up. The van Emde Boas layout is given neither the block size nor the memory size, and across seven block sizes spanning a factor of 64 it tracks the best structure that was told them. An algorithm with no parameters making a claim at every level of the hierarchy at once is a strange thing to be able to measure, and this is what it costs.

applied · Transfer 1010010⁵minruncomparisonsshipped: 32randomnearly sortedTimsort, n = 8,192comparisons; rings mark the measured minimum

The threshold somebody chose

A minrun of 32. An insertion cutoff of 16. A gallop threshold of 7. A depth limit of twice the logarithm. Four numbers, in four real source files, none of which appears in any complexity analysis — and each of which decides more about what these algorithms do than the analysis does. Swept, they turn out not to be optima, and finding out what they are instead is the point.

practice · Count 1100ε — the exponent the fanout is B toelements written per key33445679ε = 1 — the B-tree ·fanout 256 · 3transfers a queryε = 0.5 · fanout 16 · 5a querythe number above eachpoint is what a querycostsB = 256, M = 16,384 (M/B = 64)131,072 random keys

One dial between two structures

A B-tree writes 226 elements of block for every key stored and a log-structured store writes two. They are presented as rival designs. They are one design at two settings of an exponent that nothing in either description mentions, and every setting between them is available.

applied · Transfer

Named alongside it

The objects these essays reach for when they reach for this one.

B-treeBlock transferExternal-memory modelParameter choiceAmortised analysisBuffered treeCache obliviousComparison countCost modelCutoffDepth limitFanout

All concepts