Choosing a data structure
The cost table of the path's data structures and the method that starts from the most frequent operations: diagnosing a slowdown, matching a need to a structure and reading the cost of an operation.
- 36 cards
- 6 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
- The steps
- Scenarios
A few cards from the deck
Choosing a data structure: what is it?
Show the answer
The decision to keep the data organisation whose operations cost the least for the ones the program performs most often.
No structure is best everywhere: the hash table searches fast but does not sort, the array accesses fast but inserts badly. So you choose from the operations, not from habit.
What does this program print?
```python
from collections import deque
f = deque([1, 2, 3])
f.append(4)
print(f.popleft(), f)`1 deque([2, 3, 4])4 deque([1, 2, 3])1 deque([1, 2, 3, 4])1 deque([2, 3])
Show the answer
1 deque([2, 3, 4])appendadds 4 on the right,popleftremoves and returns the oldest item, 1. It is a queue: first in, first out, and each operation costs O(1).To choose a structure, start by listing the program's most frequent …, then compare their … in each candidate.
Show the answer
To choose a structure, start by listing the program's most frequent operations, then compare their cost in each candidate.
Speeding up a rare operation at the expense of a frequent one is the most common way to pick the wrong structure.
Double-ended queue (deque): what is it?
Show the answer
A sequence where elements are added and removed at both ends in constant time.
In Python,
collections.dequeoffersappend,appendleft,popandpopleftin O(1), wherelist.pop(0)shifts every element and costs O(n).