Урок 45 из 84 · ООП
Итераторы и генераторы
Содержание урока
Генераторы и итераторы представляют собой инструменты, которые, как правило, используются для поточной обработки данных. В уроке рассмотрим концепцию итераторов в Python, научимся создавать свои итераторы и разберемся как работать с генераторами.
Итераторы в языке Python
Во многих современных языках программирования используют такие сущности как итераторы. Основное их назначение – это упрощение навигации по элементам объекта, который, как правило, представляет собой некоторую коллекцию (список, словарь и т.п.). Язык Python, в этом случае, не исключение и в нем тоже есть поддержка итераторов. Итератор представляет собой объект перечислитель, который для данного объекта выдает следующий элемент, либо бросает исключение, если элементов больше нет.
При изучении цикла for, вы можете наткнуться на такой термин как "итерирование". И если в других языках это слово могут применять к любым циклам, то в Python у этого слова есть и другое значение: итерирование — это взаимодействие с неким объектом, поддерживающим протокол итерации.
Для начала разберём, что же такое протокол в контексте Python. Протоколом называют набор определенных действий над объектом. И если некий объект "А" позволяет совершать над собой действия, описанные неким протоколом "Б", то говорят: "объект А реализует протокол Б" или "объект А поддерживает протокол Б". В последующих курсах вы узнаете, что различных протоколов в Python — множество. Даже многие синтаксические конструкции языка работают для самых разных объектов сходным образом именно потому, что объекты реализуют специальные протоколы. Так мы можем в шаблон подставлять не только строки, но и значения других типов, потому что эти типы реализуют протокол приведения к строке! В Python протоколы встречаются на каждом шагу.
Протокол итерации
Протокол итерации — один из самых важных протоколов в Python. Ведь именно он позволяет циклу for работать с самыми разными коллекциями (типами данных) единообразно. В чём же заключается этот протокол? Протокол требует от объекта быть итерируемым (iterable), т.е. иметь специальный метод __iter__. Если у iterable-объекта вызвать метод __iter__, то метод должен вернуть новый специальный объект — так называемый итератор (iterator). А итератор, в свою очередь, должен иметь метод __next__.
Звучит сложно, но давайте рассмотрим живой пример — итерирование списка. Список — итерируемый, поэтому нам подходит. Итак, создадим список и итератор для него:
>>> l = [1,2,3,5,8,11]
>>> i = iter(l)
>>> i
<list_iterator object at 0x7f517843a240>
Я вызвал для списка функцию iter, но на самом деле эта функция просто вызывает у списка соответствующий метод __iter__. Это сделано для удобства чтения кода, ведь читать имена вроде __foo__ не очень удобно. Некоторые другие функции делают что-то подобное, например функция len. Большинство же специальных (магических) методов с похожими именами вызывается внутри каких-то языковых конструкций и не предназначено для вызова напрямую.
Теперь у нас есть итератор i, попробуем повызывать у него метод __next__ как напрямую, так и с помощью более удобной функции next:
>>> i.__next__()
1
>>> i.__next__()
2
>>> next(i)
3
>>> next(i)
5
Как мы видим, при каждом вызове метод возвращает очередной элемент исходного списка. А между вызовами он помнит свою позицию в списке. Таким образом, итератор выполняет роль "курсора" в вашем редакторе текста: если нажимать стрелки, то курсор перемещается и указывает на новое место в тексте. Только итератор — это курсор, умеющий перемещаться только в одну сторону.
Но что же произойдёт, когда элементы в списке кончатся? Проверим:
>>> next(i)
8
>>> next(i)
11
>>> next(i)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
StopIteration
Когда итератор достиг конца исходного списка, последующий вызов next привёл к специальной ошибке StopIteration. Только в данном случае это не ошибка, ведь всё когда-нибудь заканчивается! StopIteration — это исключение (exception). И как мы помним из прошлых уроков, исключения - это тип данных в Python, который необходим для того, чтобы сообщать программисту об ошибках. В свою очередь, те конструкции языка Python, которые работают на основе протокола итерации, знают, как реагировать на это конкретное исключение. Например, цикл for "молча" завершает работу.
Теперь вы уже можете представить, как на самом деле работает цикл for. Он получает у iterable объекта новый итератор, а затем вызывает у итератора метод __next__ до тех пор, пока не будет выброшено исключение StopIteration. Интересно, не правда ли? Но дальше будет ещё интереснее!
Цикл for и итераторы
Основное место использования итераторов – это цикл for. Если вы перебираете элементы в некотором списке или символы в строке с помощью цикла for, то ,фактически, это означает, что при каждой итерации цикла происходит обращение к итератору, содержащемуся в строке/списке, с требованием выдать следующий элемент, если элементов в объекте больше нет, то итератор генерирует исключение, обрабатываемое в рамках цикла for незаметно для пользователя.
Приведем несколько примеров, которые помогут лучше понять эту концепцию. Для начала выведем элементы произвольного списка на экран.
>>> num_list = [1, 2, 3, 4, 5]
>>> for i in num_list:
print(i)
1
2
3
4
5
Как уже было сказано, объекты, элементы которых можно перебирать в цикле for, содержат в себе объект итератор, для того, чтобы его получить необходимо использовать функцию iter(), а для извлечения следующего элемента из итератора – функцию next().
>>> itr = iter(num_list)
>>> print(next(itr))
1
>>> print(next(itr))
2
>>> print(next(itr))
3
>>> print(next(itr))
4
>>> print(next(itr))
5
>>> print(next(itr))
Traceback (most recent call last):
File "<pyshell#12>", line 1, in <module>
print(next(itr))
StopIteration
Как видно из приведенного выше примера вызов функции next(itr) каждый раз возвращает следующий элемент из списка, а когда эти элементы заканчиваются, генерируется исключение StopIteration.
Создание собственных итераторов
Если нужно обойти элементы внутри объекта вашего собственного класса, необходимо построить свой итератор. Создадим класс, объект которого будет итератором, выдающим определенное количество единиц, которое пользователь задает при создании объекта. Такой класс будет содержать конструктор, принимающий на вход количество единиц и метод next(), без него экземпляры данного класса не будут итераторами.
class SimpleIterator:
def __init__(self, limit):
self.limit = limit
self.counter = 0
def __next__(self):
if self.counter < self.limit:
self.counter += 1
return 1
else:
raise StopIteration
s_iter1 = SimpleIterator(3)
print(next(s_iter1))
print(next(s_iter1))
print(next(s_iter1))
print(next(s_iter1))
В нашем примере при четвертом вызове функции next() будет выброшено исключение StopIteration. Если мы хотим, чтобы с данным объектом можно было работать в цикле for, то в класс SimpleIterator нужно добавить метод iter(), который возвращает итератор, в данном случае этот метод должен возвращать self.
class SimpleIterator:
def __iter__(self):
return self
def __init__(self, limit):
self.limit = limit
self.counter = 0
def __next__(self):
if self.counter < self.limit:
self.counter += 1
return 1
else:
raise StopIteration
s_iter2 = SimpleIterator(5)
for i in s_iter2:
print(i)
Генераторы
В Python не только коллекции являются iterable. Ещё существуют так называемые генераторы (generators). Что же такое генератор? Генератор — это iterable, элементы которого не хранятся в нём, но создаются по мере необходимости.
Генераторы позволяют значительно упростить работу по конструированию итераторов. В предыдущих примерах, для построения итератора и работы с ним, мы создавали отдельный класс. Генератор – это функция, которая будучи вызванной в функции next() возвращает следующий объект согласно алгоритму ее работы. Вместо ключевого слова return в генераторе используется yield. Проще всего работу генератора посмотреть на примере. Напишем функцию, которая генерирует необходимое нам количество единиц.
def simple_generator(val):
while val > 0:
val -= 1
yield 1
gen_iter = simple_generator(5)
print(next(gen_iter))
print(next(gen_iter))
print(next(gen_iter))
print(next(gen_iter))
print(next(gen_iter))
print(next(gen_iter))
Данная функция будет работать точно также, как класс SimpleIterator из предыдущего примера.
Ключевым моментом для понимания работы генераторов является то, при вызове yield функция не прекращает свою работу, а “замораживается” до очередной итерации, запускаемой функцией next(). Если вы в своем генераторе, где-то используете ключевое слово return, то дойдя до этого места будет выброшено исключение StopIteration, а если после ключевого слова return поместить какую-либо информацию, то она будет добавлена к описанию StopIteration.
Для того чтобы лучше понять генераторы рассмотрим работу такого генератора как range:
>>> numbers = range(3, 11, 2)
>>> for n in numbers:
... print(n)
...
3
5
7
9
>>> list(numbers)
[3, 5, 7, 9]
Здесь range генерирует последовательность чисел от 3 до (но не включая) 11 с шагом 2 (шаг и начальное значения можно опускать, тогда счёт будет производиться от нуля и с шагом в единицу). Цикл for итерирует числа. Затем я использую функцию list, чтобы получить список — эта функция может принять в качестве единственного аргумента iterable или iterator, элементы которого сложит во вновь созданный список.
Функция list накапливает значения в список, а tuple — в кортеж.
range представляет собой перезапускаемый генератор. Для такого генератора можно создавать сколько угодно итераторов, и для каждого из них значения будут генерироваться заново.
Существуют и неперезапускаемые генераторы. Эти при вызове метода __iter__ всегда возвращают один и тот же итератор. Поэтому по значениям такого генератора можно пройтись только один раз! Таким генератором является enumerate. Давайте взглянем на пример использования enumerate:
>>> l = enumerate("asdf")
>>> list(l)
[(0, 'a'), (1, 's'), (2, 'd'), (3, 'f')]
>>> list(l)
[]
Вторая попытка проитерировать объект в переменной l ничего не даёт, т.к. генератор уже отработал один проход.
А вот ещё один встроенный генератор — zip. Этот генератор принимает на входе несколько iterable или iterators и поэлементно группирует в кортежи. Демонстрация:
>>> keys = ["foo", "bar", "baz"]
>>> values = [1, 2, 3, 4]
>>> for k, v in zip(keys, values):
... print(k, "=", v)
...
foo = 1
bar = 2
baz = 3
>>> z = zip(range(10), "hello", [True, False])
>>> list(z)
[(0, 'h', True), (1, 'e', False)]
>>> list(z)
[]
Пример демонстрирует два момента:
- zip — не перезапускаемый
- zip — перестаёт генерировать кортежи, как только заканчиваются элементы в любом из источников.
Генераторы и ленивые вычисления
Большая часть языков программирования выполняет код в том порядке, в котором элементы кода написаны. Инструкции выполняются сверху вниз, выражения вычисляются после того, как будут вычислены их составляющие, функции вызываются после того, как будут вычислены их аргументы. Такая модель исполнения называется энергичной (eager).
Существует и ленивая (lazy) модель вычисления. В рамках этой модели вычисления производятся только тогда, когда их результат становится действительно нужен. Т.к. в любой программе при разных входных данных могут быть не нужны отдельные вычисления, то ленивая модель вычисления может дать определённые преимущества: то, что не нужно — не будет вычислено. Таким образом, ленивость можно рассматривать как своего рода оптимизацию.
Python, как язык с энергичной моделью вычисления, практически всегда и всё вычисляет сразу. Однако отдельные элементы ленивости присутствуют и в Пайтоне. Генераторы — один из таких элементов. Генераторы производят элементы только по мере необходимости. И даже целые конструкции, собранные из генераторов — эдакие конвейеры, собирающие составные значения — производят сборку по одному изделию за раз!
Так составной генератор zip(range(100000000), "abc") не генерирует все сто миллионов чисел, ведь строка "abc" слишком коротка, чтобы образовать столько пар. Но даже и этих пар не будет, если результат вычисления этого выражения не будет проитерирован! Так ленивость позволяет экономить память при обработке больших потоков данных — нам не нужно загружать все данные целиком, достаточно загружать и обрабатывать их небольшими порциями.
Ссылки:
itertools — очень полезный модуль стандартной библиотеки. Содержит множество функций для создания итераторов и дальнейшей работы с ними.