Practice question · Put in order
Order the steps of choosing a data structure by workload, as the lesson describes it.
- Look up which structures make those operations cheap
- Identify which of those operations dominate the hot path
- Choose the structure, or combine two, so the dominant operations are fast
- Weigh the memory each candidate costs against the time it saves
- Write down the mix of operations the program actually performs
Hints
- The workload has to be known before anything about it can be called dominant.
- The trade-off can only be weighed once there are candidate structures to weigh.
Show the answer
- Write down the mix of operations the program actually performs
- Identify which of those operations dominate the hot path
- Look up which structures make those operations cheap
- Weigh the memory each candidate costs against the time it saves
- Choose the structure, or combine two, so the dominant operations are fast
Why
The method runs from evidence to decision: catalogue the operations, find the dominant ones, match structures to them, price the trade-off, then choose. Starting at the last step, by reaching for a familiar structure, is the pitfall the lesson names, habit is not a workload analysis.
Practise Choosing a Data Structure by Workload
The app has 5 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.
More questions on Choosing a Data Structure by Workload
- The lesson's rule is to choose a structure by which operations dominate the workload. Why is 'which structure…
- A hash table serves a workload of 90% lookups by key and 10% requests for the smallest key well, because the…
- Sort each requirement by whether a hash table alone is enough for it.
- A cache needs fast lookup by key and eviction of the least recently used entry. No single structure does…
- Select every statement the lesson supports about choosing structures.