Итераторы и генераторы в Python

Список вопросов к Python собеседованию

Итератор

Итератор — это:

• интерфейс, предоставляющий доступ к элементам коллекции (массива или контейнера). Коллекции не должны обязательно существовать в памяти и быть конечными.
• объект, в котором есть два метода: __iter__ (возвращает сам объект итератора) и __next__ (возвращает следующее значение из итератора)

Особенности итератора:

• при запросе каждого следующего значения, итератор знает, как его вычислить
• хранит информацию о текущем состоянии итерируемого объекта, над которым он работает
• почти всегда возвращает себя из метода __iter__, так как выступает итераторами для самого себя (есть исключения)
• итератор не должен иметь и часто не имеет определённой длины. Поэтому зачастую не имеет имплементации __len__
• чтобы подсчитать количество элементов в итераторе, приходится делать это вручную или использовать sum
• когда итератор завершает работу, интерпретатор Python ожидает возбуждения исключения StopIteration (в случаях работы с бесконечными множествами программист должен позаботиться о выходе из цикла самостоятельно)¹
• любой итератор является итерируемым объектом²

В Python за получение итератора отвечает функция iter(). Она отработает на любом объекте, у которого есть метод __iter__ или метод __getitem__ (позволяет получать элементы по индексу). iter() можно вызывать с двумя аргументами. Первый аргумент должен быть вызываемым объектом, а второй — неким ограничителем. Итерирование завершается, когда возбуждается исключение StopIteration (IndexError для метода __getitem__) или возвращается значение ограничителя.

1
2
3
4
5
6

class SimpleList:
  def __init__(self, *items):
    self.items = items

  def __getitem__(self, i):
    return self.items[i]

Итераторы помогают создавать более чистый код, потому что позволяют работать с бесконечными последовательностями без необходимости перераспределения ресурсов для каждой возможной последовательности, что также экономит ресурсы.³

Итерируемый объект

• это контейнер, который может служить источником данных для итератора
• это любой объект (не обязательно структура данных), способный возвращать итератор⁴
• объект, в котором есть метод __iter__
• итерируемые объекты могут представлять как конечный, так и бесконечный источник данных
• некоторые итерируемые объекты не являются итераторами, но используют другие объекты как итераторы.

Примеры итерируемых объектов:

• контейнеры (списки, множества, словари, кортежи и строки)
• открытые файлы
• открытые сокеты

Генератор

Генератор (функция-генератор) - это итератор, определение которого выглядит как определение функции.

• генераторы — функции (специальный класс функций), которые внутри используют выражение yield
• использование yield превращает обычную функцию в генератор⁵
• yield служит разделителем блоков кода, которые исполняет генератор на каждом обращении к нему, то есть на каждой итерации (цикл вовсе не обязателен)
• в результате вызова функции-генератора или вычисления генераторного выражения, получаем объект-генератор типа types.GeneratorType
• генераторы не могут возвращать значения, вместо этого они возвращают итератор, который отдает элементы по одному
• Python автоматизирует запоминание контекста генератора (текущий поток управления, значение локальных переменных и т.д.)
• каждый вызов метода __next__ у объекта генератора возвращает следующее значение
• вызов метода __next__ может быть произведен напрямую при помощи функции next(), или косвенно (например через цикл for)
• метод __iter__ реализуется автоматически

Преимущества генераторов:

• генераторы можно использовать везде, где требуются итераторы
• с помощью генераторов удобно реализовывать дискретные динамические системы
• более эффективно используют память и центральный процессор
• позволяют писать код с меньшим количеством промежуточных переменных и структур данных
• обычно для них требуется меньше строк кода
• их использование облегчает чтение и понимание кода

1
2
3
4
5

def count_generator():
  n = 0
  while True:
  yield n
  n += 1

Генераторные выражения

Генераторное выражение - это еще один синтаксический сахар в Python, простейший способ создать объект с интерфейсом итератора, при этом не загружая всех элементов в память.

• результатами генераторных выражений являются объекты с типом generator
• генераторное выражение использует такой же синтаксис, как list comprehensions, но возвращает итератор, а не список
• выглядит точно так же, как list comprehensions, но используются круглые скобки
• оно полезно в том случае, когда надо работать с большим итерируемым объектом или бесконечным итератором

1

genexpr = (x**2 for x in range(10000))

Выражение yield from

Традиционным подходом для обхода ограниченно-вложенных структур являются вложенные циклы. Тот же подход можно использовать когда генераторная функция должна отдавать значения, порождаемые другим генератором.

1
2
3
4
5
6

def chain(*iterables):
  for it in iterables:
    for i in it:
      yield i
g = chain([1, 2, 3], {'A', 'B', 'C'}, '...')
print(list(g))  # [1, 2, 3, 'A', 'B', 'C', '.', '.', '.']

Но вложенные циклы можно убрать, добавив конструкцию yield from:

1
2
3
4
5
6

def chain(*iterables):
  for it in iterables:
    yield from it

g = chain([1, 2, 3], {'A', 'B', 'C'}, '...')
print(list(g))  # [1, 2, 3, 'A', 'B', 'C', '.', '.', '.']

По сути, выражение yield from <iterable> - это просто сокращенная форма for item in iterable: yield item.

Основная польза yield from в создании прямого канала между внутренним генератором и клиентом внешнего генератора. Но это уже больше тема про сопрограммы (coroutines).

Расширенные методы генератора

С версии Python 2.5 у объекта генератора появилось еще несколько методов:

• send() - позволяет отправить данные в генератор перед вызовом следующего блока кода
• throw() - можно извне заставить его бросить исключение
• close() - можно извне заставить генератор остановиться на следующем обращении к нему

Эти методы в совокупности с выражением yield from превратили генераторы в сопрограммы (coroutine).

Модуль itertools

Itertools — это встроенный модуль в Python, который содержит функции для создания итераторов для эффективных циклов.

В модуле itertools есть набор итераторов, которые упрощают работу с перестановками, комбинациями, декартовыми произведениями и другими комбинаторными структурами.⁶

Рекурсивные генераторы

Как и любая другая функция, генераторы могут быть рекурсивными.

Пример: генератор перестановок элементов в списке

1
2
3
4
5
6
7
8
9

def permutations(items):
  if len(items) == 0:
    yield []
  else:
    pi = items[:]
    for i in range(len(pi)):
      pi[0], pi[i] = pi[i], pi[0]
      for p in permutations(pi[1:]):
        yield [pi[0]] + p

Разница между yield и return

Ппоточные алгоритмы

Подробнее