Space complexity in Python

Problem

The export that eats the memory

Every night a service exports the shop's logs for the day to an archive. So that it can carry on from where it stopped after a crash, it writes a checkpoint after every line. Except that the checkpoint is a copy of the whole file so far:

def export_logs(logs):
    file = []
    checkpoints = []
    for line in logs:
        file.append(line)
        checkpoints.append(file.copy())
    return sum(len(saved) for saved in checkpoints)

How many places do the copies hold? The program counts them:

for n in [5, 1000]:
    logs = [f"line {i}" for i in range(1, n + 1)]
    print(f"{n} lines: {export_logs(logs)} places")

5 lines: 15 places
1000 lines: 500500 places

For 1000 lines it is 500 500 places. The logs of one day are 100 000 lines, and that is 5 000 050 000 places. Every place holds a reference of 4 to 8 bytes: between 20 and 40 GB just for the copies. In the test with 1000 lines everything passes, and at night the export stops with MemoryError.

The idea

Memory is a cost too

So far you counted operations. Memory is counted the same way: how many places the algorithm sets aside itself, apart from the input it receives. This is the space complexity of the algorithm. It is written with Big-O too:

O(1): a few variables, however big the input;
O(n): a copy of the input, a helper list, a set with all the elements;
O(n²): a copy of the copy at every step, as in the export.

The input does not count, because it exists without the algorithm. Neither does the result the task asks for: the file with n lines is the export's job. What counts are the copies it makes along the way.

See it

The copies stay

file = []
checkpoint = 0
for line in logs:
    file.append(line)
    checkpoint = len(file)

Step by step, in words

file is the file the export writes; logs has 4 lines. checkpoints keeps where to resume after a crash.
Line 1 goes into the file. The checkpoint is a copy of the whole file: 1 place.
Line 2. The new checkpoint copies both lines, and the old one stays in the list: 1 + 2 = 3 places.
After 4 lines memory holds 1 + 2 + 3 + 4 = 10 places. After n lines it is n(n + 1)/2: five billion for 100 000 lines.
To resume after a crash you only need how far you got. The copies go; one number stays.
Every line changes the number: checkpoint = 4. The extra memory is 1 place, however many lines there are.

Every copy is a new list in memory, and nobody deletes the old ones: the list checkpoints keeps them. That is why the places grow as 1 + 2 + 3 + … + n. To carry on after a crash, the export only needs how far it got:

def export_logs(logs):
    file = []
    checkpoint = 0
    for line in logs:
        file.append(line)
        checkpoint = len(file)
    return checkpoint

for n in [5, 1000]:
    logs = [f"line {i}" for i in range(1, n + 1)]
    print(f"{n} lines, checkpoint: {export_logs(logs)}")

5 lines, checkpoint: 5
1000 lines, checkpoint: 1000

The file is the same, and the extra memory is one number: O(1) instead of O(n²).

Try it

Predict the output

The export with the copies gets 6 lines. How many places do the checkpoints hold?

def export_logs(logs):
    file = []
    checkpoints = []
    for line in logs:
        file.append(line)
        checkpoints.append(file.copy())
    return sum(len(saved) for saved in checkpoints)


for n in [6]:
    logs = [f"line {i}" for i in range(1, n + 1)]
    print(f"{n} lines: {export_logs(logs)} places")

Answer

6 lines: 21 places

6 lines: 6 places

6 lines: 36 places

See it

A copy or in place

The admin wants the newest log lines first. There are two ways. One makes a new list in reverse order, and the other swaps the elements in the list itself: the first with the last, the second with the one before last, until the two ends meet.

def newest_first(logs):
    result = []
    for i in range(len(logs) - 1, -1, -1):
        result.append(logs[i])
    return result


def reverse_in_place(logs):
    left = 0
    right = len(logs) - 1
    while left < right:
        logs[left], logs[right] = logs[right], logs[left]
        left += 1
        right -= 1

