Lesson · Data Structures · Sets and choices

Choosing a Structure

The operation mix decides the structure: which operations, whether order matters, whether the set changes. The data does not decide. The instrument is a cost table with a “not supported” column, because the reason not to use a hash table is usually not that it is slow at predecessor — it is that it cannot answer predecessor at any speed.

Open the interactive lesson Practice

Five structures, seven operations, and the column that decides most choices

Core ideas

What this lesson establishes

One rule for choosing, one instrument for applying it, and one thing the instrument must record that a cost column cannot express.

The mix decides, and the data does not

“What kind of data is it” is almost always the wrong question. The questions that decide are: which operations happen and in what proportion; does anything need the keys in order; does the set change or is it built once. The same million integers want a sorted array for a read-only range workload and an AVL tree if they change, and the integers are identical.

A cost table is the instrument, and it has to include the refusals

Write the operations as rows and the structures as columns and fill in the bounds this course proved. Then fill in a dash wherever the structure cannot answer the operation at all. The dashes decide more choices than the numbers do, and a table of numbers alone silently suggests that every structure can do everything at some price.

A measured total ranks structures on one mix, and only that mix

The lab runs a stated mix on every representation it can execute and ranks them by counted cost. Change the proportions and the ranking changes — on a lookup-heavy mix at n = 32 the sorted array costs 108 and the linked list 513; change it to insert-at-one-end and remove-at-the-other and the sorted array cannot run at all while the list costs 168.

The material

The cost table, the refusals, and one mix ranked by execution

The five structures this course built, the operations they refuse, and what changes when the proportions change.

This course has built eight structures and proved a bound for each. Putting the useful five in one table is the whole of the method, and the table is not new information — every entry in it was proved in one of the thirteen lessons before this one.

search insert delete min predecessor range ordered walk sorted array log n n n 1 log n log n + k n hash table 1 exp 1 exp 1 exp n — — — AVL tree log n log n log n log n log n log n + k n binary heap n log n log n 1 — — — union–find — — — — — — — hash table: expected, under simple uniform hashing; Θ(n) worst case binary heap: delete of a known position; finding the key first costs n union–find: same-set tests and merges only, at log n per operation

Three entries in that table deserve saying out loud. The hash table’s three 1s are expected under an assumption about the keys, with a Θ(n) worst case that no hash function removes. The heap’s min is 1 but its search is n, because it keeps no order between siblings. And union–find’s row is dashes all the way across, because it is not a container at all: it answers “are these two together” and holds no retrievable keys.

The refusals, which are where most choices are actually made

A hash table cannot answer predecessor (“the largest key below k”), cannot answer a range query, and cannot produce the keys in order without sorting them from scratch. This is not slowness: hashing deliberately destroys the order, which is how it gets its constant. The dash is the right entry, and a column of numbers with a large number in that cell would be a lie.

That refusal is the in-memory form of a mistake System Design counts in I/O. “Hash vs Tree for Ranges” prices a hash index and a B-tree on a workload of nine hundred point lookups and a hundred small ranges a second, and the hash index — which wins the point lookup one I/O to three — loses the mix by a factor of nearly a hundred and seventy, because its only way to answer a range is to read the whole table. Same mistake, with a disk attached and a number on it.

One mix, executed

The lab costs a mix by running it. It ranks the five sequence representations whose cost model it can execute — dynamic array, sorted array, doubly-linked list, stack and queue — rather than the five in the table above, because those are the five with a per-operation cost model already proved on this course. The lesson it teaches is the same one, and it is about the refusals:

n = 32, mostly lookups: 12 search, 2 index, 2 delete, 2 min sorted array 108 cheapest; binary search dynamic array 478 scans doubly-linked list 513 scans, and pays to reach a position stack — cannot search, index, delete or take a min queue — the same four refusals n = 32, insert at one end, remove at the other: 8 + 8 doubly-linked list 168 cheapest dynamic array 440 shifts on every front insertion sorted array — cannot be told where to insert stack, queue — cannot delete at a position

Two mixes, and the winner changed and the refusals changed with it. The sorted array is four to five times cheaper than anything else on the lookup-heavy mix and cannot run the second one at all — not slowly, at all — because an insertion at a caller-chosen position is not an operation a sorted array has. That is the shape of a real structure choice far more often than a factor of two on a shared operation.

And the ranking is a measurement of one mix at one size. 108 against 513 is a fact about eighteen operations on thirty-two elements. Move the proportions and the order changes; move n and the gaps change, because log n and n diverge. The table of bounds is what generalises, the measured ranking is what convinces, and the honest report uses both — the bound to say what will happen and the count to show it happening.

Interactive

Choosing from the operation mix

Totals where a structure can answer, a refusal where it cannot

Set the mix, and every structure runs it

Set the proportions of each operation and the size. Every representation runs the mix with a counter, the totals are ranked, and a structure that cannot perform an operation in the mix is reported as refusing it rather than given a large number. Change the proportions and watch both the winner and the set of refusals change.

