Master

Choosing the structure

The same data can live in different structures, and each one changes which operations are cheap. Picking the structure is picking the cost.

What you will see

About 2 min of reading

Quick check

Before this new lesson, one small question about the lesson you just finished. Recall it, do not look it up.

Try It

Pick a structure for the operations you need.

Set membership.

a = [1, 2, 3, 4] s = set(a) print(len(s), 3 in s)

Before you run it, say out loud what it will print. Then open the answer.

What it prints

4 True

Dict lookup.

d = {"a": 1, "b": 2} print(d["b"])

Before you run it, say out loud what it will print. Then open the answer.

What it prints

Heap top.

import heapq h = [5, 2, 8] heapify = heapq.heapify(h) print(h[0])

Before you run it, say out loud what it will print. Then open the answer.

What it prints

Balance a stack.

stack = [] for ch in "(()": if ch == "(": stack.append(ch) else: stack.pop() print(len(stack))

Before you run it, say out loud what it will print. Then open the answer.

What it prints

Put it in order

Before you write anything, put these lines back in the right order. Click a line to move it up one step. This support step is easier than writing code from scratch, and it is here to make the last example stick.

Data Flow

The structure holding data decides which operations are cheap. A set buys membership, a heap buys the next best.

1 list the operations

↓

2 pick the structure

↓

3 check the space cost

↓

4 confirm the classes

Line by line

Read the first example one line at a time. A line that prints shows what appears on screen; the rest set things up quietly.

a = [1, 2, 3, 4] sets nothing on screen

s = set(a) sets nothing on screen

print(len(s), 3 in s) 4 True

Why this works

Structure is cost

Choosing where data lives decides which operations are one step and which are a scan. That choice is a cost decision.

Match the tool to the use

A set for membership, a dict for keys, a sorted list for ranges, a heap for the next best, a stack for nesting.

Examples

List versus set

a = [1, 2, 3, 4]
s = set(a)
print(len(s), 3 in s)

Membership is linear in a list and constant on average in a set. The set costs extra space.

Dict for keys

d = {"a": 1, "b": 2}
print(d["b"])

A dict looks up a key in one step on average. That is the tool for counting and grouping.

Sorted list for ranges

a = [1, 4, 7, 9]
lo, hi = 0, len(a) - 1
while lo < hi:
    mid = (lo + hi) // 2
    if a[mid] < 5:
        lo = mid + 1
    else:
        hi = mid
print(a[lo])

A sorted list answers range questions in log n. That is the structure for nearest and between.

Heap for the next best

import heapq
h = [5, 2, 8]
heapify = heapq.heapify(h)
print(h[0])

A heap keeps the smallest on top for one step. Pushing costs log n, which beats sorting each time.

Stack for nesting

stack = []
for ch in "(()":
    if ch == "(":
        stack.append(ch)
    else:
        stack.pop()
print(len(stack))

A stack matches last in first out. Nesting and undo steps are stack shaped by nature.

Cost follows use

rows = [[1, 2], [3, 4]]
c = 0
for r in rows:
    c += len(r)
print(c)

A list of lists is fine for full scans. The same data in a dict of sets pays more space for faster lookups.

Space buys speed

a = [1, 2, 3]
s = set(a)
print(len(s))

The set stores the items again. That extra space is what makes the lookup one step.

Pick with the plan

n = 1000
print(n, n)

Write the operations you need and their sizes. The structure that makes those cheap is the pick.

Words this lesson uses

Each one is defined here on this site. Open the entry for the full definition and the other words it points at.

← You cannot beat the bound

Previous Lesson

You cannot beat the bound