C++ и Python

Язык Python

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

Итераторы

В предыдущих разделах мы встречали различные итерируемые объекты. Такие объекты можно использовать в цикле for, к ним можно применять оператор in. Разберемся в механизме итерирования. Классы стандартных контейнеров имеют метод __iter__, возвращающий итератор:

l = [1, 2, 3]
s = set(1, 2, 3)
d = {k: v for v, k in enumerate(['a', 'b', 'c'])}

all(map(lambda x: hasattr(x, '__iter__'), [l, s, d]))  # True
type(l.__iter__())  # <class 'list_iterator'>
type(iter(l))       # <class 'list_iterator'>

itl = iter(l)
for x in itl:
    print(x, end=' ')
# 1 2 3

for x in itl:
    print(x, end=' ')
# этот цикл не запустится, поскольку итератор позволяет
# перебрать объекты только один раз

its = iter(s)
type(its)  # <class 'set_iterator'>
# для получения следующего значения можно использовать функцию next.
# Функция next вызывается при переборе значений в цикле for
next(its)  # 1
next(its)  # 2
next(its)  # 3

Вызов метода __iter__ в данном случае аналогичен использованию функции iter. В обоих случаях мы получаем итератор. В итераторе должен быть определен метод __next__, который возвращает следующее значение. Функция next вызывает метод __next__.

Функция iter также вернет итератор, если вместо метода __iter__ реализован метод __getitem__, позволяющий доступаться к элементам контейнера по индексу.

Чтобы сделать тип итерируемым, достаточно реализовать метод __iter__ или метод __getitem__. Чтобы создать тип-итератор, необходимо определить в нем метод __next__ и метод __iter__. Последний должен возвращать сам объект (self). Таким образом, итераторы сами являются итерируемыми объектами.

Генераторы

Другой встречавшийся нам итерируемый объект — результат вызова функции range:

import sys

for x in range(5):
    print(x, end=' ')
# 1 2 3 4 5

rng = range(10**6)
type(rng)  # <class 'range'>
sys.getsizeof(rng)  # 48 — размер объекта в байтах

l = list(rng)
sys.getsizeof(l)  # 9000120

Функция range возвращает объект типа range, который занимает фиксированный объем памяти. Эффективное использование памяти достигается благодаря тому, что каждое значение вычисляется в реальном времени, позволяя избавиться от необходимости хранить все значения в памяти. Такое поведение можно реализовать с помощью генераторов. Напишем свою версию range:

def my_range(start, stop=None, step=None):
    if step is None:
        step = 1
    if stop is None:
        start, stop = 0, start
    v = start
    while v < stop:
        yield v
        v += step

myrng = my_range(5)
type(myrng)           # <class 'generator'>
sys.getsizeof(myrng)  # 128

for x in myrng:
    print(x, end=' ')
# 0 1 2 3 4

Размер нашего генератора больше, чем объекта range, но он также не зависит от значений аргументов функции my_range. Ключевым элементом функции-генератора my_range является строка

yield v

При достижении этой строки генератор запоминает свое состояние, прерывает работу до следующего вызова метода __next__ и возвращает текущее значение переменной v.

Создадим более интересный генератор, который вычисляет последовательность Рекамана:

def rekaman(stop):
    n = 0
    prev = 0
    visited = set()
    while n < stop:
        if n == 0:
            yield 0
            prev = 0
        elif prev - n > 0 and prev - n not in visited:
            yield prev - n
            prev = prev - n
        else:
            yield prev + n
            prev = prev + n
        n += 1
        visited.add(prev)

for r in rekaman(100):
    print(r, end=' ')
# 0 1 3 6 2 7 13 20 12 21 11 22 10 23 9 24 8 25 43 62 42 63 41 18 42
# 17 43 16 44 15 45 14 46 79 113 78 114 77 39 78 38 79 37 80 36 81 35
# 82 34 83 33 84 32 85 31 86 30 87 29 88 28 89 27 90 26 91 157 224
# 156 225 155 226 154 227 153 228 152 75 153 74 154 73 155 72 156 71
# 157 70 158 69 159 68 160 67 161 66 162 65 163 64

Функции-генераторы являются удобным и гибким инструментом языка python. Иметь этот инструмент в арсенале очень полезно.

Альтернативный способ создания генераторов предоставляют генераторные выражения:

l1 = [x**2 for x in range(100)]  # списковое включение
g1 = (x**2 for x in range(100))  # генераторное выражение

type(l1)  # <class 'list'>
type(g1)  # <class 'generator'>

Генераторные выражения имеют синтаксис близкий к списковому включению. Отличие состоит только в использовании круглых скобок. В частности, в генераторных выражениях можно использовать условный оператор:

g = (x for x in range(20) if x % 3)
for val in g:
    print(val, end=' ')
# 1 2 4 5 7 8 10 11 13 14 16 17 19

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

Функция map также возвращает итератор (генератор):

l1 = [x**2 for x in range(100)]
g1 = (x**2 for x in range(100))
m1 = map(lambda x: x**2, range(100))

type(l1)  # <class 'list'>
type(g1)  # <class 'generator'>
type(m1)  # <class 'map'>

sys.getsizeof(l1)  # 920
sys.getsizeof(g1)  # 128
sys.getsizeof(m1)  # 64

Если преобразованную коллекцию необходимо обходить несколько раз или надо сохранить все её элементы, то генератор можно преобразовать в список:

m2 = list(map(lambda x: x**2, range(100)))

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

from typing import NamedTuple

class FourVector(NamedTuple):
    t: float
    r: list

fv = FourVector(1, [0.3, 0.4, 0.0])
for x in fv:
    print(x, end=' ')
# 1 [0.3, 0.4, 0.0]

Объекты класса FourVector является итерируемыми, поскольку класс наследуется от типа NamedTuple. Давайте изменим правило итерирования:

import itertools

class FourVector(NamedTuple):
    t: float
    r: list

    def __iter__(self):
        if isinstance(self.r, list):
            return itertools.chain([self.t], self.r)
        return (x for x in [self.t, self.r])

fv1 = FourVector(1, [0.3, 0.4, 0.0])
fv2 = FourVector(1, 0.5)

for x in fv1:
    print(x, end=' ')
# 1 0.3 0.4 0.0

for x in fv2:
    print(x, end=' ')
# 1 0.5

Мы не могли использовать спиское включение вместо генераторного выражения в методе __iter__, поскольку, в отличие от типа generator, тип list не является итератором. Функция itertools.chain принимает несколько итераторов или итерируемых коллекций и создаёт генератор, который последовательно проходит по всем их элементам.

Резюме

Итерируемый объект должен иметь реализацию хотя бы одного из методов __iter__ и __getitem__. Объект-итератор должен иметь реализацию метода __next__.

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

Источники