Lists, dicts and what they cost

Most slow Python data code is not slow because Python is slow. It is slow because it uses a list where it needed a dict, and does a scan a million times instead of a lookup a million times.

To see why, look at what each structure is in memory.

A list is an array of pointers

A Python list is one block of memory holding pointers: 8 bytes each on a 64-bit machine. The values themselves live elsewhere, as separate objects. An int object takes 28 bytes. A short string takes about 50.

Measure it:

import sys

nums = list(range(1000, 2000))          # 1,000 ints
list_bytes = sys.getsizeof(nums)        # the pointer array only
int_bytes = sum(sys.getsizeof(n) for n in nums)

print("empty list:      ", sys.getsizeof([]), "bytes")
print("list of 1,000:   ", list_bytes, "bytes")
print("per slot:        ", (list_bytes - sys.getsizeof([])) // len(nums), "bytes")
print("the ints, total: ", int_bytes, "bytes")
print("total:           ", list_bytes + int_bytes, "bytes for 1,000 numbers")

About 36 KB for 1,000 numbers. As raw 4-byte integers, like a database column, the same data is 4 KB. That 9x overhead is the price of every value being a full Python object with a type, a reference count and a value.

The pointer array gives lists their costs:

The last row is the trap. v in xs is a scan, exactly like SELECT without an index. One scan of 100,000 items is fast. 100,000 scans of 100,000 items is 10 billion comparisons.

A dict is a hash table

A dict keeps an array of slots too, but it does not fill them in order. To store a key, Python computes hash(key), a fixed-size integer, and uses it to pick a slot. To find a key, it does the same thing and goes straight to that slot.

So key in d does not look at every entry. It computes one hash and checks one slot, occasionally a few if two keys collided. The cost stays about the same at 10 entries or 10 million.

A set is the same table with keys and no values.

The price is memory. A hash table keeps spare slots so collisions stay rare. When it gets about two-thirds full, it allocates a bigger table and moves every entry over. That is why a dict uses noticeably more memory than a list of the same items, and why its size grows in jumps.

Measure the difference

Here is the scan versus the lookup, on the same 5,000 ids:

import time

ids = list(range(5_000))
id_set = set(ids)
queries = list(range(0, 10_000, 2))     # 5,000 lookups, half of them misses

t = time.perf_counter()
hits_list = sum(1 for q in queries if q in ids)
list_s = time.perf_counter() - t

t = time.perf_counter()
hits_set = sum(1 for q in queries if q in id_set)
set_s = time.perf_counter() - t

print("hits:", hits_list, hits_set)
print(f"list: {list_s:.3f} s")
print(f"set:  {set_s:.5f} s")
print(f"set is about {list_s / set_s:,.0f}x faster")

Your numbers will differ by machine, and the in-browser Python is slower than a laptop. The ratio will not change much: the set is usually hundreds to thousands of times faster, and the gap grows with the size of the list. Double the list and the list version takes twice as long. The set version barely moves.

Dicts are how you group

Lesson 3 of the SQL track showed that GROUP BY is a hash map. In Python you write that hash map yourself, and a dict is the tool:

orders = [
  ("delivered", 120.50), ("shipped", 35.00), ("delivered", 80.25),
  ("cancelled", 15.00), ("delivered", 42.10), ("shipped", 9.99),
]

totals = {}
counts = {}
for status, amount in orders:
  totals[status] = totals.get(status, 0) + amount
  counts[status] = counts.get(status, 0) + 1

for status in sorted(totals):
  print(f"{status:<10} {counts[status]} orders  {totals[status]:8.2f}")

One pass. One entry per status. Memory grows with the number of distinct statuses, not the number of orders. collections.Counter and collections.defaultdict are shortcuts for exactly this loop.

Tuples and strings

Two more structures you will use constantly. A tuple is a list that cannot change: the same array of pointers, a little smaller, and hashable, so it can be a dict key. That makes it the natural key for grouping by two fields, like (city, day).

A string is not an array of pointers. It is one object holding its characters packed together, which is why "delivered" costs about 50 bytes and not 9 pointers. Strings cannot change either. s += "x" builds a new string every time, so joining 100,000 pieces with += copies data over and over. Collect the pieces in a list and call "".join(parts) once.

Picking the right one

A short rule set:

• Order matters, access by position: list.
• “Have I seen this?”: set.
• Look something up by a key: dict.
• Running totals per key: dict.
• Millions of numbers you will do math on: neither. Use an array of raw values. That is the subject of the last lesson in this track.

And one habit: when a loop is slow, look for an in or a .index() on a list inside it. That is the scan hiding in plain sight.

Ship it

Write a script, bench.py, that answers one question with your own numbers: at what size does a set start to beat a list for membership tests?

1. For sizes 10, 100, 1,000 and 10,000, build a list and a set of that many ints.
2. Time 10,000 lookups against each with time.perf_counter().
3. Print one line per size: size, list time, set time, ratio.

You have shipped it when you can point at the line where the set first wins clearly, and explain why in one sentence using the words “scan” and “hash”.