Знакомимся с продвинутыми возможностями Python: итераторы, генераторы, itertools
2026-02-26 17:02 Diff
https://ru.hexlet.io/blog/posts/znakomimsya-s-prodvinutymi-vozmozhnostyami-python-iteratory-generatory-itertools

В Python есть много возможностей, которые привлекают математиков. Вот некоторые из них: встроенная поддержка кортежей, списков и множеств, которые записываются практически так же, как это делается в математике, list comprehensions или генераторы списков, синтаксис которых похож на генераторы множеств, и другое.

Ещё один набор полезных для математиков инструментов — итераторы и генераторы, а также связанный с ними модуль itertools. Эти инструменты позволяют писать элегантный код при работе с такими математическими объектами, как бесконечные последовательности, случайные процессы, рекуррентные отношения и комбинаторные структуры. В этой публикации описана работа с итераторами и генераторами в Python.

Содержание

Итераторы

Итераторы — объекты, которые позволяют обходить коллекции. Коллекции не должны обязательно существовать в памяти и быть конечными. Официальную документацию смотрите по ссылке. Примечание редактора: также смотрите наш курс по спискам.

Давайте уточним определения. Итерируемый — объект, в котором есть метод __iter__. В свою очередь, итератор — объект, в котором есть два метода: __iter__ и __next__. Почти всегда iterator возвращает себя из метода __iter__, так как они выступают итераторами для самих себя, но есть исключения.

В целом стоит избегать прямого вызова __iter__ и __next__. При использовании for или генераторов списков Python вызывает эти методы сам. Если всё-таки необходимо вызвать методы напрямую, используйте встроенные функции iter и next и в параметрах передавайте итератор или контейнер. Например, если c — итерируемый, используйте конструкцию iter(c) вместо c.__iter__(). Если a — итератор, используйте next(a), а не a.__next__(). Это похоже на использование len.

Раз уж речь зашла о len, то стоит упомянуть, что итераторы не должны иметь и часто не имеют определённой длины. Поэтому в них часто нет имплементации __len__. Чтобы подсчитать количество элементов в итераторе, приходится делать это вручную или использовать sum. Пример есть ниже после раздела о модуле itertools.

Некоторые итерируемые (iterable) не являются итераторами, но используют другие объекты как итераторы. Например, объект list относится к итерируемым, но не является итератором. В нём реализован метод __iter__, но отсутствует метод __next__. Итераторы объектов list относятся к типу listiterator. Обратите внимание, у объектов list есть определённая длина, а у listiterator нету.

Когда итератор завершает работу, интерпретатор Python ожидает возбуждения исключения StopIteration. Однако, как уже отмечалось, итераторы могут работать с бесконечными множествами. В таких случаях программист должен позаботиться о выходе из цикла.

Ниже дан простой пример итератора. Он считает с нуля до бесконечности. Это упрощённая версия itertools.count.

Посмотрите пример использования. В последней строке сделана попытка превратить итератор в список. Это приводит к бесконечному циклу.

Важная поправка к сказанному выше: если у объекта нет метода __iter__, его можно обойти, если определить метод __getitem__. В этом случае встроенная функция iter возвращает итератор с типом iterator, который использует __getitem__ для обхода элементов списка. Этот метод возвращает StopIteration или IndexError, когда обход завершается. Пример:

И пример использования:

Рассмотрим ещё один интересный пример: генерацию последовательности Q Хофштадтера. В приведённом ниже коде итератор используется для генерации последовательности с помощью вложенных повторений.

Q(n)=Q(n−Q(n−1))+Q(n−Q(n−2))

Например, qsequence([1, 1]) генерирует точную последовательность Хофштадтера. Мы используем исключение StopIteration, чтобы показать, что последовательность не может продолжаться, так как для генерации следующего элемента должен использоваться несуществующий индекс. Если в параметрах указать значения [1, 2], последовательность немедленно заканчивается.

Вот пример использования:

Генераторы

Генераторами называют итераторы, определение которых выглядит как определение функций. Ещё одно определение: генераторы — функции, которые внутри используют выражение yield. Генераторы не могут возвращать значения, вместо этого выдают элементы по готовности. Python автоматизирует запоминание контекста генератора, то есть текущий поток управления, значение локальных переменных и так далее. Каждый вызов метода __next__ у объекта генератора возвращает следующее значение. Метод __iter__ также реализуется автоматически. То есть генераторы можно использовать везде, где требуются итераторы. Пример кода ниже похож на ранее рассмотренный класс итератора. Но этот код более компактный и читабельный.

Посмотрите, как это применяется на практике.

Теперь взгляните на реализацию последовательности Q Хофштадтера с помощью генератора. Заметьте, эта реализация значительно проще использованного выше подхода. Однако здесь уже невозможно использовать методы типа current_state. Извне невозможно получить доступ к переменным, которые хранятся в контексте генератора.

Существует словарь gi_frame.f_locals, но он относится к CPython, но не входит в стандарт языка Python.

Одно из возможных решений — получение одновременно списка и результата.

def hofstadter_generator(s): a = s[:] while True: try: q = a[-a[-1]] + a[-a[-2]] a.append(q) yield q except IndexError: return

