Python: Generator

School CS110
, , ,
1

One of the most efficient and memory-friendly ways to handle large datasets or infinite sequences is by using generators.
Generators are a crucial concept in Python that allows you to create iterable sequences without loading the entire dataset into memory at once. Generators can be used to implement a variety of patterns, including lazy evaluation, iterators, and coroutines.

In this blog post, we’ll explore the low-level details of Python generators, how they work, and why they are so efficient.

Generators, in Python, are a type of iterable, like lists or tuples, but they are different in the way they generate and retrieve values. Unlike traditional sequences, which store all elements in memory, generators produce values on the fly, one at a time. This lazy evaluation of data makes generators particularly useful when dealing with large datasets or when memory resources are limited.

Generator Internals

Under the hood, generators work by pausing execution each time yield is encountered. Local variables and execution state are saved.

When next() is called, execution resumes where it left off until the next yield. This allows the function to produce a new value whenever resumed until it becomes empty.

generators are functions that use the yield keyword to produce a value and temporarily pause their execution, preserving their state. When you iterate over a generator, it resumes execution from where it left off, producing the next value when requested.

Here is a simple example of a Python generator:

def generate_numbers():
  """Generates a sequence of numbers from 1 to 10."""
  for i in range(1, 11):
    yield i

# Create a generator object.
generator = generate_numbers()

# Get the next value from the generator.
print(next(generator))  # 1

# Get the next value from the generator.
print(next(generator))  # 2

# Get the last value from the generator.
print(next(generator))  # 10

# Trying to get the next value from the generator raises a StopIteration exception.
try:
    print(next(generator))
except StopIteration:
    print("Generator is finished.")

To understand the low-level details of generators, let’s break down how the generate_numbers() function works:

  1. When you call generate_numbers(), Python doesn’t execute the function but returns a generator object. The function is in a suspended state at this point.
  2. When you call next method, Python starts executing the function until it reaches the first yield, it then yields the first number in the sequence (1), suspends execution, preserving the function’s state, and returns to the caller.
  3. The caller then calls the generator again (next), which restores its state from the stack frame and continues execution. The generator then yields the next number in the sequence (2) and returns to the caller.
  4. This process continues until the generator yields the last number in the sequence (10). At that point, the generator raises a StopIteration exception to indicate that it is finished.

Another example

def simple_generator():
  yield 1
  yield 2
  yield 3

gen = simple_generator()

for value in gen:
  print(value)

To understand the low-level details of generators, let’s break down how the simple_generator function works:

  1. When you call simple_generator(), Python doesn’t execute the function but returns a generator object. The function is in a suspended state at this point.
  2. When you iterate over the generator using a loop (e.g., for value in gen), Python starts executing the function until it encounters the first yield statement (yield 1). It produces the value 1 and suspends execution, preserving the function’s state.
  3. The value 1 is returned to the loop, and the loop continues.
  4. When the loop requests the next value, Python resumes execution of the generator function from where it left off. It proceeds to the next yield statement (yield 2) and produces the value 2. Again, it suspends execution.
  5. This process repeats until there are no more yield statements to execute, at which point the generator raises a StopIteration exception, signaling the end of iteration.

Benefits of Using Python Generators

Python generators offer a number of benefits, including:

  • Lazy evaluation: Generators can be used to implement lazy evaluation, which means that values are only calculated when they are needed. This can be useful for large datasets or for algorithms that require multiple passes over the data.
  • Iterators: Generators can be used to implement iterators, which are objects that can be used to iterate over a sequence of values. Iterators are efficient and easy to use.
  • Coroutines: Generators can be used to implement coroutines, which are functions that can be suspended and resumed. Coroutines are useful for implementing asynchronous programming patterns.

Examples

Fibonacci numbers

def generate_fibonacci_numbers():
  """Generates a sequence of Fibonacci numbers."""
  a, b = 0, 1
  while True:
    yield a
    a, b = b, a + b


# Create a generator object.
generator = generate_fibonacci_numbers()

# Get the first few Fibonacci numbers.
print(next(generator)) # 0
print(next(generator)) # 1
print(next(generator)) # 1
print(next(generator)) # 2
print(next(generator)) # 3
print(next(generator)) # 5

Prime numbers

def generate_prime_numbers():
  """Generates a sequence of prime numbers."""
  primes = []
  for n in range(2, 1000):
    if all(n % p != 0 for p in primes):
      primes.append(n)
      yield n


# Create a generator object.
generator = generate_prime_numbers()

# Get the first few prime numbers.
print(next(generator)) # 2
print(next(generator)) # 3
print(next(generator)) # 5
print(next(generator)) # 7
print(next(generator)) # 11
print(next(generator)) # 13

Pipeline for squared numbers

def generate_numbers():
  """Generates a sequence of numbers from 1 to 10."""
  for i in range(1, 11):
    yield i

def square_numbers(generator):
  """Squares the numbers in the generator."""
  for number in generator:
    yield number * number

# Create a generator object for generating numbers.
generator = generate_numbers()

# Create a generator object for squaring the numbers.
squared_numbers = square_numbers(generator)

# Print the squared numbers.
for number in squared_numbers:
  print(number)

Disadvantages of Generator

  1. Single Iteration: Generators are designed for a single iteration. Once you’ve iterated through a generator, you can’t easily restart the iteration. If you need to iterate through the same sequence multiple times, you may need to recreate the generator, which can be less efficient in some cases.
  2. Not Suitable for All Data Types: Generators work well for sequences of data and lazy evaluation. However, they may not be the best choice for data structures where random access to elements is required, such as lists or arrays. Generators do not support indexing, so you cannot access elements by their position in the sequence.
  3. Complexity: Generators can sometimes introduce complexity, especially when you need to maintain state or context across multiple iterations. Managing state within generator functions can be error-prone and challenging to debug.
  4. Memory Overhead: Although generators are memory-efficient for large sequences, they may introduce some memory overhead due to the generator object itself and any additional state information needed to resume execution.
  5. Performance Trade-offs: In some cases, generators might be slower than using traditional data structures like lists or tuples, particularly for small datasets. The overhead of suspending and resuming execution can impact performance, although this difference is often negligible for most applications.
  6. Limited Compatibility: While generators are widely supported in Python, not all libraries or codebases may be designed to work seamlessly with generators. You may encounter compatibility issues when trying to integrate generators into existing code.