Space complexity measures how an algorithm’s memory or disk-storage use grows as its inputs grow. It offers a practical worst-case intuition rather than an exact quantitative measurement. section 4.1 section 4.1.3
Use space complexity to notice avoidable storage and choose a smaller-memory approach:
- Reading every row of a large file into a list requires O(n) additional memory. section 4.1.3
- Reading one line at a time keeps usage near the size of the largest line, reducing the approach to O(1) space. section 4.1.3
- Lists store all their contents together and therefore use O(n) space; generators produce values one at a time. section 4.2.3
color_counts = {}
with open('all-favorite-colors.txt') as favorite_colors_file:
favorite_colors = favorite_colors_file.read().splitlines() #1
for color in favorite_colors:
if color in color_counts:
color_counts[color] += 1
else:
color_counts[color] = 1
This listing shows the memory-heavy approach: split the entire file into a list before counting colors. section 4.1.3
color_counts = {}
with open('all-favorite-colors.txt') as favorite_colors_file:
for color in favorite_colors_file: #1
color = color.strip() #2
if color in color_counts:
color_counts[color] += 1
else:
color_counts[color] = 1
This listing shows the space-conscious alternative: process and discard each color line as it arrives. section 4.1.3
Generating values on demand
A generator using yield pauses after producing each value, avoiding storage of all produced values at once. The same idea explains why range can represent very large sequences efficiently. section 4.2.3
