TEC Techniques Technique
Choosing a data structure
Also known as: Choosing a data structure · which structure to use · list or set · slice or map · data structure cheat sheet · the cost of operations
Choosing a structure starts with the list of operations a problem needs, not with a name. The price of the same operation in a list and a set, a slice and a map differs hundreds and thousands of times: in a measurement, from a few nanoseconds to milliseconds. A map of operation costs in Python and Go, a rule for choosing, and the case where the honest answer is to keep two structures at once.
A program checks whether a user has already been sent a mailing, if user in sent, and its sent is a list. With a hundred addresses this goes unnoticed. With a hundred thousand each check looks through the whole list, and a loop over new addresses turns from a minute into an hour. Change one bracket, sent = set() instead of sent = [], and the same check becomes thousands of times cheaper. Below is what the basic operations cost in the standard structures of Python and Go, measured on the site's server.
The map is read by rows: for each operation, green cells are structures where it costs less than two microseconds, red ones where it costs from twenty microseconds to milliseconds. Tick the operations your problem needs: the scene shows which structure does all of them cheaply, and if there is none, which two do it together. For example, “is x there”, “add” and “take the minimum” together are beyond any single one: a set does not know order, a heap cannot search quickly, and a sorted array inserts expensively. People keep two.
The idea
First write out the operations the program will do often, and for each one how many times. Then find a structure where all the frequent operations are cheap. If there is none, keep several structures over the same data, each for its own operations, and update them together. The cost of rare operations hardly matters: a program that searches a million times and sorts once must be fast at searching.
This is the answer to “which is faster, a list or a set”: it depends on what for. Appending to a list is cheaper than adding to a set, since no hash needs to be computed. Checking whether an element is present is thousands of times cheaper in a set. The structure of each is worked through in its own article, the dynamic array, the hash table, the binary heap, the stack and queue, the linked list; here they are gathered on one map.
Cheat sheet
| Needed often | Python | Go | Why |
|---|---|---|---|
| is the element there | set, dict | map | a hash table: O(1) on average |
| a value by key | dict | map | the same |
| by index, a sequential pass | list | slice | an array: O(1) by index, sequential access the fastest of all |
| at both ends | collections.deque | a slice at its ends or a ring buffer | O(1) at an end |
| the minimum, the next by priority | heapq | container/heap | a heap: O(log n) |
| in order, nearest, a range | a sorted list and bisect | a sorted slice and sort.Search | binary search O(log n), insertion O(n), but by a fast shift |
| order and frequent insertions | third-party: sortedcontainers | third-party trees | the standard libraries have no search tree |
| insertion in the middle at a known place | — | container/list | a linked list: O(1) if the place has already been found |
Two differences between the languages are worth remembering. In Go taking an element off the front of a slice costs nothing: a = a[1:] just moves the start, while in Python list.pop(0) shifts the whole tail, and a queue needs a deque. Conversely, Python has a ready set, while in Go a set is made from map[T]struct{} or map[T]bool.
Code
One problem, a log of orders with deadlines (add, cancel, is there such a deadline, the earliest deadline), and two implementations. The first keeps everything in a list. The second keeps a dictionary “deadline → how many orders” for checks and cancellations and a heap for the minimum, and throws cancelled deadlines out of the heap only when they surface at the top. The program counts how many elements each one touched: this number does not depend on the machine.
On a thousand operations the list touches 60 times more elements, on twenty thousand 900 times more: its work grows as the square of the log's length, while the dictionary with a heap grows almost linearly. The answers agree, and that is the first thing to check after changing the structure.
What it costs
The price of a choice is not only time. Two structures over the same data mean twice the memory and code that must update both consistently: forget to decrement the counter on a cancellation, and the heap will return an order that does not exist. Hash tables take more room than arrays (how much exactly is in the article on estimating memory) and do not keep order. A sorted array is fast to read, but every insertion shifts the tail.
Hence the order of action. A simple structure while the data are few: a list and an array are the fastest of all on a hundred elements. An estimate when the data become many: how many operations of each kind, and what each costs. And a profiler if the program is slow and the estimate does not explain why: in a profile a slow x in list shows up at once.
Problems
The problem is that very order log, where one structure is not enough.
Orders by deadline