Choosing the right collection

You now have five ways to hold many values: lists, tuples, dicts, sets, and the frozenset and frozendict variants. Picking the wrong one rarely breaks a program, but it can make it clumsy or painfully slow. The trick is to choose by what you will do with the data, not by what it looks like.

Ask what the code needs

Each collection answers a different question. Here they are in action, one at a time.

students = ["Ada", "Ben", "Cy"]
grades = {"Ada": "A", "Ben": "B", "Cy": "A"}

students.append("Dee")
print(students)
print(grades["Ben"])

['Ada', 'Ben', 'Cy', 'Dee']
B

The list is ordered, may repeat and will change. The dict looks a value up by name.

tags = {"python", "tutorial"}
print("python" in tags)

origin = (0, 0)
print(origin[0], origin[1])

True
0 0

The set answers “is it here?”, ignoring repeats. The tuple is a fixed group that can also serve as a dict key.

Real programs nest these freely: a dict of sets, a list of tuples, a dict of lists. This loop builds a dict whose values are sets, which answers “which students got each grade, without repeats?”:

grades = {"Ada": "A", "Ben": "B", "Cy": "A"}

by_grade = {}
for student, grade in grades.items():
    by_grade.setdefault(grade, set()).add(student)

for grade in sorted(by_grade):
    print(grade, sorted(by_grade[grade]))

A ['Ada', 'Cy']
B ['Ben']

What operations cost

The shared fundamentals track introduces Big-O, which describes how the work grows as the data grows. Here is the short version for Python’s built-in collections, in typical cases.

“Constant” means the time barely changes whether the collection holds ten items or ten million. “Scans” means the time grows in step with the length. Dicts and sets get their speed from hashing: the item’s hash value says roughly where to look, so Python does not have to check every entry. That is also why their keys must be hashable.

The practical rule: if you test in repeatedly on a large collection, make it a set (or a dict). If you only test a few times, or the collection is tiny, a list is fine and often simpler.

Measuring it

import time

size = 100_000
as_list = list(range(size))
as_set = set(as_list)
missing = -1

start = time.perf_counter()
for _ in range(200):
    missing in as_list
list_time = time.perf_counter() - start

start = time.perf_counter()
for _ in range(200):
    missing in as_set
set_time = time.perf_counter() - start

print("list is slower:", list_time > set_time)
print("set is at least 100x faster:", list_time / set_time > 100)

list is slower: True
set is at least 100x faster: True

time.perf_counter() is a stopwatch. Each loop repeats the test 200 times and the difference between the two readings is the time taken. We look for a value that is not present, which is the worst case for the list because it must check all 100,000 items before giving up, while the set answers with one hash lookup. The program prints comparisons rather than raw times because times differ from machine to machine. Print the two numbers yourself to see the gap: on typical hardware it is several orders of magnitude. The standard timeit module automates this kind of measurement.

deque, a preview

A list is fast at the end and slow at the front. When you add and remove at both ends, as in a queue of people waiting, the standard library offers collections.deque (pronounced “deck”).

from collections import deque

line = deque(["Ada", "Ben"])
line.append("Cy")
line.appendleft("VIP")
print(line)
print(line.popleft())
print(line.pop())
print(list(line), len(line))

deque(['VIP', 'Ada', 'Ben', 'Cy'])
VIP
Cy
['Ada', 'Ben'] 2

With maxlen, the deque discards from the opposite end when full, which makes a neat “last N items” buffer:

from collections import deque

recent = deque(maxlen=3)
for n in range(1, 6):
    recent.append(n)
print(recent)

deque([3, 4, 5], maxlen=3)

append and pop work on the right, appendleft and popleft on the left, and all four are fast. Only 3, 4 and 5 remain above. The data-structures track in the shared fundamentals covers queues in general, and a later lesson returns to collections in depth. For now, remember the name.

Common pitfalls

• Searching a big list over and over. Repeated x in big_list inside a loop turns a quick job into a slow one. Build a set once, outside the loop.
• Using list.pop(0) as a queue. Every pop shifts all the remaining items. Use a deque.
• Using a set when order matters. Sets do not keep a meaningful order. Use a list, or a dict with its insertion order.
• Using a dict or set when you need duplicates. Both collapse repeats. A list keeps every occurrence.
• Optimising too early. For a few dozen items, any collection is fast enough. Choose for clarity first, and measure before you tune.
• Timing a best case. Searching for an item at the front of a list looks fast. Test absent and late items too.

print("1: list")
print("2: dict")
print("3: set")
print("4: tuple")

1: list
2: dict
3: set
4: tuple

import time

size = 100_000
as_list = list(range(size))
as_set = set(as_list)

start = time.perf_counter()
for _ in range(200):
    -1 in as_list
list_time = time.perf_counter() - start

start = time.perf_counter()
for _ in range(200):
    -1 in as_set
set_time = time.perf_counter() - start

print("list is slower:", list_time > set_time)
print("set is at least 100x faster:", list_time / set_time > 100)

list is slower: True
set is at least 100x faster: True

words = ["listen", "silent", "enlist", "google", "gogole", "cat", "act"]

groups = {}
for word in words:
    key = tuple(sorted(word))
    groups.setdefault(key, []).append(word)

for group in groups.values():
    print(group)

['listen', 'silent', 'enlist']
['google', 'gogole']
['cat', 'act']

Summary

• Choose by operation: list for ordered and changeable, tuple for fixed groups, dict for lookup by key, set for membership and uniqueness, deque for both ends.
• in scans a list but hashes into a set or dict, so repeated membership tests belong in a set.
• Measure rather than guessing, and test the worst case.

This completes the collections module. Next up is functions, where these structures become arguments and return values.