Workload

elements held—

index by position—

search for a value—

insert at the front—

insert at the end—

delete at a position—

take the minimum—

Operations in the mix—

Cheapest—

Its total—

Dearest that can run it—

Out of the running—

Dearest : cheapest—

Method

Choosing a structure from a workload

Four steps, and the third eliminates more candidates than the fourth ranks.

Write the operation mix down as proportions

“Mostly reads” is not a workload. Twelve searches, two indexes, two deletions and two minima at n = 32 is. Include the operations that happen rarely: a single range query per hour still eliminates every hash table.

Ask the three questions that decide

Does anything need the keys in order? Does the set change after it is built? Is any single operation on a latency deadline, as opposed to the sequence being fast on average? The first eliminates hashing, the second eliminates a sorted array, the third eliminates anything amortised.

Cross out every structure that cannot answer something in the mix

This is the step that does the work. A dash is not a large number and it cannot be traded against a small one. Do this before totalling anything, because a structure that refuses one operation in the mix is not a candidate at any cost.

Total the survivors, then name what the winner cannot do

Rank by counted cost on the mix. Then state, explicitly, the operations the winner refuses — because the next requirement to arrive will be one of them, and having named them is the difference between a choice and a guess.

Mixes and refusals

Score 0 / 0

Choose the answer you can justify.

Three workloads, three answers

The same five structures against three mixes. The interesting column is the last one.

A. a read-only price list: lookup by key, range scans, no changes hash table lookups are fastest RANGE: not supported sorted array log n lookup, log n + k range, no inserts needed AVL tree same as sorted array, and pays constants for an update ability the workload never uses → sorted array. It cannot insert; the workload never asks. B. a live index: lookup, insert, delete, occasional range hash table three operations in one, RANGE: not supported sorted array insert and delete are n AVL tree log n on all four → AVL tree. It cannot answer a lookup in one step; nothing else here can do all four at all. C. a scheduler: insert a task, always take the most urgent binary heap insert log n, min 1, extract log n AVL tree the same bounds, larger constants, plus order it does not need hash table MIN: n. It has no order at all. → binary heap. It cannot find a task by name: SEARCH is n. measured, mix A at n = 32 in the lab's five representations: sorted array 108, dynamic array 478, list 513, stack and queue refuse

Every one of the three answers was decided by a refusal rather than by a ratio. The hash table lost A and B because it cannot do ranges; the sorted array lost B because it cannot insert cheaply; the heap won C and the sentence naming what it cannot do — find a task by name — is the most useful line in the analysis, because that is the requirement that will arrive next.

Notice what the AVL tree is in workload A: correct, general, and wrong. It answers everything the mix asks at the same asymptotic cost as the sorted array, with larger constants, in exchange for an update ability the workload never exercises. Choosing the more capable structure by default is a real cost paid for a real reason that does not apply.

For a faded rehearsal, take workload D: a union-of-components problem — repeated “are these two connected” and “merge these two groups”, with no key ever retrieved. The supplied observation is that four of the five structures in the table have a dash in every column that matters, because none of them maintains a partition. Name the structure, quote its proved bound from this course, and then say what it cannot do — the list is long, and that is the point.

Common mistakes

Believing a hash table is always the fastest mapIt cannot answer predecessor, cannot answer a range, and cannot produce the keys in order — not slowly, at all, because hashing destroys the order that those operations are about. Its constant-time lookup is also expected rather than worst-case. System Design’s “Hash vs Tree for Ranges” is the same mistake with an I/O count attached: the hash index wins the point lookup and loses the mix by a factor of nearly a hundred and seventy.

Choosing from the data rather than from the mix“They are integers, so use a hash table” and “there are a lot of them, so use a tree” are both non-arguments. The same million integers want a sorted array if they never change and are scanned in ranges, an AVL tree if they change, a heap if only the smallest is ever wanted, and a disjoint-set forest if the question is connectivity. The data is identical in all four.

Reading a measured ranking as a general resultThe lab’s 108 against 513 is one mix at one size. Change the proportions and the winner changes; change n and the ratios change, because the structures being compared have different growth rates. The cost table is what generalises and the measurement is what makes it concrete, and a report that offers only one of the two is either unconvincing or unjustified.

Check your understanding

✓

Finish when your first question about a workload is which operations it contains rather than what the data is.

You should be able to reproduce the cost table for the five structures with the dashes in the right places, eliminate candidates on refusals before totalling anything, rank the survivors on a stated mix, and state in one sentence what your chosen structure cannot do at all.

Note: Every cost in that table was produced by running an operation sequence on the structure and counting, and every bound beside it was proved once. The next course spends them: Sorting and Selection uses the heap directly for heapsort and for merging many runs, and turns the expected-height argument left open in “The Shape Problem and Random BSTs” into the exact expectation 2(n+1)Hₙ − 4n that randomised quicksort pays on every input.