Two dials
Time and space are separate choices. A faster program can use more memory, and a lean one can spend more steps.
Cache only what repeats
A cache pays off when the same work repeats. If nothing repeats, the cache only costs memory.
Trading time for space
You can spend extra memory to save steps, or save memory to spend steps. The two dials are chosen on purpose, not by accident.
What you will see
13 7
About 2 min of reading
Try It
Trade memory for steps and back.
1
Set membership loop.
a = [3, 1, 4, 1, 5]
s = set(a)
steps = 0
for x in a:
steps += 1
if x in s:
steps += 1
print(steps)
Before you run it, say out loud what it will print. Then open the answer.
What it prints
10
2
Fib 10 with cache.
memo = {}
def fib(n):
if n in memo:
return memo[n]
if n < 2:
return n
v = fib(n - 1) + fib(n - 2)
memo[n] = v
return v
print(fib(10))
Before you run it, say out loud what it will print. Then open the answer.
What it prints
55
3
Fib 10 no cache.
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
print(fib(10))
Before you run it, say out loud what it will print. Then open the answer.
What it prints
55
4
Sum and max one pass.
a = [4, 7, 2]
s = 0
m = a[0]
for x in a:
s += x
if x > m:
m = x
print(s, m)
Before you run it, say out loud what it will print. Then open the answer.
What it prints
13 7
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
Extra memory can buy fewer steps, and a single pass can save memory. The trade is chosen on purpose.
1
find the repeated work
↓
2
spend memory to cache
↓
3
or keep one pass
↓
4
balance time and space
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 = [3, 1, 4, 1, 5]
sets nothing on screen
s = set(a)
sets nothing on screen
steps = 0
sets nothing on screen
for x in a:
sets nothing on screen
steps += 1
sets nothing on screen
if x in s:
sets nothing on screen
steps += 1
sets nothing on screen
print(steps)
10
Why this works
Examples
A set buys a step
a = [3, 1, 4, 1, 5]
s = set(a)
steps = 0
for x in a:
steps += 1
if x in s:
steps += 1
print(steps)Building the set costs n once. Each membership test is then one step.
Without the set
a = [3, 1, 4, 1, 5]
steps = 0
for x in a:
steps += 1
if x in a:
steps += 1
print(steps)Membership in a list scans it, so the loop pays n each turn. That is quadratic.
Cache the answers
memo = {}
def fib(n):
if n in memo:
return memo[n]
if n < 2:
return n
v = fib(n - 1) + fib(n - 2)
memo[n] = v
return v
print(fib(10))The cache turns repeated work into one lookup. Space n buys linear time.
No cache is exponential
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
print(fib(10))Without the cache the same calls repeat. The tree of calls doubles each level.
Sort to search
a = [5, 2, 9, 1]
a.sort()
lo, hi = 0, len(a) - 1
print(a, a[(lo + hi) // 2])Sorting costs n log n once but then each search is log n. Worth it when you search many times.
One pass saves memory
a = [4, 7, 2]
s = 0
m = a[0]
for x in a:
s += x
if x > m:
m = x
print(s, m)Sum and max in one pass keep only two numbers. No extra list is stored.
Space is not free
n = 1000000
a = [0] * n
print(len(a))A cache of a million entries costs a million slots. Sometimes that memory is the real limit.
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.
← Naming a cost class
Previous Lesson
Naming a cost class