08The decision map
In Chapter 7 we opened the hash table up and watched dict and set answer in a single step. In Chapter 6 we laid the list and the array out as a plain row of slots. So the machinery is yours now. And yet, sitting at the keyboard, you still pause for half a second between [] and {}. This chapter turns that pause into reflex. Here's the plan. We walk five questions in a fixed order, and the first yes hands you the one right container. Then we read every operation's price tag off a single page, watch an array pack tighter than a list points, reach for the queue that never shuffles its neighbours, and total the memory bill for a million items — all before Titanium stops playing. The whole way through, one question decides everything: what is your data being asked to do? That, and never your syntax, is what picks the structure. By the end you'll walk into Chapter 9's functions choosing your data structures on sight.
01Five questions, one answer
Let's start with the thing that feels like it should be taste. Picking a data structure looks like a matter of preference — some people just like dictionaries. But it isn't taste. It's an interrogation, and the suspect is your data, never your syntax. You ask five questions in a fixed order, and the very first yes hands you the verdict. No weighing six options, no second-guessing. Five straight nos, and a standing default is almost always fine. That's the whole chapter in one breath. Everything after this section is just the evidence that each verdict holds up.
Here are the five, in the order that matters. 1. Do you look things up by a key? Type "Blinding Lights", get back 200 — a name pointing at a value → dict. 2. Does each item count at most once, and do you mostly ask "is it in there?" The distinct artists in your library — The Weeknd, David Guetta, Sia, each once → set. 3. Is it a fixed record, where every position means something and nothing ever changes? ("Blinding Lights", "The Weeknd", 200) → tuple. 4. Do items enter and leave at the ends? An up-next queue you push onto and pop from → deque. 5. Is it millions of plain numbers? Raw audio samples, a column of track-lengths → array. Five straight "no"s? Then reach for the honest default: list — ordered, editable, and cheap to grow at the end.
list is simply what's left when your data made no special demand at all.list, the honest default. That is the entire decision map.A map you only read is a map you'll forget. So take the interview for a spin. Below are six real modelling jobs pulled straight from the playlist app. Slide through them and watch the tree fire: which question answers yes, and which structure lights up as the verdict.
Here is every verdict at once, holding real playlist data: six shapes on one small screen. Read it as the answer key to the interview above.
from collections import deque
from array import array
track = ("Blinding Lights", "The Weeknd", 200) # tuple — a frozen record
length = {"Blinding Lights": 200, "Titanium": 245} # dict — title → seconds
artists = {"The Weeknd", "David Guetta", "Sia"} # set — each name once
up_next = deque(["Titanium"]) # deque — grows at both ends
samples = array("i", [0, 141, 297, 410]) # array — millions of ints, packed
playlist = ["Blinding Lights", "Titanium"] # list — ordered, the defaultdict. But notice the two answers weren't fighting; they were describing different layers. In real code you nest them: a dict keyed by title, whose values are tuple records — {"Blinding Lights": ("The Weeknd", 200)}. The map picks the outer shape; the questions repeat for whatever rides inside.✗ The myth
Alist can do everything, so just use a list and move on — the structure is a stylistic choice you can always fix later.✓ The reality
The dominant operation dictates the structure, and the wrong pick silently turns a free O(1) into an O(n) you pay on every single call. Ask "is this artist in my library?" against a 100,000-namelist and Python scans the whole street; the same question against a set is one hop. Measured on this machine, the set answered roughly 11,000× faster. That's not taste — that's the difference between instant and sluggish.list isn't a consolation prize. It's ordered so "the 3rd track" means something, it's mutable so you can add and remove, and it over-allocates spare slots so appends are almost free — grow one from empty and its byte-size climbs in jumps (56 → 88 → 120 → 184…), leaving room to grow so most appends touch nothing but a counter. When your data makes no special demand, that bundle of "just works" is exactly what you want.The deeper cut — "the first yes decides" is a labelled simplification
Two honest caveats, so nothing here is a half-truth. First, "the first yes decides" is a rule of thumb about the dominant access pattern, not an iron law. Real data is layered, so real programs compose structures rather than pick just one: a list of tuples (a table of records), a dict whose values are lists (an artist → their songs index), a set of tuples (unique key-pairs). You run the interview once for the outer shape, and again for whatever lives inside. That's exactly why tuple can serve where a list can't: a tuple is hashable, so it can be a dict key or a set member, while a list raises TypeError: unhashable type: 'list'. Second, when this chapter calls a dict or set lookup "one hop" or "O(1)," that's the average case, backed by hashing. A bad run of hash collisions can drag a single lookup toward O(n). In everyday code with ordinary keys that effectively never happens, which is why we teach the clean version first. And the six aren't the whole family: frozenset (an immutable set you can use as a key), Counter, and OrderedDict are specialisations that answer the same five questions with one extra constraint bolted on.
Five questions land you on a structure — but "trust me, it's faster" is a promise, not a proof. What does each choice actually cost, operation by operation? One table, every price tag laid bare →
tuple earn its own question when a list holds the same three fields? Because a tuple is hashable and a list is not. Freeze ("The Weeknd", 200) and you can use it as a dict key or drop it in a set; try the same with ["The Weeknd", 200] and Python stops you cold: TypeError: unhashable type: 'list'. Question 3 isn't about "can't change" for its own sake — immutability is the ticket that lets a record ride inside the keyed structures above it.dict and set are the same machine — a hash table — and a set is just a dict that forgot its values (measured: 62.5 vs 70.5 MiB for a million items, the gap being exactly the missing value pointers). list and tuple are one idea — a row of pointers — split only by "can it change?" You're choosing among fewer distinct ideas than six names suggest.list is simply what's left when the data made no special demand at all.set that promised never to change, so it can itself be a key. A Counter is a dict whose values are tallies. An OrderedDict is a dict that guarantees order as an API, not a side-effect. Answer the same five questions, then ask "any extra constraint?" — and the specialised container names itself."ends_only" — a stand-in label for what the data does (items enter and leave at the ends), not a magic string you'd ever type into choose(); real code reads that access pattern straight off the job. Press Next and watch the gate, the code and the verdict move as one.02Every price tag on one page
Before the map, a quick refresher on the currency it's priced in. Big-O doesn't measure seconds. It measures how the work grows as the data grows. O(1) means the cost stays flat whether you're holding ten songs or ten million: one step, every time. O(n) means the cost rises in step with the count — twice the data, twice the work. Chapter 6 showed why a list reads by index in O(1) but inserts into the middle at O(n): every element past the gap has to shuffle up one slot. Chapter 7 showed why a hash table finds a key in O(1) on average, no matter how big it gets. Here is the whole course so far, every structure and every price tag, pressed onto a single page.
Here is what the page is really about: the price tag is set by the layout in memory, not by how the code reads in your editor. The line s[i] looks identical on a list and a deque — the same three characters — yet one answers in a single hop and the other walks block by block. So this table isn't a syntax cheat-sheet. It's a map of machines: six different ways to arrange bytes, and the costs that fall out of each arrangement.
Read the table as a set of trade-offs and one row stands out. The list and the set disagree on exactly one square that matters here: x in s. On a list it's O(n): the machine walks the row, comparing item after item, until it finds a match or falls off the end. On a set it's O(1): one hash, one probe, done. Same question ("is this title in the collection?"), same line of Python, wildly different bill. Let's put a number on it.
# the *identical* line of code — only the container underneath changes
songs = ["Blinding Lights", "Titanium", "Levitating", "bad guy"] # a plain list
"Blinding Lights" in songs # True — but it scans item by item: O(n)
fast = set(songs) # tip the same titles into a set, once
"Blinding Lights" in fast # True — one hash probe, no scan: O(1)if x in c: reads the same either way. The cost class flips because the machinery underneath it changed shape. Speed lives in the container, not the cleverness.✗ The myth
Big-O is the running time — a smaller O always means a faster program, full stop.
✓ The reality
Big-O is the growth rate, not the clock. Two structures can share an O-column and still differ tenfold on the constants. A list and an array both index in O(1), yet the array's 16 packed samples ride into the CPU in a single 64-byte cache line, while the list hands over one address at a time and chases each to a different corner of RAM. Same price tag on paper — wildly different wall-clock speed, for a hardware reason Big-O can't see (the callout below shows exactly why).
array row is identical to the list row. Same O(1) index, same O(n) middle insert, both ordered, both mutable. Every square that Big-O can see matches. So if the price tags are the same, why does array even exist?The deeper cut — the asterisks, and what Big-O can't see
Those little marks on the table are load-bearing. Amortized O(1) (the *): a list append is usually a single pointer write. But when the block it reserved fills up, the whole thing relocates to a bigger block — O(n), but only that once, averaged flat over the many cheap appends around it. You can watch the reservation grow in jumps: an empty list already weighs 56 bytes, and its capacity steps up at lengths 1, 5, 9, 17, 25, 33… — chapter 6's overallocation, caught in the act.
Average O(1) (the ~): a hash lookup only sinks toward O(n) if a pile of keys happen to collide into the same bucket. That's vanishingly rare with real data, and guaranteed nowhere. Order is its own footnote. Since CPython 3.7 a dict iterates in insertion order: feed it Titanium, Blinding Lights, Levitating, bad guy and it hands them straight back in that order. The same four dropped in a set come out shuffled (on this machine: Titanium, Levitating, bad guy, Blinding Lights), because a set promises nothing about sequence at all.
A deque is a doubly-linked chain of fixed-size blocks — 64 slots each in CPython, and you can prove it: a deque's memory footprint jumps every 64 items you add (at length 64, 128, 192…). Both ends are O(1) by construction. But reaching dq[500000] has to walk block after block — O(n), and about 600× slower than dq[0] when you time it. That's why the deque is an ends-only tool: brilliant at a queue, hopeless as a lookup table.
And the big one the curio is circling: Big-O counts element moves and probes, never nanoseconds. So array and list land in the same O-column, yet the array wins hands down on the constants. Its numbers sit wall-to-wall as raw bytes — a thousand of them fit in about 1,080 bytes — so they stream through the cache. The list stores the same thousand numbers as 8,856 bytes of pointers, each aiming at a 28-byte integer object parked somewhere else in RAM. Identical Big-O, but the array is smaller and faster, because it never chases a pointer. That gap — packed bytes versus a scatter of pointers — is the next section's whole story.
The array and the list share a row, yet one packs its numbers shoulder-to-shoulder and the other stores nothing but addresses. Let's open both up and watch an array pack while a list points →
s[i] is three characters whether s is a list or a deque — so how can one be hundreds of times slower? Because the layout, not the syntax, sets the price. On a list, dq[500000] is one multiply-and-jump (chapter 3's arithmetic). On a deque there's no single street to compute on, so it walks block by block from the nearest end. Timed on this machine: dq[0] in ~36 ns, dq[500000] in ~22,000 ns — about 600x slower, for the identical-looking line.list and array share every square on the table — same O(1) index, same O(n) middle, both ordered and mutable — yet the array is plainly faster in practice, and here is the hardware reason. The CPU never fetches one byte; it pulls a fixed 64-byte cache line at a time. An array('i') packs 16 consecutive ints into a single line, so one fetch feeds the next ~16 reads — that's spatial locality. A list holds only 8-byte pointers; each one you follow jumps to an int object parked elsewhere, so most reads are a cache miss — a full round-trip to RAM, roughly two orders of magnitude slower than a value already sitting in the CPU. Same Big-O, same element-move count — but one layout streams and the other stalls. When two rows tie on Big-O, the far-left column — layout in memory — breaks the tie.dict remembers the order you built it; a set doesn't. Drop the same four titles into each — Titanium, Blinding Lights, Levitating, bad guy — and the dict hands them straight back in that order (guaranteed since Python 3.7), while the set returns them scrambled. It isn't that the set is careless: order is a free side-effect of how a dict lays its entries down, and a promise a set never made, because "is it in?" never needed one.03array packs, list points
Big-O isn't the only bill a data structure sends you. There's a second invoice that never shows up in a complexity table — the memory bill — and on that line the two workhorses of this chapter, the list and the array, could hardly be further apart. Same numbers, same lookup cost, but wildly different weight.
Chapter 6 showed you what a list really is under the lid: an array of pointers — 8 bytes per slot, each one an address pointing at a full Python object living somewhere else in RAM. And Chapter 2 put a small integer on the scale at 28 bytes all by itself. Add those up, and one stored number in a list costs roughly 36 bytes: 8 for the pointer, 28 for the boxed int it points at. The standard library's array module throws all of that overboard. Writing array('i', ...) declares one thing up front — "signed 4-byte integers, nothing else" — and then lays the raw values down shoulder to shoulder in a single block. This is Chapter 0's even-stride street — 6000, 6004, 6008 — finally made literal: in an array('i') the 4-byte values themselves sit in the consecutive boxes, the exact wall-to-wall layout C and NumPy use. No pointer, no object header, no reference count — just 4 bytes per number, about nine times smaller. The price of the discount is printed right on the receipt: one type code, one type. Try to append a string and you get a TypeError the instant you ask.
[i] lookup — but one carries 36 bytes of machinery per number and the other carries 4.0xc8 — 11001000, the very byte Chapter 0 drew.In daily use an array feels almost exactly like a list. append, remove by value, indexing, slicing and iteration all behave the way your fingers expect. The single difference is the wall: hand it anything that isn't the declared number type and it refuses on the spot — no silent coercion, no mystery crash three functions later.
from array import array
lengths = array('i', [200, 245, 194]) # 'i' = signed int, 4 bytes each
lengths.append(177) # feels exactly like a list
lengths.remove(245) # by value, first match — like list
print(lengths.itemsize) # 4 (bytes per slot)
print(len(lengths) * lengths.itemsize) # 12 (3 ints, packed tight)
lengths.append("HUMBLE.") # TypeError: 'str' object cannot be interpreted as an integer'b' is 1 byte, 'h' is 2, 'i' is 4, 'q' is 8; 'f' is a 4-byte float and 'd' an 8-byte double. Because every slot is identical and there's nothing wedged between them, len(a) * a.itemsize is the exact byte count of your data — no estimate, no hidden headers.array.array only when you have lots of numbers and a measured memory or interop problem — for everyday code a plain list is fine and far more flexible. And when the real job is number-crunching, the scientific world skips straight to NumPy: the same wall-to-wall packing, plus fast math that sweeps whole blocks at once down in C. You'll watch it win a race shortly.a[i], Python has to lift those 4 raw bytes back up into a full int object to hand you — so a[0] is a[0] comes back False, a freshly built box on each read. Pure-Python iteration runs about the same speed as a list, sometimes a hair slower. The tight packing only buys speed when a C loop — NumPy — devours the whole block without boxing anything. Here, memory is the honest win; raw speed is NumPy's story.✗ The myth
"array is just a faster list — swap it in for a free speed-up."
✓ The reality
It's a smaller, stricter list: identical Big-O, roughly 9× less memory, but locked to a single numeric type. Reading an item is no faster in Python — the real speed only arrives when C code (NumPy) swallows the packed block whole.
The deeper cut — when "9× smaller" quietly becomes "2×"
"36 bytes per number, 9× the array" is a labelled simplification — dead accurate when every integer is its own object, which is the normal case for a big pile of distinct numbers (measured on this machine: exactly 36.0 B per list item, 4.0 for the array). But Python quietly pre-builds the small integers from −5 through 256 once at startup, and hands out those same singletons everywhere they're needed. Our playlist lengths — 177, 194, 200, 245 — all live inside that window. So a list of them doesn't allocate four fresh int objects at all; it just stores four 8-byte pointers aimed at shared singletons that were going to exist anyway. Its marginal cost collapses to about 8 B per slot (measured), and the gap to the array narrows to roughly 2×. The 9× headline is precisely true where it counts — large, distinct values, exactly the situation that makes you reach for array in the first place. It's honestly smaller than 9× only when the integers are tiny and repeated. Same spirit as Chapter 0's "off or on is a useful lie": true at the altitude we teach it, and now refined.
A list pays for its flexibility in bytes — but it hides a sharper weakness that has nothing to do with size: the front. Delete item #0 and every remaining item has to shuffle down one slot to close the gap. And one everyday job pounds that exact spot, over and over — the queue that doesn't shuffle. →
a = array('i', [1000]); a[0] is a[0] is False, because each read lifts the 4 raw bytes into a freshly built int box. But watch the edge case — for a small value it flips to True: array('i', [200])[0] is …[0] returns the same object, because 200 is one of Python's pre-cached singletons and the "new" box is really the shared one. Same code, opposite answer, decided entirely by whether the number sits in the −5…256 cache.len(a) * a.itemsize is the exact byte count of your data — no estimate, no hidden headers. Four 'i' ints is 4 × 4 = 16 bytes, full stop. A list can never tell you that: ask its size and you learn how many pointers it holds, never the weight of the objects at the far end of them.array('i') and the block reads c8 f5 c2 b1 (little-endian, one number every 4 bytes): 200 lands as 0xc8 = 11001000, the very byte chapter 0 built switch by switch. The list stores none of those bytes — only 8-byte addresses pointing at int objects that hold them elsewhere.list of them allocates no new int objects; it points four times at shared singletons, and its marginal cost collapses to ~8 B, shrinking the gap to about 2x. The 9x is exactly true where it counts — big distinct values — which is precisely when you'd reach for an array.04The queue that doesn't shuffle
Your player keeps two lines of songs, and they run in opposite directions. There's the up-next queue: songs join at the back, and the one that plays next is always taken from the front — first in, first out, a FIFO queue. And there's your play history: hit previous and you get back the track you just heard — last in, first out, a stack. The stack is the easy one. A plain list already is a stack, because append() and pop() both work at the tail end. You push onto the end, you pop off the end, and nothing else in the list ever moves. Both are O(1): one poke at the last slot, done.
The queue is where it hurts. Serve the front of a list and you must call pop(0) — and chapter 6 already showed you the bill for that. A list is one solid, wall-to-wall row of slots. Delete the first one and there's now a hole at the front, so every remaining element gets copied one slot to the left to close it. One method call, n−1 moves. Serve a ten-thousand-song queue that way, song by song, and you pay for roughly fifty million element copies just to hand out ten thousand tracks. The front of a list is the most expensive door in the house.
The fix has a blunt name: collections.deque, the double-ended queue. Its trick is to stop being one long street. Instead of a single contiguous block, a deque is a chain of small blocks — each block a strip of 64 cells, each block storing the address of the block before it and the block after it. The deque itself is almost forgetful: it remembers just two addresses — where the first block is, and where the last block is. Its cells hold plain 8-byte references, exactly like a list's slots do. Working at either end touches only that end's block. To serve the front you lift one reference out of the leftmost cell and nudge a cursor inward; to add at the back you drop a reference into the next free cell. A whole fresh block is hooked onto the chain — or a spent one unhooked — only when an end block completely fills or empties, which is about once every 64 operations. Nothing in the middle is ever touched. That is why append, appendleft, pop and popleft are all O(1), and why a deque also does moves a list can't, like rotate(n), alongside the familiar extend and count.
popleft) and adding at the back (append) each disturb a single end block; the interior is never shuffled. That is the whole reason both ends are O(1).from collections import deque
up_next = deque(["Blinding Lights", "Levels", "Strobe"])
up_next.append("Titanium") # a new song joins the back O(1)
now_playing = up_next.popleft() # serve the front -> 'Blinding Lights' O(1)
up_next.appendleft("Encore") # a VIP request cuts to the front O(1)
up_next.rotate(1) # wrap the last track around to the front
print(up_next)
# deque(['Titanium', 'Encore', 'Levels', 'Strobe'])n−1 still waiting each shuffle down one slot; serve the next and n−2 shuffle, and so on — so the list pays (n−1)+(n−2)+…+1 = n(n−1)/2 moves, the square of its length. That's why a 4,000-song queue costs about 8 million element moves to drain, while the deque just lifts one block per serve and stays a straight line. Watch the red bar leap while the green one barely stirs.deque gives you two cheap doors by trading the single wall-to-wall row for a chain of blocks. Reach for it the instant you add or remove at the front.deque(maxlen=50) and it becomes a fixed-size window: push a 51st item and the far end silently drops off. It's the one-liner behind "your last 50 played tracks" — append forever, and it prunes itself. Down at the metal it's a ring buffer: feed a deque(maxlen=64) the raw audio samples streaming past and it always holds exactly the last 64 — average them and you've built a moving-average low-pass filter, the same fixed-window trick sound hardware runs in silicon. The cap turns "remember everything" into "remember the last N," for free.list not just a deque under the hood? Because the chain that buys you two cheap ends quietly taxes the middle. On a list, songs[5000] is one multiply-and-jump — the address falls straight out of arithmetic (that's chapter 3's whole point). On a deque there's no single street to do arithmetic on, so reaching the middle means walking block by block from the nearest end: O(n). A list trades cheap ends for a cheap middle; a deque makes the opposite bet. Neither is "faster" — they're built for different jobs.✗ The myth
pop(0) is one operation. I called a single method, so it costs a single step.
✓ The reality
One call, n−1 moves. Every element still waiting gets copied one slot left to close the gap. Draining a 10,000-song queue this way is ~50 million moves; a deque does the same job in 10,000. Same result, a thousandfold difference in work.
The deeper cut — where "O(1)" and "touches only one block" get more honest
Two of the phrases above are labelled simplifications, and here's the refinement. First, the deque's O(1) is a stronger promise than a list's. A list's append is only amortized O(1): most calls are instant, but when the underlying row fills up the list must allocate a bigger one and copy every element across — a rare O(n) hiccup you pay for in bulk later. A deque never does that. It never relocates existing elements. When it needs room it just mallocs one more 64-cell block (about 528 bytes: 64 references × 8 bytes, plus 16 bytes of prev/next bookkeeping) and hooks it on. So append/appendleft/pop/popleft are worst-case O(1) — no single call ever stalls.
Second, "64" and "O(1) everywhere" aren't universal laws — they're this CPython's design. The block length is a compile-time constant (currently 64); another build could choose differently. And two deque operations escape the O(1) club: indexing or slicing the interior is O(n), as the curio showed, and rotate(k) costs O(k) steps. A single-step rotate(1) is genuinely O(1), but rotate(n/2) walks half the chain. The clean rule to keep is narrower and true: the two ends are always cheap; the middle never is.
Time costs are now mapped edge to edge — stack, queue, and the shuffle that ruins the front of a list. But twice this chapter we've muttered "heavier" and "lighter" about memory without ever weighing anything. Enough muttering. Let's put a million items on the scale →
list is already a perfect stack: append() and pop() both work the tail, and nothing else in the row ever moves — both O(1). LIFO costs you nothing. The deque exists only for the other direction: the queue, where you serve from the front. FIFO is the hard problem; a list's single cheap door faces the wrong way for it.sys.getsizeof(dq) as you append: it holds flat, jumps, holds flat, jumps — a fresh step every 64 items. That's the deque quietly malloc-ing one more 64-cell block and hooking it onto the chain. The "64" you'll hear quoted isn't folklore; it's a compile-time constant you can measure in ten lines.append is only amortized O(1) — most calls are instant, but occasionally the whole row relocates and every element is copied across. A deque never does that: it never moves an existing element, it just allocates one more ~528-byte block (64 references × 8 bytes + 16 of prev/next bookkeeping) and links it on. So all four of append/appendleft/pop/popleft are worst-case O(1) — no single call ever stalls.05The bill for a million items
Your two-song playlist has quietly grown into a library — a million tracks, each with a length in seconds. But a length in seconds is human metadata, the sticker on the sleeve. A track's actual bytes are its waveform, a run of roughly 8.8 million raw audio samples, each a signed 2-byte integer. We'll weigh the generic million first, then come back to those samples, where the packing bites hardest. That's a fine excuse to ask the question the whole decision map has been circling: what does a structure actually cost? Not in theory — in bytes, on this machine, right now. So let's do the honest experiment. Store the same million numbers five ways, watch the process's real memory, and read the receipt. The ranking is not a matter of taste. It falls straight out of how each structure lays its bytes down in the RAM street from chapter 0.
Here is the receipt, measured with Python's own tracemalloc at n = 1,000,000. A dict is the heaviest by far, because it never just stores your numbers. It builds a hash table: a wide array of slots, kept deliberately two-thirds empty so lookups stay fast, and for every entry it files away a hash, a pointer to the key object, and a pointer to the value object. A set is the same machine minus the values — one boxed key per slot, spare room and all. A list is lighter: one 8-byte pointer per item, each pointing at a separate boxed integer living elsewhere in RAM (exactly the "street of addresses" picture from chapter 0). One bookkeeping note before the bars land. That boxed int weighs 28 bytes on the scale — §3's figure — but the allocator hands it out in a rounded-up 32-byte block. So the same item reads 36 B weighed raw (8 + 28) and 40 B weighed at allocation (8 + 32); this section uses the honest 40. An array — array('i') or a NumPy row — throws all of that away and packs the raw 4-byte numbers wall to wall: no pointers, no per-number object, with fast math on top. Narrow the type and it packs tighter still — audio samples fit an array('h') at 2 bytes each, so 32 of them ride in every 64-byte cache line the CPU pulls. And a generator answers a question none of the others can: what if you never need to store the sequence at all, only produce it on demand? It holds no numbers — only a suspended frame (its local variables plus a marker of where it paused), resuming on each pull to compute one more value and freezing again. You'll build one from the metal up in chapter 10; here we only weigh it.
n = 1,000,000. The dict is not full of "more data" than the generator — it is full of bookkeeping. That gap is the whole lesson.next() thaws the frame, runs forward to the next value, and re-freezes. You'll assemble that frame yourself in chapter 10; for now, just note that "essentially nothing" has an exact, tiny weight.Now make it move. Drag n from a single track up to a million and watch each bill grow — and grow at wildly different rates. Notice what the slider exposes at the small end: the generator's fixed overhead means that for a handful of items it is not the cheapest option at all. Below a few dozen numbers a packed array undercuts it. The generator only becomes the lightest thing on the chart once n climbs past that — and from there it never loses.
base + rate × n; only the rate differs — and the generator's rate is zero, so its bar never grows. At the far left the flat green bar is actually taller than the packed array: fixed overhead you haven't earned back yet.sys.getsizeof(a_million_ints) and it answers 7.63 MiB — and lies to you by a factor of five. That figure is only the container: a million 8-byte pointers. It does not count the million separate 28-byte integer objects those pointers aim at, scattered across RAM. The true bill is nearer 38.6 MiB. A pointer knows an address, not the size of the house at the end of it.4 × 1,000,000 bytes flat — about 3.9 MiB, a tenth of the list. And because the numbers sit contiguous, 16 of them ride in every 64-byte cache line the CPU fetches, so one fetch feeds the next 16 reads instead of chasing a pointer per number. Make it concrete: to compute the loudness of a million raw samples (the sum of their squares), NumPy sweeps the packed block in C and finishes in a few milliseconds; the same sum over a list, boxing and unboxing every value, runs one to two orders of magnitude slower. That is exactly why the standard array isn't the finish line — when the job is math over the whole block, NumPy's C loop is.samples = array('h', [0, 12000, 24000, 18000, -6000, -22000, -14000, 3000]) (peak 24000). Packed in an array('h') at 2 bytes apiece, the whole clip is 2 × 8,800,000 bytes — about 17 MB laid wall to wall, so a loudness walk streams it: 32 samples per 64-byte cache line, one fetch feeding the next 32 reads. Hold the identical samples in a plain list and each becomes a boxed int — ~28 bytes of object plus an 8-byte pointer — so the same audio balloons to roughly 300 MB scattered across the heap, chasing one pointer per sample. Same numbers, same peak; the packaging alone is the gap between 17 and 300.✗ The myth
A bigger structure means you gave it more data. Shrinking memory means throwing information away.✓ The reality
Most of a big structure's bill is bookkeeping — pointers, cached hashes, deliberately empty slots — not your values. You can often cut memory 10× while keeping every last number, just by choosing packaging that carries less overhead.The deeper cut — why the "rate × n" line is a labelled simplification
The interactive draws each bill as a straight line, base + rate × n. That is a useful lie — honest at a million, rounded at the edges — and here is the truth underneath it. Real structures don't grow smoothly. They grow in power-of-two jumps. A dict's size holds flat, then leaps: on this machine it steps at 224, 352, 632 bytes as you cross its resize thresholds, because when a hash table fills past its load factor it doubles its slot count in one allocation. A list overallocates the same way — 88, 120, 184, 248 bytes — grabbing spare room so that most appends are free. So the true curve is a staircase, and the line is its average.
And one more thing the line hides, one of the nicest facts in this whole section: those 28-byte integer objects are shared when the values repeat. A list of a million distinct numbers really does cost 38.6 MiB. But a list of a million copies, [200] * 1000000, costs just 7.63 MiB, because all million pointers aim at the same one integer object. The container is identical; only the boxed-int bill collapsed. Memory doesn't count values — it counts objects, and Python is quietly thrifty about making new ones.
So here is the entire decision map, applied one last time to the library we have carried since chapter 0 — each line a different answer to "what does this data need to do, and what am I willing to pay for it?" Read the last line, lengths — an array('i') of durations in seconds — as the metadata layer. One altitude below it, each track is itself an array('h') of ~8.8 million samples: the same packed-versus-boxed choice made once more on the actual bytes. The waveform is the metal the playlist sits on.
from collections import deque
from array import array
track = ("Blinding Lights", "The Weeknd", 200) # tuple — a frozen record
library = [track] # list — ordered, grows at the end
by_title = {"Blinding Lights": track} # dict — O(1) avg lookup by key
artists = {"The Weeknd", "David Guetta"} # set — unique, O(1) membership
up_next = deque(["Titanium", "Blinding Lights"]) # deque — O(1) at both ends
lengths = array('i', [200, 245]) # array — packed 4-byte intsEvery structure on this map just sits there, holding bytes at its own price, until code reaches in and acts on it. Next: functions — little machines you build once and feed the library through, with inputs, a value handed back, and a strange, strict rule about where their variables are allowed to live →
base + rate × n — a useful average. The truth grows in power-of-two jumps. A list holds flat, then leaps 88 → 120 → 184 → 248 as it doubles its reserve; a dict grows its entire slot table in one allocation the moment it crosses about two-thirds full. The smooth line is the average of a staircase.[200] * 1_000_000 costs just 7.63 MiB — a fifth as much, holding the same million slots. Why? All million pointers aim at the same one int object. Memory doesn't count values; it counts objects. The container is byte-for-byte identical — only the boxed-int bill collapsed, because there was one box to build instead of a million.dict the heaviest structure on the chart? Almost none of its 70.5 MiB is your numbers. It sizes its slot table well above a million and keeps a third-plus of the slots deliberately vacant, so hash collisions stay rare and lookups stay one hop. Each live slot then files a cached hash plus a pointer to the key and a pointer to the value. You're paying for empty air — the price of finding any entry in a single jump.dict ~74 B, set ~66 B, list ~40 B, array 4 B, generator 0 B. The numbers are identical in every one — a few bytes of actual data. Everything above 4 bytes is bookkeeping: pointers, cached hashes, deliberately empty slots. The structure you pick decides how much packaging rides on each value.Five container shapes, and each answers one question: do you need order, uniqueness, fast lookup, or a fixed record? These fifteen tiny programs let you watch the right tool click into place — then reshape one container into another.