Optimising a program
The optimisation method (measure, target, change one thing, measure again), the five levers, memoization, Amdahl's law and the trade-off between time and memory.
- 23 cards
- 6 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
- Scenarios
- Understand
A few cards from the deck
Measure before optimising: what is it?
Show the answer
The principle that code is only changed to make it faster after measuring where it loses time, then a new measurement checks that the change helped.
An optimisation often makes code harder to read; it is only justified by a measured gain on the part that weighs.
How many times does the body of
fibrun forfib(6)?
```python
def fib(k):
return k if k < 2 else fib(k - 1) + fib(k - 2)`- 25
- 6
- 13
- 64
Show the answer
25
The same subproblems are recomputed:
fib(2)alone is evaluated 5 times. The number of calls grows like the sequence itself (exponentially). Withlru_cache, each value from 0 to 6 is computed once: 7 runs.The optimisation method: …, target the hot spot, change one thing only, then … again.
Show the answer
The optimisation method: measure, target the hot spot, change one thing only, then measure again.
Changing several things at once makes it impossible to know which helped, or which hurt. The second measurement may conclude that the change must be undone.
Memoization: what is it?
Show the answer
A technique that stores a function's result for each argument already seen, so the same computation is not redone.
It only works for a pure function (same argument, same result) and trades memory for time. In Python:
functools.lru_cache.