5 / 8 Typing & Performance

Generator Memory Versus List Memory

Both functions return the same value for the same n:

def sum_of_squares_list(n: int) -> int:
    squares = [x * x for x in range(n)]
    return sum(squares)

def sum_of_squares_gen(n: int) -> int:
    squares = (x * x for x in range(n))
    return sum(squares)

For n = 10_000_000, how do their memory footprints compare, and why?

A

sum_of_squares_list uses less memory than sum_of_squares_gen for large n, because each resumption of a generator allocates a brand-new stack frame that is never freed.

B

sum_of_squares_list uses O(n) additional memory: the list comprehension eagerly computes and holds all n squared values before sum() ever runs. sum_of_squares_gen uses O(1) additional memory: the generator expression produces one value at a time on demand, and sum() consumes and discards each value before the next is produced, so only a small, constant amount of extra state is alive at once.

C

Both use O(n) memory, because sum() has to materialize its argument into a list internally before it can add the values together.

D

sum_of_squares_gen also uses O(n) memory, because the generator has to precompute all n values up front so it knows how many __next__() calls it can support before raising StopIteration.