logs = ["09:00 login", "09:05 cart", "09:07 payment"]
newest = newest_first(logs)
print("Copy:     " + ", ".join(newest))
print("Original: " + ", ".join(logs))
reverse_in_place(logs)
print("In place: " + ", ".join(logs))

Copy:     09:07 payment, 09:05 cart, 09:00 login
Original: 09:00 login, 09:05 cart, 09:07 payment
In place: 09:07 payment, 09:05 cart, 09:00 login

The copy needs n new places, but the original stays as it was. The change in place needs one place for the swap, but the old order is gone. Which is better depends on whether someone else still reads the original.

More precisely, if you are curious

The built-in functions make the same choice, and the name does not always tell you:

logs = ["09:00 login", "09:05 cart", "09:07 payment"]
copy = logs[::-1]
logs.reverse()
print("In place: " + ", ".join(logs))
print("Copy:     " + ", ".join(copy))

In place: 09:07 payment, 09:05 cart, 09:00 login
Copy:     09:07 payment, 09:05 cart, 09:00 login

logs.reverse() reverses in place, and logs[::-1] makes a copy. Every slice logs[a:b] is a copy: logs[1:] in a recursion copies almost the whole list at every call. reversed(logs) does not copy, it only reads from the back.

The copy is shallow: the new list keeps references to the same texts, not new texts. That is why the places are counted one per element.

Try it

Fill in

Finish the swap of the two ends:

logs[left], logs[right] = logs[right],

See it

Recursion holds memory too

A list is not the only thing that takes room. Every call of a function keeps its parameters and local variables on the call stack until it returns. Here is counting the errors in the log with recursion and with a loop:

def errors_from(logs, i):
    if i == len(logs):
        return 0
    here = 1 if logs[i].startswith("ERROR") else 0
    return here + errors_from(logs, i + 1)

def errors(logs):
    count = 0
    for line in logs:
        if line.startswith("ERROR"):
            count += 1
    return count

small = make_logs(500)
big = make_logs(1_000_000)
print(f"500 lines: {errors_from(small, 0)} errors")
try:
    print(f"1000000 lines: {errors_from(big, 0)} errors")
except RecursionError:
    print("1000000 lines: RecursionError")
print(f"With a loop: {errors(big)} errors")

500 lines: 5 errors
1000000 lines: RecursionError
With a loop: 10000 errors

The recursion makes not a single list, but for n lines there are n unfinished calls on the stack: O(n) memory. The stack is small, and a million calls do not fit. The loop has one variable count: O(1).

Python stops the recursion already at about 1000 calls (sys.getrecursionlimit()). This is a guard: the real stack would be enough for more, but not for a million.

More precisely, if you are curious

How deep the recursion can go depends on the size of the stack and the size of one frame. The limit is raised with sys.setrecursionlimit, but then the real stack of the process may run out and Python crashes without a message.

When the recursive call is the last action of the function (with no here + after it), some languages turn it into a loop (a tail call). Java, C#, Python and Node do not, so in them depth always costs memory.

The idea

Time against memory

The shop checks whether two orders of the day have the same number. The first way compares every pair. The second remembers the numbers it has seen in a set:

def has_duplicate_loops(orders):
    for i in range(len(orders)):
        for j in range(i + 1, len(orders)):
            if orders[i] == orders[j]:
                return True
    return False

def has_duplicate_set(orders):
    seen = set()
    for order in orders:
        if order in seen:
            return True
        seen.add(order)
    return False

today = [100512, 100513, 100514, 100512]
print(has_duplicate_loops(today), has_duplicate_set(today))

True True

Both give the same answer, but they pay differently:

the nested loops: O(1) memory and O(n²) time;
the set: O(n) memory (up to n numbers) and O(n) time.

This is a common trade: memory for time. How many comparisons and checks the two make when there is no repeat (the worst case):

