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

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

Схема для понимания итераторов и генераторов
Схема для понимания итераторов и генераторов

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

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

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

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

В 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]

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

О реализации итератора в книге «банды четырех»
Минимальный интерфейс класса Iterator состоит из операций First, Next, IsDone и CurrentItem. Этот интерфейс можно упростить, объединив операции Next, IsDone и CurrentItem в одну, которая будет переходить к следующему объекту и возвращать его. Если обход завершен, то эта операция вернет специальное значение (например, 0), обозначающее конец итерации. Именно так и реализовано в Python, но вместо специального значения, о конце итерации говорит исключение StopIteration.
  • это контейнер, который может служить источником данных для итератора
  • это любой объект (не обязательно структура данных), способный возвращать итератор4
  • объект, в котором есть метод __iter__
  • итерируемые объекты могут представлять как конечный, так и бесконечный источник данных
  • некоторые итерируемые объекты не являются итераторами, но используют другие объекты как итераторы.
Итерируемый объект, но не итератор
Например, объект list относится к итерируемым, но не является итератором. В нём реализован метод __iter__, но отсутствует метод __next__. Итераторы объектов list относятся к типу listiterator. У объектов list есть определённая длина, а у listiterator нету.

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

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

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

  • генераторы — функции (специальный класс функций), которые внутри используют выражение yield
  • использование yield превращает обычную функцию в генератор5
  • 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))

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

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 — это встроенный модуль в Python, который содержит функции для создания итераторов для эффективных циклов.

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

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

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

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
returnyield
Оператор return возвращает только одно значение.Оператор yield может возвращать серию результатов в виде объекта-генератора.
return выходит из функции, а в случае цикла он закрывает цикл. Это последний оператор, который нужно разместить внутри функции.Не уничтожает локальные переменные функции. Выполнение программы приостанавливается, значение отправляется вызывающей стороне, после чего выполнение программы продолжается с последнего оператора yield.
Логически, функция должна иметь только один return.Внутри функции может быть более одного оператора yield.
Оператор return может выполняться только один раз.Оператор yield может выполняться несколько раз.
return помещается внутри обычной функции Python.Оператор yield преобразует обычную функцию в функцию-генератор.

Подробнее