Same Data, Different Shapes

Same data, different shapes

You finished Advanced Python, so you already use data structures every day: list, dict, set, tuple. This course is about what happens underneath, and why the shape you pick can make the same program thousands of times faster.

A data structure is a way of arranging data in memory so that certain operations are fast. That is the whole definition. Every structure in this course is a different answer to one question: which operations do you need to be fast?

Here is the idea in one experiment. We store 10,000 usernames two ways: as a list (a row of items) and as a dict (items filed under keys). Then we look up the same user in both and count how much work each shape does.

Two shapes, two amounts of work

The list has to check names one at a time until it finds the target. The dict computes where the key lives and jumps there, a mechanism the hash tables unit takes apart in detail.

names = [f"user{i}" for i in range(10000)]
target = "user9999"

checks = 0
for name in names:
    checks += 1
    if name == target:
        break
print("list scan checks:", checks)

positions = {name: i for i, name in enumerate(names)}
print("dict lookup checks: 1")
print("position:", positions[target])

Output

list scan checks: 10000
dict lookup checks: 1
position: 9999

Ten thousand checks against one. The data was identical in both cases, the same 10,000 usernames, so nothing about the information explains the gap. Only the arrangement does.

Worth noticing that the target was deliberately the last name in the list. Had it been user0, the list would have won with a single check. The list is not slow, it is slow for this operation, and that distinction is what the whole course is about.

A data structure is best described as a way of arranging data in memory so that certain operations are fast.

The arrangement is the entire point. A list arranges items in a row, which makes reading by position fast and searching slow. A dict arranges items by key, which makes lookup by key fast.

What this rules out is the idea of a best structure. Every arrangement trades some operations for others, so the useful question is never which structure is fastest but which operations your program performs most often. Answer that and the structure usually picks itself.

The same trade, on a smaller table

Two parallel lists hold locker codes and the room each one opens. Finding a room by scanning costs one check per locker passed, while building a dict first makes the lookup direct.

codes = ["A17", "B22", "C31", "D44", "E58", "F63", "G79", "H85"]
rooms = [101, 102, 103, 104, 105, 106, 107, 108]

target = "G79"
checks = 0
room = None
for i in range(len(codes)):
    checks += 1
    if codes[i] == target:
        room = rooms[i]
        break
print("checks:", checks)
print("room:", room)

room_of = dict(zip(codes, rooms))
print("dict answer:", room_of[target])

Output

checks: 7
room: 107
dict answer: 107

The loop runs over indexes rather than values, using for i in range(len(codes)), because the answer lives in rooms[i] and only the position connects the two lists. Counting the check at the top of the body, before the if, means a found match still counts as a check.

dict(zip(codes, rooms)) pairs each code with its room in one expression, after which room_of["G79"] gives 107 with no scan at all.

Both answers are 107, which is the point. Correctness was never in question, only cost, and the cost of the scan grows with the number of lockers while the cost of the lookup does not.