Обратите внимание, итерация в данном примере завершается простым return без параметров. Внутри происходит возбуждение исключения StopIteration. Следующий пример связан с распределением Бернулли, которое реализуется с помощью двух генераторов. Речь идёт о бесконечной последовательности случайных булевых значений. При этом вероятность True равна p, а вероятность False определяется формулой q=1-p. Затем применяется экстрактор фон Неймана, который принимает процесс Бернулли с 0 < p < 1 как источник энтропии и возвращает чистый процесс Бернулли с p = 0.5.

import random def bernoulli_process(p): if p > 1.0 or p < 0.0: raise ValueError("p should be between 0.0 and 1.0.") while True: yield random.random() < p def von_neumann_extractor(process): while True: x, y = next(proccess), next(process) if x != y: yield x

Наконец, с помощью генераторов удобно реализовывать дискретные динамические системы. Пример ниже показывает, как с помощью генераторов реализуется отображение тент.

>>> def tent_map(mu, x0): ... x = x0 ... while True: ... yield x ... x = mu * min(x, 1.0 - x) ... >>> >>> t = tent_map(2.0, 0.1) >>> for __ in range(30): ... print(next(t)) ... 0.1 0.2 0.4 0.8 0.4 0.8 0.4 0.8 0.4 0.8 0.4 0.8 0.4 0.8 0.4 0.8 0.4 0.799999999999 0.400000000001 0.800000000003 0.399999999994 0.799999999988 0.400000000023 0.800000000047 0.399999999907 0.799999999814 0.400000000373 0.800000000745 0.39999999851 0.79999999702

Ещё один пример касается последовательности Коллатца.

Обратите внимание, в этом примере не нужно вручную использовать StopIteration. Это исключение срабатывает автоматически, когда поток управления достигает конца функции.

Пример использования генератора:

>>> # Если гипотеза Коллатца верна, list(collatz(n)) с любым n ... # всегда завершается >>> list(collatz(7)) [7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1] >>> list(collatz(13)) [13, 40, 20, 10, 5, 16, 8, 4, 2, 1] >>> list(collatz(17)) [17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1] >>> list(collatz(19)) [19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]

Рекурсивные генераторы

Генераторы могут быть рекурсивными, как любая другая функция. Рассмотрим это на примере собственной реализации itertools.permutations. Это генератор перестановок элементов в списке. Обратите внимание, стандартная функция itertools.permutations работает быстрее, поэтому используйте её на практике. Идея простая: функция перемещает каждый элемент списка на первое место, заменяя его первым элементом в списке.

Генераторные выражения

Генераторные выражения позволяют реализовать генераторы с помощью очень простого синтаксиса. В примере ниже представлен генератор, который обходит все совершенные квадраты. Результатами генераторных выражений являются объекты с типом generator. В них реализованы методы __next__ и __iter__.

Процесс Бернулли из предыдущих разделов также можно реализовать с помощью генераторных выражений. В данном примере p=0.4. Если в генераторном выражении требуется ещё один итератор, который используется в качестве счётчика цикла, можно использовать itertools.count для генерации бесконечной последовательности. В противном случае можно использовать range.

Как отмечалось выше, генераторные выражения можно передавать в функции, которые нуждаются в итераторе. Например, сумму первых десяти совершенных квадратов можно получить так:

Ниже будут другие примеры генераторных выражений.

Модуль itertools

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

Обратите внимание, представленные ниже алгоритмы не являются оптимальными для практического использования. Примеры используются, чтобы показать возможности перестановок и комбинаций. На практике лучше избегать перечисления перестановок и комбинаций, если вы не имеете веской причины для этого, так как размер перечислений растёт по экспоненте.

Посмотрите на интересные примеры ниже. В первом представлен альтернативный способ реализации известного паттерна: обход трёхмерного массива, а также обход всех индексов с 0≤i<j<k≤n.

Альтернативные реализации с использованием перечислителей itertools обеспечивают два преимущества: они короче (одна строка вместо трёх), и их проще обобщать. Нужно помнить, что разница в быстродействии может быть значительной, особенно при больших значениях n.

Второй пример касается интересной математической задачи. С помощью генераторных выражений, itertools.combinations и itertools.permutations вычислим количество инверсий перестановки, а затем суммируем количество инверсий во всех перестановках в списке.

Сумма количества инверсий перестановок n равна OEIS A001809. Поэтому относительно легко показать, что закрытая форма равна n!n(n-1)/4. На практике эта формула эффективнее, но пример кода ниже необходим для отработки применения перечислителей itertools.

Пример использования:

В качестве ещё одного примера давайте рассчитаем количество повторений с помощью метода полного перебора. Даны n и k, количество повторений Dn,k определяется как количество перестановок множества n, в котором k фиксированных значений.

Сначала пишем функцию, которая использует генераторное выражение для подсчёта фиксированных значений в перестановке. Затем используем itertools.permutations и ещё одно генераторное выражение, чтобы посчитать общее количество перестановок n, в которых k фиксированных значений. Ещё раз обратите внимание, код ниже неоптимальный, он служит для отработки применения генераторных выражений.

Применение:

В статье рассмотрели особенности использования итераторов, генераторов и модуля itertools в Python. Вопросы и пожелания пишите в комментариях.

Адаптированный перевод статьи A Study of Python's More Advanced Features Part I: Iterators, Generators, itertools by Sahand Saba. Мнение адмнистрации «Хекслета» может не совпадать с мнением автора оригинальной публикации.