Bits of select support against positions inspected, at ten per cent density

Bits of select support against positions inspected, at ten per cent density

A bit vector of 65,536 positions holding 6,554 ones and costing 77,979 bits with its rank directory. The upper curve keeps one position per L ones and scans from it: cheap, and its worst case grows with L. The lower flat curve is the dense-and-sparse structure, whose worst case is 7 ones passed at every sample interval, because the bound comes from the sub-block spacing and the interval only decides how many anchors are stored. Passing those 7 ones costs up to 186 position inspections at this density. Every one in the vector is asked for, so these are worst cases rather than the worst of a sample. Binary search over the rank directory costs no extra bits at all and inspects 510 positions. Both axes are logarithmic.

Drawn at 700 × 430, wide on the page. Everything above is what select-cost returns with no arguments; the caption is the generator's own, computed from the numbers in the drawing rather than written beside it.

3 essays call select-cost. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about — which is what optcheck and figfill exist to catch.