def comparisons_loops(orders):
    count = 0
    for i in range(len(orders)):
        for j in range(i + 1, len(orders)):
            count += 1
            if orders[i] == orders[j]:
                return count
    return count


def checks_set(orders):
    seen = set()
    count = 0
    for order in orders:
        count += 1
        if order in seen:
            return count
        seen.add(order)
    return count

for n in [10, 1000]:
    orders = [100000 + i for i in range(n)]
    print(f"{n} orders: {comparisons_loops(orders)} comparisons with loops, {checks_set(orders)} checks with a set")

10 orders: 45 comparisons with loops, 10 checks with a set
1000 orders: 499500 comparisons with loops, 1000 checks with a set

Nested loops, no memory O(n²)
A set of seen numbers, n places O(n)

Algorithm	n = 10	n = 1,000	n = 100,000
Nested loops, no memory	45	499,500	≈ 4,995,000,000
A set of seen numbers, n places	10	1,000	100,000

The code runs in your browser, in JavaScript. The number of operations is the same in every language, because the algorithm is the same. The time depends on the machine, so it is only for comparison. “≈” is an estimate from the curve: we do not run an n that big, so the page does not freeze.

For 100 000 orders the loops make almost 5 billion comparisons, and the set makes 100 000 checks and keeps 100 000 numbers. When the memory is there, the set wins. When it is not (a small device, a huge input), you either sort the numbers (then the repeats are next to each other) or read in parts.

More precisely, if you are curious

We count one check in the set as one operation. It is O(1) on average, because the set is a hash table: the number becomes a hash, and the hash says which bucket to look in. One place in a set costs more than one number in an array: in a set about 30–60 bytes (an entry in the table and the int object). So "O(n) memory" for 10 million orders is hundreds of MB, not 40.

Try it

Find the bug

A colleague rewrote the check with a set, but it never finds a repeat:

def has_duplicate_set(orders):
    for order in orders:
        seen = set()
        if order in seen:
            return True
        seen.add(order)
    return False

today = [100512, 100513, 100514, 100512]
print(has_duplicate_set(today))

False

Number 100512 is there twice, and the answer is "no". Which line is the bug on?

Pick the line with the bug.

Exercise

The last three lines

Solve the task in your editor.

The last lines. When something breaks, the admin wants only the last k lines of the log. Write last_lines(logs, k), which returns them while keeping at most k lines in memory, not the whole log: O(k) memory. Run it with 1000 lines ("line 1" … "line 1000") and k = 3.

line 998
line 999
line 1000

One possible solution

Keep a queue: every new line goes in at the back, and when there are more than k lines, the oldest goes out at the front.

from collections import deque


def last_lines(logs, k):
    recent = deque(maxlen=k)
    for line in logs:
        recent.append(line)
    return list(recent)

deque(maxlen=k) throws out the oldest line by itself when it is full.

More tasks

The average length without a copy. Compute the average length of a line in the log with O(1) extra memory: without a new list of lengths.
Errors by hour. Count the errors for every hour (09, 10…). How much memory does your solution need if there are 24 hours and a million lines?
The repeated numbers. Return not only "yes or no", but all repeated numbers. How much memory does the solution with a set need, and can you do without it?

Test

Check yourself

1. A function makes a new list with n log lines in reverse order. How much extra memory does it need?O(1)O(n)O(n²)

2. The export keeps a copy of the whole file so far after every line. How many places does memory hold for n lines?n(n + 1)/2, that is O(n²)n2n

3. A recursive function with no list at all calls itself 1 000 000 times, one call inside another. How much memory does it need?O(n): every call stays on the stack until it returnsO(1), because there are no listsNone, memory is only for objects

4. You look for a repeated number in 10 000 000 orders on a server with a few GB of free memory. Which do you choose?It makes no differenceThe set: O(n) memory, but O(n) time instead of O(n²)The nested loops, because they need no memory

5. What does not count in the extra memory of a function?The stack of its recursionA copy of the input the function makesThe input the function receives

Space complexity

Cookies