# Глава 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 ``` В данном примере итерабельным объектом является список `numbers`. Чтобы пройтись по нему, под капотом цикла `for` создается итератор. Он и перебирает элементы, пока они не кончатся. Если немного упростить, то цикл `for n in numbers` — всего лишь синтаксический сахар примерно над такой конструкцией: ```python def for_loop(numbers): iterator = numbers.__iter__() while True: try: n = iterator.__next__() except StopIteration: break else: print(n) ``` На вход цикла `for` должен поступать итерабельный объект. То есть такой объект, у которого присутствует dunder-метод `__iter__()`, возвращающий итератор. Для начала работы с итерабельным объектом необходимо получить итератор на первый элемент. Благодаря ему можно забирать элементы коллекции и двигаться по ней вперед. При перемещении по коллекции у итератора вызывается dunder-метод `__next__()`, который возвращает следующий элемент. Если следующего элемента нет, метод бросает исключение `StopIteration`. Генерация этого исключения не считается ошибочной ситуацией: `StopIteration` выступает в качестве маркера окончания прохода по коллекции для вызывающего кода. Исключение `StopIteration` сигнализирует, что элементы иссякли и итерироваться дальше не нужно. Итератор — объект, который позволяет поэлементно обходить коллекции: списки, кортежи, словари и так далее. Он отвечает за: - возвращение данных по одному элементу из контейнера или потока, - отслеживание текущего и пройденных элементов. Объект считается итератором, если он **следует протоколу итератора,** то есть определяет два 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) ``` ``` 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`. ## Бесконечные генераторы В модуле `itertools` есть генератор `cycle`. Он позволяет закольцованно перебирать элементы переданного ему итерабельного объекта: ```python from itertools import cycle pool = cycle(["-", "\\", "|", "/"]) for i, elem in enumerate(pool): print(elem) if i > 5: break ``` ``` - \ | / - \ | ``` Напишите бесконечный генератор `cycle`, который по кругу выдает элементы переданного ему списка. {.task_text} ```python {.task_source #python_chapter_0230_task_0050} def cycle(lst): # Your code here pool = cycle(["A", "B", "C"]) for i, elem in enumerate(pool): print(elem) if i > 5: break ``` Организуйте два вложенных цикла: внутри `while True` циклом `for item in lst` перебирайте элементы `lst` и возвращайте их через `yield`. {.task_hint} ```python {.task_answer} def cycle(lst): while True: for item in lst: yield item pool = cycle(["A", "B", "C"]) for i, elem in enumerate(pool): print(elem) if i > 5: break ``` ## Встроенные функции для работы с генераторами В питоне есть ряд встроенных функций, принимающих или возвращающих генераторы. Например, функция `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. Подробнее о корутинах мы [поговорим](/courses/python/chapters/python_chapter_0320/) в главе про модуль 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()`. Если до вызова `next()` вызвать метод `send()` с аргументом, отличным от `None`, произойдет исключение: ``` 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 ``` ## Резюмируем - Итератор — объект, который позволяет поэлементно перебирать последовательности значений. - Объект считается итератором, если он реализует протокол итератора: dunder-методы `__iter__()` и `__next__()`. - При истощении генератора он должен бросить исключение `StopIteration`. - Генератор — это итератор для реализации ленивых вычислений. Например, он полезен для обработки бесконечных последовательностей. - С помощью выражения `yield` можно и отправлять, и получать данные из генератора. - В питоне есть множество встроенных генераторов для решения типичных задач: `open()`, `zip()`, `map()`, `range()` и другие.