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

Packed representation — where it appears

Storing a structure's entries end to end with no unused slots, computing each entry's position rather than reserving a regular grid. It saves space, about half for a triangular table, at the price of address arithmetic and without improving locality.

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

01234567801234567891724303539424410182531364043111926323741122027333813212834142229152316one unit = one subproblem given a valueeach number is a storage offset, of 45 slots

A triangle stored in a square

An interval table has a cell for every range of keys and nothing below its diagonal, and it can be stored as a square array, as packed rows, or as packed diagonals — the last matching the order it is filled in. On sixty-four keys, with every read replayed through a small cache, the square misses 39.7% of its reads, packed rows 38.8%, and packed diagonals 78.4%. Storing a table in the order it is written is storing it in the order it is not read.

tables · Table run together1.00xsigma 21 · 5 bitsone separator1.00xsigma 22 · 5 bitsa separator each1.20xsigma 36 · 6 bitsruns 1.00xruns 1.00xruns 1.02x16 documents of 512 characterspacked bits, against running them together

Two currencies for one separator

Giving every document its own boundary marker costs a fifth of the packed text and three per cent of the run count. Both numbers are right, they are about the same change, and which one a collection pays depends on a structure nobody named.

space · Document

Named alongside it

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

Access patternAlphabet sizeBurrows-wheeler runsCacheDocument collectionDynamic programmingEvaluation orderIndex sizeInterval dpLocalityMemory layoutMiss rate

All concepts