Lessons · Python · memory for speed

Spend memory to save time

Precomputing something once (a running total, a lookup table) can turn a repeated expensive calculation into one cheap read.

Hone is a place to practise programming. This is one of its lessons, written out in full and free to read without an account.

What it is for

Range totals, prefix sums, caches, memoisation: most speed-ups in real systems are this trade. Memory is cheap; a user's time is not.

How to think about it

Ask: am I recomputing the same thing repeatedly? If a loop does the same work for overlapping inputs, compute it once into a table and read from that.

Worked example

sales = [5, 3, 8, 2]

Daily sales. We will ask for many 'total between day i and j' questions.

prefix = [0]

prefix[k] will hold the total of the first k days.

for s in sales: prefix.append(prefix[-1] + s)

[0, 5, 8, 16, 18]. Built once.

print(prefix[3] - prefix[1])

11: days 1 and 2, in one subtraction instead of a loop.

Your turn

Remember results of an expensive function.

cache = {}
def slow(n):
    if n in cache:
        return cache[n]
    result = compute(n)
    cache[] = result
    return result

The trap

A cache that never empties. Fine for a script; in a long-running service it is a memory leak. Bound it or use functools.lru_cache.

Practise memory for speed on HoneA question on it now, a coding challenge where there is one, and it is remembered for review. Free, no email needed.