# Глава 23. Итераторы и генераторы
> Работа, ты меня не бойся, я тебя не трону!
Народная пословица
Итераторы позволяют поштучно перебирать последовательности объектов. Генераторы — это итераторы, реализующие стратегию ленивых вычислений. Они помогают сэкономить оперативную память при переборе больших (и даже бесконечных!) последовательностей. Разберемся, как их применять на практике.
## Итераторы и итерабельные объекты
Итерабельным объектом в питоне называется объект, который способен возвращать элементы по одному. Из него можно получить итератор — специальный объект для перемещения по элементам итерабельного объекта.
Два классических примера использования итераторов и итерабельных объектов — цикл `for` и выражение `in`:
```python {.example_for_playground}
numbers = [1, 2, 3]
for n in numbers:
print(n)
if 2 in numbers:
print("found item")
```
```
1
2
3
found item
```
Списки являются итерабельными объектами. Чтобы пройтись по ним, под капотом цикла `for` создается итератор. Он и перебирает элементы, пока они не кончатся:
```python
def for_loop(iterable):
iterator = iterable.__iter__()
while True:
try:
item = iterator.__next__()
except StopIteration:
break
else:
print(item)
```
На вход цикла `for` должен поступать итерабельный объект. То есть такой объект, у которого есть dunder-метод `__iter__()`, возвращающий итератор.
Первым делом для работы с итерабельным объектом необходимо получить итератор на первый элемент. Благодаря ему мы сможем забирать элементы коллекции и двигаться по ней вперед.
При перемещении по коллекции у итератора вызывается dunder-метод `__next__()`, который возвращает следующий элемент. Если следующего элемента нет, он бросает исключение `StopIteration`.
Генерация этого исключения не считается ошибочной ситуацией: `StopIteration` выступает в качестве маркера окончания прохода по коллекции для вызывающего кода. Благодаря ему появляется возможность распознать, что больше не нужно итерироваться (например, в цикле `for`).
Итератор — объект, который позволяет поэлементно обходить коллекции: списки, кортежи, словари и так далее. Он отвечает за:
- возвращение данных по одному элементу из контейнера или потока,
- отслеживание текущего и пройденных элементов.
Объект считается итератором, если он определяет два dunder-метода (следует протоколу итератора):
- `__iter__()` — возвращает инстанс итератора. Чтобы не вызывать этот dunder-метод напрямую, в языке реализована встроенная функция-обертка `iter()`.
- `__next__()` — возвращается элемент, на который указывает итератор. Метод должен быть заточен под тип контейнера. При окончании итерации `__next__()` должен бросить исключение `StopIteration`. Для этого метода существует обертка в виде встроенной функции `next()`.
В промышленном коде почти никогда не требуется напрямую работать с dunder-методами итератора: они неявно вызываются в циклах.
Рассмотрим пример класса, следующего протоколу итератора:
```python
class SeqIterator:
def __init__(self, sequence):
self._sequence = sequence
self._index = 0
def __iter__(self):
return self
def __next__(self):
if self._index < len(self._sequence):
item = self._sequence[self._index]
self._index += 1
return item
raise StopIteration
```
Если объект является итератором, то он автоматически считается итерабельным объектом. Обратное в общем случае неверно. Например, итератор `range()` — это итерабельный объект. А итерабельный объект типа `tuple` итератором точно не является.
По мере перебора итератор истощается, и для повторного прохода по элементам его нужно пересоздавать. Зато он занимает очень мало места в памяти. Итерабельный объект же никогда не истощается, но занимает в памяти столько места, чтобы уместить в нем все свои элементы.
Возьмем нашу реализацию итератора `SeqIterator` из примера выше и создадим с ее помощью итерабельный класс `SeqIterable`.
```python {.example_for_playground}
class SeqIterable:
def __init__(self, sequence):
self._sequence = sequence
def __iter__(self):
return SeqIterator(self._sequence)
for item in SeqIterable([1, 2, 3]):
print(item)
```
```
1
2
3
```
Что выведет этот код? {.task_text}
В случае исключения напишите `error`. {.task_text}
```python {.example_for_playground}
vals = iter([1, 2, 3])
a = 2 in vals
b = 2 in vals
print(a is b)
```
```consoleoutput {.task_source #python_chapter_0230_task_0010}
```
Встроенная функция `iter()` вызвала dunder-метод `__iter__()` у списка. В переменную `vals` сохранился итератор. Затем выражение `in` переместило итератор по коллекции до элемента 2. Многократный проход по одним и тем же элементам через один и тот же итератор невозможен: для этого итератор нужно пересоздавать. Поэтому повторный вызов `in` вернул `False`. {.task_hint}
```python {.task_answer}
False
```
Реализуйте класс-итератор `KVIterator`: обертку для итерирования по ключам и значениям словаря. {.task_text}
```python {.task_source #python_chapter_0230_task_0020}
class KVIterator:
def __init__(self, d):
...
d = {"a": 1, "b": 2}
for k, v in KVIterator(d):
print(f"{k}={v}")
```
В инициализатор `KVIterator` должен передаваться словарь. Назовем его `d`. Тогда внутри инициализатора можно завести итератор: `self._i = iter(d.items())`. {.task_hint}
```python {.task_answer}
class KVIterator:
def __init__(self, d):
self._i = iter(d.items())
def __iter__(self):
return self._i
def __next__(self):
return next(self._i)
```
## Генераторы {#block-generators}
Генераторы — это итераторы специального вида. С их помощью реализуется стратегия [ленивых вычислений](https://en.wikipedia.org/wiki/Lazy_evaluation).
Вычисления считаются ленивыми, если они откладываются ровно до того момента, пока не потребуется их результат. Это и происходит в процессе итерирования по генератору. В названии генераторов заложена их суть: данные в генераторе не хранятся, а рассчитываются, то есть «генерируются» в момент обращения.
Для того чтобы функция считалась генератором, в ней должно присутствовать ключевое слово `yield`. Главное отличие генераторов от обычных функций в том, что для возврата значения вместо `return` используется оператор `yield`. Он не завершает выполнение функции, а только приостанавливает (yield означает «уступать»). Таким образом запоминается состояние, в котором функция была приостановлена.
Под состоянием понимается набор локальных переменных, адрес для возобновления работы генератора и регистры общего назначения. Все это хранится в объекте генератора. При последующем обращении к генератору его состояние восстанавливается и вычисления возобновляются с того места, где были прерваны. При завершении работы генератора неявно вызывается оператор `return`.
Рассмотрим пример генератора:
```python {.example_for_playground}
def sequence_generator(sequence):
for item in sequence:
yield item
for number in sequence_generator([1, 2, 3]):
print(number)
```
```
1
2
3
```
При вызове функции `sequence_generator()` наружу возвращается генератор. Выполнение функции при этом еще не началось! Чтобы его инициировать, нужно вызвать метод `__next__()` генератора. Внутри цикла `for` этот вызов происходит неявно.
C помощью конструкции `yield from` удобно создавать генераторы-посредники. Рассмотрим редуцированный пример:
```python {.example_for_playground}
def f(items):
for item in items:
yield item
g = f('abcd')
print(list(g))
```
```
['a', 'b', 'c', 'd']
```
В генератор `f()` передан итерабельный объект `items`. Генератор по одному возвращает из него элементы. `yield from` позволяет это выразить более компактно:
```python {.example_for_playground}
def f(items):
yield from items
```
В чем преимущество генераторов над обычными контейнерами? В каких случаях использовать их более выгодно?
- Если неизвестен объем обрабатываемых данных. Например, при работе с сетевым потоком или файлом.
- Если в каждый момент времени требуется работать с элементом какой-либо последовательности, но не с последовательностью целиком.
- При работе с бесконечными последовательностями.
Напишите генератор `even_sequence()`, который при каждом обращении генерирует положительные четные числа, начиная с 0. {.task_text}
```python {.task_source #python_chapter_0230_task_0030}
```
Внутри генератор заводится целочисленная переменная, инициализирующаяся нулем. В вечном цикле после каждого `yield` она инкрементируется на 2. {.task_hint}
```python {.task_answer}
def even_sequence():
x = 0
while True:
yield x
x += 2
```
Генератор — это подвид итератора. Поэтому при его истощении также генерируется исключение `StopIteration`:
```python {.example_for_playground}
def strange_generator():
print("before return")
return
print("after return")
yield
g = strange_generator()
next(g)
```
```bash
before return
Traceback (most recent call last):
File "example.py", line 8, in <module>
next(g)
StopIteration
```
Так как внутри функции `strange_generator()` есть ключевое слово `yield`, она считается генератором. Генератор при создании абсолютно ничего не делает и ждет, пока его запустят, то есть вызовут метод `__next__()`.
Как только мы запускаем генератор, функция выполняется до оператора `yield` либо `return`. При достижении `yield` функция приостанавливает свое выполнение и ждет возобновления. А при достижении `return` происходит завершение работы генератора выбрасыванием исключения `StopIteration`.
## Встроенные функции для работы с генераторами
В питоне есть ряд встроенных функций, принимающих или возвращающих генераторы.
Например, функция `open()` может быть использована для открытия текстовых файлов. В таком случае она возвращает генератор, который позволяет лениво итерироваться по строкам в файле. В отличие от загрузки файла целиком такой подход здорово экономит память:
```python
import sys
with open("/path/to/file.txt") as f:
print(sys.getsizeof(f))
for l in f:
print(l)
```
```
208
Python
is
awesome
```
В данном примере мы вызвали `open()` через [контекстный менеджер,](/courses/python/chapters/python_chapter_0210/) получили генератор `f` и с его помощью проитерировались по строкам файла. Размер объекта генератора, рассчитанный через `getsizeof()`, не зависит от объема файла. Если бы в нашем файле было не три строки, а несколько миллионов, генератор бы по-прежнему занимал небольшое количество байт.
Помимо `open()`, генераторы возвращают встроенные функции `enumerate()`, `range()`, `map()` и [другие.](/courses/python/chapters/python_chapter_0280/)
Функции-конструкторы встроенных коллекций принимают на вход итераторы. В том числе в них можно передать и генератор:
```python {.example_for_playground}
print(list(range(5)))
print(dict(enumerate(range(8))))
```
```
[0, 1, 2, 3, 4]
{0: 0, 1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7}
```
Стандартная библиотека также предоставляет множество полезных генераторов, [среди которых](/courses/python/chapters/python_chapter_0280/) `itertools.chain()` и `itertools.zip_longest()`.
## Генератор с получаемым значением
Помимо получения значений из генератора существует возможность отправить в него значение. Генератор, которому можно предоставить значение, можно считать урезанной **корутиной**. «Урезанной», потому что нельзя использовать в цикле событий asyncio. Подробнее о корутинах в одной из следующих глав.
```python {.example_for_playground}
def input_gen():
while True:
r = yield
print(f"{r}")
c = input_gen()
c.send(None) # либо next(c)
c.send("Hi, input_gen")
next(c)
```
```
Hi, input_gen
None
```
Обратите внимание: после создания такого генератора его необходимо запустить либо через `send(None)`, либо через `next()`. Только после этого он будет готов принимать значения через `send()`. Если вызвать метод `send()` с аргументом, отличным от `None`, до вызова `next()`, произойдет исключение:
```
TypeError: can't send non-None value to a just-started generator
```
Обратите внимание, что в консоль вывелось две строки. Вызов метода `send()`, помимо отправки значения в генератор, запускает его до следующего `yield`. Поэтому при отправке `c.send("Hi, input_gen")` происходит прокрутка генератора (включая вывод в консоль переданного значения) до следующего `yield`. И при последующем вызове `next(c)` в консоль выводится переданное значение: `None`.
Как мы уже выяснили, с помощью выражения `yield` можно и отправлять, и получать данные. Мало кто знает, но эти две операции легко **объединить:**
```python
b = yield a
```
Как это читать? Сначала вернуть из корутины `a`, и когда какое-то значение будет отправлено в корутину через `send()`, присвоить его `b`. Таким образом через полученное значение `b` корутина может узнать, как вызывающая сторона отреагировала на передачу из корутины значения `a`.
Для остановки генератора существует метод `close()`. Но явно он почти никогда не вызывается, вместо этого он уничтожается сборщиком мусора.
Напишите функцию для поиска подстроки в тексте. Пусть она инициализируется искомой подстрокой и в вечном цикле принимает строки для поиска. Если подстрока найдена, пусть генератор отдает обратно индекс подстроки в строке. Если не найдена — то значение `-1`. {.task_text}
```python {.task_source #python_chapter_0230_task_0040}
def search(substr):
# Your code here
finder = search("is")
next(finder)
assert finder.send("Now is better than never.") == 4
assert finder.send("Readability counts.") == -1
```
Пусть генератор `search()` принимает аргумент `substr`. Тогда в генераторе можно завести переменную `i`, хранящую индекс подстроки `substr` в искомом тексте, и проинициализировать ее значением -1. В вечном цикле генератор будет возвращать `i`, принимать строку `line` для поиска и искать подстроку. Первые два действия объединяются конструкцией: `line = yield i`. Затем следует определение индекса подстроки в полученной строке: `i = line.find(substr)`. {.task_hint}
```python {.task_answer}
def search(substr):
i = -1
while True:
line = yield i
i = line.find(substr)
finder = search("is")
next(finder)
assert finder.send("Now is better than never.") == 4
assert finder.send("Readability counts.") == -1
```
## Резюмируем
- Итератор — объект, который позволяет перемещаться по коллекции и получать элементы.
- Итератор должен бросать исключение `StopIteration` при достижении конца коллекции.
- Генератор — это итератор для реализации ленивых вычислений. Например, он полезен для обработки бесконечной последовательности значений.
- С помощью выражения `yield` можно и отправлять, и получать данные из генератора.
- В питоне есть множество встроенных генераторов для решения типичных задач: `open()`, `zip()`, `map()`, `range()` и другие.
Наша группа в telegram. Здесь можно задавать вопросы и общаться.
Задонатить. Если вам нравится курс, вы можете поддержать развитие площадки!