Choosing the right collection

What you'll learn

• Compare list, tuple, set, and dict on the four questions that matter: order, mutability, uniqueness, and lookup
• Pick a collection from the question your code will ask of it
• Understand why "in a list" is slow and "in a set" is fast, with a measurement
• Recognize the signs that you chose the wrong one

Concept

You now know four collections, and each exists because it answers a different question well. The choice is not about taste. It follows from what the code will do with the data: look items up by position, by key, or by membership; add and remove, or hold a fixed shape; allow duplicates or forbid them. Ask those questions first and the collection picks itself.

The decisive question is usually the lookup. If you will ask "what is at position i" or "what comes next", that is a list. If you will ask "is this here" or "which of these are also in those", that is a set. If you will ask "what is the value for this name", that is a dictionary. A tuple is a list you promise not to change, which makes it usable where lists are not: as a dictionary key, as a set member, and as a return value that says "these three things belong together".

The speed difference is not a detail. x in some_list checks items one by one, so it slows down as the list grows. x in some_set and key in some_dict compute where the item would live and check that one spot, so they stay fast at any size. A loop that does a list membership test on every iteration over another large list is the single most common performance bug in beginner code, and the fix is one line: set(some_list) before the loop.

Signs you chose wrongly: you search a list by a field to find one record (want a dictionary keyed by that field); you call if x not in items: items.append(x) (want a set); you unpack a list into exactly three names every time (want a tuple); you need to change a tuple (want a list, or a new tuple). None of these are errors Python reports. They are smells you learn to notice.

Code

The same data in all four collections, showing what each makes easy and what each refuses.

# four_ways.py
tags_list = ["python", "web", "python", "data"]
tags_tuple = tuple(tags_list)
tags_set = set(tags_list)
tag_counts = {"python": 2, "web": 1, "data": 1}

print(tags_list[0], tags_tuple[-1])
print(sorted(tags_set), len(tags_set))
print(tag_counts["python"])
print("web" in tags_list, "web" in tags_set, "web" in tag_counts)

tags_list.append("ai")
tags_set.add("ai")
tags_set.add("ai")
print(len(tags_list), len(tags_set))
tags_tuple.append("ai")

python data
['data', 'python', 'web'] 3
2
True True True
5 4
Traceback (most recent call last):
  File "four_ways.py", line 15, in <module>
    tags_tuple.append("ai")
    ^^^^^^^^^^^^^^^^^
AttributeError: 'tuple' object has no attribute 'append'

The membership speed gap, measured. Same question, same answer; the set version is dramatically faster and the gap widens with size.

# membership_speed.py
import time

wanted = list(range(0, 200_000, 2))
candidates = list(range(0, 200_000, 3))

start = time.perf_counter()
hits_list = sum(1 for c in candidates[:2000] if c in wanted)
list_ms = (time.perf_counter() - start) * 1000

wanted_set = set(wanted)
start = time.perf_counter()
hits_set = sum(1 for c in candidates[:2000] if c in wanted_set)
set_ms = (time.perf_counter() - start) * 1000

print(hits_list == hits_set, hits_set)
print("set at least 50x faster:", list_ms / max(set_ms, 1e-9) > 50)

True 1000
set at least 50x faster: True

Three smells and their fixes, side by side. Each pair does the same job; the second line of each is the version you want to write.

# smells.py
users = [{"id": 7, "name": "ada"}, {"id": 9, "name": "linus"}]

# smell: scanning a list for a field      fix: a dict keyed by that field
found = next(u for u in users if u["id"] == 9)
by_id = {u["id"]: u for u in users}
print(found["name"], by_id[9]["name"])

# smell: "if not in, append" for uniqueness   fix: a set
seen_list = []
for tag in ["a", "b", "a"]:
    if tag not in seen_list:
        seen_list.append(tag)
seen_set = set(["a", "b", "a"])
print(seen_list, sorted(seen_set))

# smell: a list that is always three fixed things   fix: a tuple
point_list = [3, 4, 5]
point = (3, 4, 5)
x, y, z = point
print(point_list[0], x)

linus linus
['a', 'b'] ['a', 'b']
3 3

Try it yourself

Create choose.py and, for each of these scenarios, pick a collection, build a tiny example, and print one operation that shows why you chose it: the order of songs in a playlist; the set of words a spell-checker knows; a mapping from country code to country name; the latitude and longitude of a city; the unique visitors to a site today. Add a one-line comment above each explaining the choice.

Common mistakes

• Defaulting to a list for everything. It works until the data grows or you need lookups by name, and then it is slow and unclear.
• Membership tests on a list inside a loop. Convert to a set once, before the loop.
• Using a dictionary when you only need uniqueness. If the values are all True or None, you wanted a set.

What's next

• Choose by lookup: position means list, key means dict, membership or uniqueness means set, fixed record means tuple.
• Membership in a set or dict stays fast as data grows; in a list it does not, and converting once fixes it.
• Watch for the smells: scanning a list by field, "if not in then append", and unpacking a list into fixed names.

You can pick the right container on sight. Next you will learn to build collections in a single readable expression: comprehensions.