Что такое генератор питон
Итерируемый объект, итератор и генератор
Привет, уважаемые читатели Хабрахабра. В этой статье попробуем разобраться что такое итерируемый объект, итератор и генератор. Рассмотрим как они реализованы и используются. Примеры написан на Python, но итераторы и генераторы, на мой взгляд, фундаментальные понятия, которые были актуальны 20 лет назад и еще более актуальны сейчас, при этом за это время фактически не изменились.
Итераторы
Для начала вспомним, что из себя представляет паттерн «Итератор(Iterator)».
Назначение:
Существуют два вида итераторов, внешний и внутренний.
Внешний итератор — это классический (pull-based) итератор, когда процессом обхода явно управляет клиент путем вызова метода Next.
Внутренний итератор — это push-based-итератор, которому передается callback функция, и он сам уведомляет клиента о получении следующего элемента.
Классическая диаграмма паттерна “Итератор”, как она описана в небезызвестной книги «банды четырех»:
Aggregate — составной объект, по которому может перемещаться итератор;
Iterator — определяет интерфейс итератора;
ConcreteAggregate — конкретная реализация агрегата;
ConcreteIterator — конкретная реализация итератора для определенного агрегата;
Client — использует объект Aggregate и итератор для его обхода.
Пробуем реализовать на Python классический итератор
Конкретная реализация итератора для списка:
Конкретная реализация агрегата:
Теперь мы можем создать объект коллекции и обойти все ее элементы с помощью итератора:
А так как мы реализовали метод first, который сбрасывает итератор в начальное состояние, то можно воспользоваться этим же итератором еще раз:
Реализации могут быть разные, но основная идея в том, что итератор может обходить различные структуры, вектора, деревья, хеш-таблицы и много другое, при этом имея снаружи одинаковый интерфейс.
Протокол итерирования в Python
В книге «банды четырех» о реализации итератора написано:
Минимальный интерфейс класса Iterator состоит из операций First, Next, IsDone и CurrentItem. Но если очень хочется, то этот интерфейс можно упростить, объединив операции Next, IsDone и CurrentItem в одну, которая будет переходить к следующему объекту и возвращать его. Если обход завершен, то эта операция вернет специальное значения(например, 0), обозначающее конец итерации.
Именно так и реализовано в Python, но вместо специального значения, о конце итерации говорит StopIteration. Проще просить прощения, чем разрешения.
Сначала важно определиться с терминами.
Рассмотрим итерируемый объект (Iterable). В стандартной библиотеке он объявлен как абстрактный класс collections.abc.Iterable:
У него есть абстрактный метод __iter__ который должен вернуть объект итератора. И метод __subclasshook__ который проверяет наличие у класса метод __iter__. Таким образом, получается, что итерируемый объект это любой объект который реализует метод __iter__
Но есть один момент, это функция iter(). Именно эту функцией использует например цикл for для получения итератора. Функция iter() в первую очередь для получения итератора из объекта, вызывает его метод __iter__. Если метод не реализован, то она проверяет наличие метода __getitem__ и если он реализован, то на его основе создается итератор. __getitem__ должен принимать индекс с нуля. Если не реализован ни один из этих методов, тогда будет вызвано исключение TypeError.
Итого, итерируемый объект — это любой объект, от которого встроенная функция iter() может получить итератор. Последовательности(abc.Sequence) всегда итерируемые, поскольку они реализуют метод __getitem__
Теперь посмотрим, что с итераторами в Python. Они представлены абстрактным классом collections.abc.Iterator:
__next__ Возвращает следующий доступный элемент и вызывает исключение StopIteration, когда элементов не осталось.
__iter__ Возвращает self. Это позволяет использовать итератор там, где ожидается итерируемых объект, например for.
__subclasshook__ Проверяет наличие у класса метода __iter__ и __next__
Итого, итератор в python — это любой объект, реализующий метод __next__ без аргументов, который должен вернуть следующий элемент или ошибку StopIteration. Также он реализует метод __iter__ и поэтому сам является итерируемым объектом.
Таким образом можно реализовать итерируемый объект на основе списка и его итератор:
Функция next() вызывает метод __next__. Ей можно передать второй аргумент который она будет возвращать по окончанию итерации вместо ошибки StopIteration.
Прежде чем переходить к генераторам, рассмотрим еще одну возможность встроенной функции iter(). Ее можно вызывать с двумя аргументами, что позволит создать из вызываемого объекта(функция или класс с реализованным методом __call__) итератор. Первый аргумент должен быть вызываемым объектом, а второй — неким ограничителем. Вызываемый объект вызывается на каждой итерации и итерирование завершается, когда возбуждается исключение StopIteration или возвращается значения ограничителя.
Например, из функции которая произвольно возвращает 1-6, можно сделать итератор, который будет возвращать значения пока не «выпадет» 6:
Небольшой класс ProgrammingLanguages, у которого есть кортеж c языками программирования, конструктор принимает начальное значения индекса по названию языка и функция __call__ которая перебирает кортеж.
Можем перебрать все языки начиная с C# и до последнего:
Генераторы
С точки зрения реализации, генератор в Python — это языковая конструкция, которую можно реализовать двумя способами: как функция с ключевым словом yield или как генераторное выражение. В результате вызова функции или вычисления выражения, получаем объект-генератор типа types.GeneratorType.
В объекте-генераторе определены методы __next__ и __iter__, то есть реализован протокол итератора, с этой точки зрения, в Python любой генератор является итератором.
Концептуально, итератор — это механизм поэлементного обхода данных, а генератор позволяет отложено создавать результат при итерации. Генератор может создавать результат на основе какого то алгоритма или брать элементы из источника данных(коллекция, файлы, сетевое подключения и пр) и изменять их.
Ярким пример являются функции range и enumerate:
range генерирует ограниченную арифметическую прогрессию целых чисел, не используя никакой источник данных.
enumerate генерирует двухэлементные кортежи с индексом и одним элементом из итерируемого объекта.
Yield
Для начало напишем простой генератор не используя объект-генератор. Это генератор чисел Фибоначчи:
Но используя ключевое слово yield можно сильно упростить реализацию:
Любая функция в Python, в теле которой встречается ключевое слово yield, называется генераторной функцией — при вызове она возвращает объект-генератор.
Объект-генератор реализует интерфейс итератора, соответственно с этим объектом можно работать, как с любым другим итерируемым объектом.
Рассмотрим работу yield:
Создается стейт-машина в которой при каждом вызове __next__ меняется состояния и в зависимости от него вызывается тот или иной кусок кода. Если в функции yield в цикле, то соответственно состояние стейт-машины зацикливается пока не будет выполнено условие.
Свой вариант range:
Генераторное выражение (generator expression)
Если кратко, то синтаксически более короткий способ создать генератор, не определяя и не вызывая функцию. А так как это выражение, то у него есть и ряд ограничений. В основном удобно использовать для генерации коллекций, их несложных преобразований и применений на них условий.
В языках программирования есть такие понятия, как ленивые/отложенные вычисления(lazy evaluation) и жадные вычисления(eager/greedy evaluation). Генераторы можно считать отложенным вычислением, в этом смысле списковое включение(list comprehension) очень похожи на генераторное выражение, но являются разными подходами.
Первый вариант работает схожим с нашей функцией cool_range образом и может генерировать без проблем любой диапазон. А вот второй вариант создаст сразу целый список, со всеми вытекающими от сюда проблемами.
Yield from
Для обхода ограниченно вложенных структур, традиционный подход использовать вложенные циклы. Тот же подход можно использовать когда генераторная функция должна отдавать значения, порождаемые другим генератором.
Функция похожая на itertools.chain:
Но вложенные циклы можно убрать, добавив конструкцию yield from:
Основная польза yield from в создании прямого канала между внутренним генератором и клиентом внешнего генератора. Но это уже больше тема про сопрограммы(coroutines), которые заслуживают отдельной статьи. Там же можно обсудить методы генератора: close(), throw() и send().
И в заключении еще один пример. Функция принимающая итерируемый объект, с любым уровнем вложенности другими итерируемыми объектами, и формирующая плоскую последовательность:
Генераторы Python. Их создание и использование
Приходилось ли вам когда-либо работать с настолько большим набором данных, что он переполнял память вашего компьютера? Или быть может у вас была сложная функция, для которой нужно было бы сохранять внутреннее состояние при вызове? А если при этом функция была слишком маленькой, чтобы оправдать создание собственного класса? Во всех этих случаях вам придут на помощь генераторы Python и ключевое слово yield.
Прочитав эту статью, вы узнаете:
Если вы являетесь Питонистом начального или среднего уровня и вы заинтересованы в том, чтобы научиться работать с большими наборами данных в питоновском стиле, то скорее всего это руководство для вас.
По ссылке ниже вы можете скачать копию файла с данными, используемыми в этом руководстве.
Использование Генераторов
Функции генераторов (их описание можно почитать в PEP 255) представляют собой особый вид функций, которые возвращают «ленивый итератор». И хотя содержимое этих объектов вы можете перебирать также как и списки, но при этом, в отличие от списков, ленивые итераторы не хранят свое содержимое в памяти. Чтобы составить общее представление об итераторах в Python взгляните на статью Python “for” Loops (Definite Iteration).
Теперь, когда вы имеете примерное представление о том, чем является генератор, у вас наверняка появилось желание увидеть как он работает. Давайте рассмотри два примера. В первом вы увидите общий принцип работы генераторов. В последующих у вас будет возможность изучить работу генераторов более подробно.
Пример 1: Чтение больших файлов
Списки Python
Работа с потоками данных и большими файлами, такими например как CSV, являются наиболее распространенными вариантами использования генераторов. Давайте возьмем CSV файл (CSV является стандартным форматом для обмена данными, колонки в нем разделяются при помощи запятых). Предположим, что вы хотите посчитать количество имеющихся в нем рядов. Код ниже предлагает один из путей для, того, чтобы осуществить это:
Это вполне приемлемое решение, но будет ли этот подход работать, если файл окажется слишком большим? А что если файл окажется больше чем вся доступная память, которая есть в нашем распоряжении? Для того чтобы ответить на этот вопрос, давайте предположим, что csv_reder() будет открывать файл и считывать его в массив.
В этом случае open() возвращает объект генератора, который вы можете «лениво» (не обсчитывая заранее) перебирать ряд за рядом. Тем не менее, file.read().split() загружает все данные в память сразу, вызывая ошибку памяти (MemoryError).
До того как это произойдет, вы можете заметить, что ваш компьютер замедлился. Возможно вам потребуется даже вручную остановить программу. Но что нам делать, если мы хотим этого избежать?
Генераторы Python
Давайте взглянем на новое определение функции csv_reader() :
В этой версии вы открываете файл и проходите его содержимое, возвращая ряд за рядом. Этот код выводит следующий результат без каких-либо ошибок:
Почему так получилось? Да потому что вы по сути превратили функцию csv_reader() в генератор. Эта версия кода открывает файл, проходит по строкам и извлекает для чтения лишь отдельный ряд, вместо того, чтобы возвращать весь файл целиком.
Также вы можете определить выражение создающее генератор, которое очень похоже по синтаксису на выражение создающее список. В таком виде вы можете использовать генератор без вызова функции:
Такой способ создания генератора csv_gen является более лаконичным.
Более подробно о yield мы расскажем позже, а пока запомните основные отличия между использованием ключевых слов yield и return:
Пример 2: Создание бесконечной последовательности
Создание же бесконечной последовательности стопроцентно потребует от нас использования генератора. Причина проста — ограниченность памяти нашего компьютера.
Если вы попробуете запустить этот код в теле цикла for, то увидите, что на самом деле он бесконечный:
Эта программа будет исполняться, до тех пор, пока вы ее вручную не остановите.
Пример 3: Нахождение палиндромов
Вы можете использовать бесконечные последовательности множеством различных способов. Одним из них, который мы отметим особенно, является создание детектора палиндромов. Детектор палиндромов выявляет все последовательности букв и цифр, которые являются палиндромами. Это слова или числа, которые читаются одинаково вперед и назад, как «121» например. Сперва давайте зададим наш числовой детектор палиндромов:
Не особо беспокойтесь о понимании вычислений, лежащих в основе данного кода. Просто заметьте, что функция принимает введенное число, переворачивает его, и сравнивает с оригиналом. Теперь вы можете использовать генератор бесконечной последовательности для получения бегущего списка со всеми числовыми палиндромами:
В консоли выводятся только те номера, которые читаются одинаково и вперед и назад.
Примечание: на практике вам вряд ли придется писать свой собственный бесконечный генератор последовательностей, по той простой причине, что есть уже очень эффективный генератор itertools.count() из модуля itertools.
Теперь, когда вы познакомились с простым примером использования генератора бесконечной последовательности, давайте рассмотрим более детально работу этого генератора.
Понимание работы генератора Python
К этому моменту вы уже познакомились с двумя основными способами создания генераторов: с помощью функции и с помощью выражения. У вас также должно было сформироваться интуитивное представление о том, как работает генератор. Давайте теперь уделим некоторое время тому, чтобы сделать наши знания более четкими.
Примечание. Если вы хотите больше узнать о генераторах списков, множеств и словарей в Python, можете прочитать статью Эффективное использование генераторов списков (англ).
Создание генератора с помощью выражения
Как и выражения создающие списки, выражения создающие генераторы позволяют быстро получить объект генератора с помощью всего одной строчки кода. Использоваться они могут в тех же случаях, что и выражения создающие списки, но при этом у них есть одно дополнительное преимущество. Их можно создавать не удерживая весь объект в памяти перед итерацией. Если перефразировать, вы не будете расходовать память при использовании генератора.
Давайте для примера возьмем возведение в квадрат некоторых чисел:
Это подтверждает тот факт, что с помощью круглых скобок вы создали объект генератора, а также то, что он отличается от списка.
Профилирование эффективности генератора
Ранее мы узнали, что использование генераторов является отличным способом оптимизации памяти. И хотя генератор бесконечной последовательности является наиболее ярким примером этой оптимизации, давайте рассмотрим еще один пример с возведением числа в квадрат и проверим размер полученных объектов.
Вы можете сделать это с помощью вызова функции sys.getsizeof () :
В этом случае размер списка, полученного с помощью выражения составляет 87 624 байта, а размер генератора — только 120. То есть, список занимает памяти в 700 раз больше, чем генератор! Однако нужно помнить одну вещь. Если размер списка меньше доступной памяти на работающей машине, тогда обработка его будет занимать меньше времени, чем аналогичная обработка генератора. Чтобы удостовериться в этом, давайте просуммируем результаты приведенных выше выражений. Вы можете использовать для анализа функцию cProfile.run () :
Здесь вы можете видеть, что суммирование всех значений, содержащихся в списке заняло около трети времени аналогичного суммирования с помощью генератора. Поэтому если скорость является для вас проблемой, а память — нет, то список, возможно, окажется лучшим инструментом для работы.
Примечание. Эти измерения действительны не только для генераторов, созданных с помощью выражений. Они абсолютно идентичны и для генераторов, созданных с помощью функции. Ведь, как мы уже говорили выше, эти генераторы эквивалентны.
Генераторы Python: что это такое и зачем они нужны
Генераторы используют, чтобы оперативная память не давилась большими объёмами информации. В Python это фишки, экономящие память.
Допустим, у вас есть файл, который весит десяток гигабайт. Из него нужно выбрать и обработать строки, подходящие под какое-то условие, а то и сравнить со строками другого большого файла.
Другой пример: нужно проанализировать практически бесконечный поток данных. Это могут быть, например, показания счётчиков, биржевые котировки, сетевой трафик.
А может, нужно создать поток данных самостоятельно: рассчитать комбинаторную структуру для определения вероятности какого-то события, математическую последовательность или последовательность случайных чисел.
Что делать? Хранить такие объёмы данных в компьютере нереально: они не поместятся в оперативную память — а некоторые и на жёсткий диск. Выход один — обрабатывать информацию небольшими порциями, чтобы не вызывать переполнения памяти. В Python на этот случай есть специальный инструмент — генераторы.
Программист, консультант, специалист по документированию. Легко и доступно рассказывает о сложных вещах в программировании и дизайне.
Что такое генератор и как он работает?
Этим генераторы отличаются от списков — те хранят в памяти все свои элементы, и удалить их можно только программно. Вычисления с помощью генераторов называются ленивыми, они экономят память.
Рассмотрим пример: создадим объект-генератор gen с помощью так называемого генераторного выражения. Он будет считать квадраты чисел от 1 до 4 — такую последовательность создаёт функция range(1,5).
Когда мы выведем на консоль переменную gen, то увидим лишь сообщение, что это объект-генератор.
При четырёх вызовах метода next(a) будут по одному рассчитываться и выводиться на консоль значения генератора: 1, 4, 9, 16. Причём в памяти будет сохраняться только последнее значение, а предыдущие сотрутся.
Когда мы попытаемся вызвать next(gen) в пятый раз, генератор сотрёт из памяти последний элемент (число 16) и выдаст исключение StopIteration.
Всё! Генератор больше не работает. Сколько бы мы ни вызывали next(gen), ничего считаться не будет. Чтобы запустить генератор ещё раз, придётся создавать его заново.
И что, для вычисления генератора придётся много раз вызывать next()?
Нет, значения можно вычислять в цикле for. В этом случае метод next() вызывается неявно. Например:
Когда весь цикл пройден, произойдёт исключение StopIteration. Хотя на консоль сообщение об этом не выводится, но генератор помнит о нём и больше работать не будет. То есть цикл for можно запускать только один раз, во второй раз не получится. Нельзя об этом забывать.
И чем помогут генераторы в наших задачах?
Для этого сначала рассмотрим упрощённый способ создания генератора — с помощью генераторного выражения.
Генераторные выражения позволяют создавать объект-генератор в одну строчку. В общем случае их пишут по шаблону:
( выражение for j in итерируемый объект if условие)
Где for, in, if — ключевые слова, j — переменная.
Пример генераторного выражения мы рассмотрели выше. Теперь посмотрим, как можно применить его для обработки большого файла.
Перед нами задача: на сервере есть огромный журнал событий log.txt, в котором хранятся сведения о работе какой-то системы за год. Из него нужно выбрать и обработать для статистики данные об ошибках — строки, содержащие слово error.
Такие строки можно выбрать и сохранить в памяти с помощью списка:
Здесь path — путь к файлу log. В результате сформируется список вида:
[строка1, строка2, строка3, ….. ]
В списке e_l содержатся все строки со словом error, они записаны в память компьютера. Теперь их можно обработать в цикле. Недостаток метода в том, что, если таких строк будет слишком много, они переполнят память и вызовут ошибку MemoryError.
Переполнения памяти можно избежать, если организовать поточную обработку данных с использованием объекта-генератора. Мы создадим его с помощью генераторного выражения (оно отличается от генератора списка только круглыми скобками).
Рассмотрим следующий код:
Этот метод не вызывает переполнения, так как в каждый момент времени в памяти находится только одна строка. При этом нужный для работы объём памяти не зависит от размера файла и количества строк, удовлетворяющих условию.
Как ещё можно создавать генераторы?
Генераторные выражения — это упрощённый вариант функций-генераторов, также создающих генераторы.
Функция-генератор отличается от обычной функции тем, что вместо команды return в ней используется yield. И если return завершает работу функции, то инструкция yield лишь приостанавливает её, при этом она возвращает какое-то значение.
При первом вызове метода next() выполняется код функции с первой команды до yield. При втором next() и последующих до конца генератора — код со следующей после yield команды и до тех пор, пока yield не встретится снова.
Чтобы было понятнее, рассмотрим небольшой пример:
Здесь функция f_gen(5) при вызове создаёт генератор a. Мы видим это, когда выводим a на консоль.
Посчитаем значения генератора в цикле for.
Как видим, значения переменных n и s между вызовами сохраняются.
Yield — инструмент очень гибкий. Его можно несколько раз использовать в коде функции-генератора. В этом случае команды yield служат разделителями кода: при первом вызове метода next() выполняется код до первого yield, при следующих вызовах — операторы между yield. При этом в генераторной функции необязательно должен быть цикл, все значения генератора и так посчитаются.
Как создать бесконечную последовательность
Рассмотрим, как можно с помощью генератора создать математическую последовательность, например, программу, генерирующую простые числа (напоминаем, это числа, не имеющие делителей, кроме 1).
Наша программа будет последовательно анализировать целые числа больше 1. Для каждого числа n программа ищет делители в диапазоне от 2 до √n. Если делители есть, программа переходит к следующему числу. Если их нет, значит, n — число простое, и программа выводит его на печать.
Этот код выдаёт бесконечную последовательность простых чисел без ограничения сверху. Остановить его можно только вручную.
Подобным образом с помощью генераторов можно создавать ряды случайных чисел, комбинаторные структуры, рекуррентные ряды, например, ряд Фибоначчи и другие последовательности.
Какие ещё методы есть у генераторов?
Когда-то был один next(), но в Python 2.5 появилось ещё три метода:
Рассмотрим пару небольших примеров.
С помощью этих методов можно создавать сопрограммы, или корутины, — это функции, которым можно передавать значения, приостанавливать и снова возобновлять их работу. Их обычно используют в Python для анализа потоков данных в корпоративной многозадачности. Генераторы позволяют создавать сложные разветвлённые программы для обработки потоков.
Что ещё можно сказать
С изучения генераторов начинается освоение последовательной обработки гигантских потоков данных. Это может быть, например, трейдинг и технический анализ в биржевых операциях.
Но даже если не говорить о глобальных задачах, скрипты с применением генераторов — это способ избежать копирования данных в память. Генераторы позволяют экономить ресурсы компьютера и создавать красивый чистый код.
Изучить генераторы и другие объекты Python можно на курсах в Skillbox. Вы получите серьёзные теоретические знания и практический опыт. С самого начала обучения будете участвовать в реальных проектах. Те, кто успешно окончит курсы, станут программистами middle-уровня, а мы поможем найти хорошую работу.
Веб-скрапинг (web scraping) автоматизированное получение данных с веб-страниц.