A name with possibilities.

When does a coordinate list use fewer slots?

Consider a fictional grid with three rows and four columns, indexed from one. Every omitted value is defined to be zero. Its four nonzero entries are row one column two equal to seven, row two column four equal to five, row three column one equal to two and row three column four equal to nine. Compare a dense grid with triples containing row, column and value. Count every number as one equal-size slot; ignore shared dimension metadata.

SparseField.com
Reconstruct the grid in the SparseField grid-storage worksheetRows indexed 1–3 · columns 1–4Row 1: 0 · 7 · 0 · 0Row 2: 0 · 0 · 0 · 5Row 3: 2 · 0 · 0 · 9Omitted entries are defined to be zero

01

Reconstruct all twelve cells before comparing sizes

The first row is zero, seven, zero, zero. The second row is zero, zero, zero, five. The third row is two, zero, zero, nine. The coordinate list contains (1,2,7), (2,4,5), (3,1,2) and (3,4,9). Reconstructing the rows checks that each listed value lands in the intended cell and that all eight other cells use the declared zero default. The example has no repeated coordinates. If duplicates were allowed, a separate rule would need to say whether to combine them, reject them or let one entry replace another.

Count both representations in the SparseField grid-storage worksheetCount one equal-size slot per numberDense: 3 × 4 = 12 slotsList: 4 triples × 3 = 12 slotsResult: a tie in this modelCoordinates have a storage cost too

02

Count coordinates as well as stored values

The dense representation uses twelve value slots. Four triples use three slots each, also twelve slots, so this example is a tie under the stated model. With k nonzero entries, the coordinate list uses three times k slots. It is smaller than the twelve-slot dense grid only when k is less than four: zero through three entries. Five entries would require fifteen slots. This comparison does not predict actual memory use because real formats may use different index widths, headers, alignment and compression. Keep those implementation details outside the simple model until they are explicitly measured.

Find the occupancy threshold in the SparseField grid-storage worksheetKeep the 3 × 4 grid fixedList size: 3 × k slotsSmaller when 3 × k < 12Therefore k must be less than 4Actual byte sizes require a separate model

03

Record the assumptions with the result

A reusable worksheet records row and column counts, index origin, coordinate order, default value, duplicate policy and the number of occupied positions. It then records the counting model, dense total, coordinate-list total and comparison result. For this grid the totals are twelve and twelve, with no storage advantage in the equal-size-slot model. A later exercise can change the occupancy while retaining the dimensions to find the threshold directly. Preserve the reconstructed grid alongside the list so another reader can check both the representation and the arithmetic without relying on a visual impression of sparseness.

sparsefield.com

Explore SparseField

Held for potential development. Acquisition inquiries may be considered.

Domain options ↗