Programming: Python:


Итераторы и простые генераторы



  Автор: Дэвид Мертц (David Mertz) - нештатн. журналист Gnosis Software Inc.
  Перевод: Intersoft Lab
  Источники:

В Python 2.2 появилась новая конструкция со своим ключевым словом. Эта конструкция - генератор, а ключевое слово - yield. Хотя генераторы позволяют реализовать новые, мощные и оригинальные идеи, все же не так-то просто понять, как они работают. Эта статья - попытка ненавязчивого объяснения этой конструкции, равно как связанного с ней понятия итераторов.

Что такое Python?

Python - свободно доступный, интерпретируемый язык программирования высокого уровня, разработанный Гвидо ван Россумом (Guido van Rossum). Он объединяет ясный синтаксис с мощной (но необязательно) объектно-ориентированной семантикой. Python может быть установлен на любой платформе и обеспечивает прекрасную совместимость при переходе с одной платформы на другую.

Введение

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

И хотя то, что предлагает Python 2.2, не настолько умопомрачительно, как, например, полные продолжения и микронити, представленные в Stackless Python, генераторы и итераторы действительно могут кое-что, что выделяет их среди традиционных функций и классов.

Давайте рассмотрим сначала итераторы, поскольку их легче понять. Прежде всего, итератор - это объект, у которого имеется метод .next(). Это не совсем верно, но достаточно близко. На самом деле, большая часть контекстов требует объект, который сгенерирует итератор, когда к нему применяется новая встроенная функция iter(). Для того, чтобы определенный пользователем класс (который имеет необходимый метод .next()) возвращал итератор, нужно всего лишь обеспечить возврат self методом __iter__(). Примеры ниже пояснят сказанное. Метод .next() может вызвать исключение StopIteration, если итерация логически завершилась.

Генератор немного сложнее и является более общим понятием. Генераторы используются в основном для определения итераторов; поэтому не всегда стоит учитывать все тонкости их применения. Генератор является функцией, которая запоминает точку в теле функции, из которой происходил последний возврат. Второй (или n-ный) вызов генератора оказывается в середине функции, причем все локальные переменные оказываются неизмененными с момента последнего вызова.

В некоторой степени генераторы похожи на замыкания (closure), о которых шла речь в предыдущих статьях о функциональном программировании. Подобно замыканию, генератор "помнит" состояние своих данных. Но с генератором можно достигнуть большего в том смысле, что он также "помнит" свою позицию в пределах структуры управления потоком данных (что в императивном программировании нечто большее, чем просто значения данных). Продолжения по-прежнему более общие конструкции, поскольку они позволяют произвольно перемещаться между кадрами стека, а не всегда возвращаться в контекст вызывающей функции (как делает генератор).

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

Случайное блуждание

С целью пояснения, позвольте мне поставить довольно простую задачу, которую можно решить различными способами: как новыми, так и старыми. Предположим, мы хотим получить поток случайных чисел меньших единицы, которые подчиняются обратному ограничению. А именно, мы хотим, чтобы каждое следующее число было, по крайней мере, на 0.4 больше или меньше предыдущего. Более того, сам поток не бесконечен, а заканчивается после случайного числа шагов. Например, мы прервем его, как только появится число меньшее 0.1. Описанные ограничения несколько схожи с теми, что можно найти в алгоритме "случайного блуждания", причем условие окончания напоминает "локальный минимум", но, определенно, эти требования мягче, чем при решении реальных задач.

Python 2.1 или его более ранние версии предлагают несколько методов решения этой задачи. В данном случае будем просто создавать и отправлять список чисел в поток. Это может выглядеть следующим образом;


# RandomWalk_List.py #
import random
def randomwalk_list():
    # инициализация потенциальных элементов
    last, rand = 1, random.random()
    # пустой список
    nums = []
    # условие прерывания
    while rand > 0.1:
        # принятие числа
        if abs(last-rand) >= 0.4:
            last = rand
            # добавление последнего
            # элемента в nums
            nums.append(rand)
        else:
            # отображение отклонения
            print '*',
        # новый потенциальный элемент
        rand = random.random()
    # добавление последнего малого элемента
    nums.append(rand)
    return nums

Использовать эту функцию очень просто:


# Iterate over Random Walk List #
for num in randomwalk_list():
    print num,

Однако данный подход обладает ощутимыми ограничениями. Крайне маловероятно, что данный пример сгенерирует длинный список; но, сделав условие прерывания более жестким, мы могли бы создавать произвольно длинные потоки (их точный размер будет случайным, но порядок величин можно спрогнозировать). В определенный момент проблемы памяти и эффективности могут сделать этот подход неприемлемым и излишним. Именно эта проблема и вынудила добавить функции xrange() и xreadlines() в более ранние версии Python. Еще более существенно то, что многие потоки зависят от внешних событий, и все же они должны быть обработаны, когда каждый элемент доступен. Например, поток может слушать порт или ожидать ввода пользователя. В этих случаях создание полного списка из такого потока просто неприемлемо. Python 2.1 и более ранние версии предлагали еще один прием: можно было использовать "статическую" локальную переменную для запоминания информации о последнем вызове функции. Очевидно, глобальные переменные могли бы сделать то же самое, но они порождают хорошо знакомые проблемы: засоряют глобальное пространство имен и допускают ошибки, вызванные нелокальностью. Возможно, это вас удивит - если вы не знакомы с этой хитростью - в Python нет "официального" объявления статической области. Однако, если именованные параметры имеют изменяемые значения по умолчанию, они могут быть долговременными хранилищами предыдущих вызовов. Списки, в частности, удобные изменяемые объекты, которые могут содержать даже множественные значения.

Используя "статический" подход мы можем написать следующую функцию:


# RandomWalk_Static.py #
import random
# инициализация "статических" переменных
def randomwalk_static(last=[1]):
    # инициализация возможного результата
    rand = random.random()
    # условие прерывания
    if last[0] < 0.1:
        # признак конца потока
        return None
    # поиск приемлемого кандидата
    while abs(last[0]-rand) < 0.4:
         # отображение отклонения
         print '*',
         # новый кандидат
         rand = random.random()
    # обновить "статическую" переменную
    last[0] = rand
    return rand

Эта функция весьма некритична к памяти. Ей достаточно помнить только одно предыдущее значение, она возвращает всего лишь единственное число (а не длинный список чисел). Подобная функция могла бы вернуть следующую величину, зависящую (частично или полностью) от внешних событий. Недостаток этого подхода в том, что он несколько менее лаконичен и много менее элегантен.


# Iterate over Static Random Walk #
num = randomwalk_static()
while num is not None:
    print num,
    num = randomwalk_static()

Новый способ блуждания

"Под капотом" Python 2.2 все последовательности - итераторы. Знаменитая питоновская конструкция 'for elem in lst:' теперь фактически запрашивает lst для создания итератора. Цикл for будет затем последовательно вызывать метод .next() этого итератора, пока не достигнет исключения StopIteration. К счастью, программистам на Python не нужно знать, что происходит в этом месте, поскольку все встроенные типы генерируют свои итераторы автоматически. На самом деле, сейчас словари имеют методы .iterkeys(), .iteritems() и .itervalues() для создания итераторов; первый соответствует новой конструкции: 'for key in dct:'. Подобно этому, новая конструкция 'for line in file:' поддерживается итератором, вызывающим .readline().

Но зная, что фактически происходит внутри интерпретатора Python, становится очевидным, как использовать пользовательские классы, которые генерируют свои собственные итераторы, а не итераторы встроенных типов. Пример пользовательского класса, позволяющего напрямую использовать randomwalk_list(), а также экономный - по-элеметный -randomwalk_static, приведен ниже:


# RandomWalk_Iter.py #
import random
class randomwalk_iter:
    def __init__(self):
        # инициализация предыдущего значения
        self.last = 1
        # инициализация кандидата
        self.rand = random.random()
    def __iter__(self):
        # создание простейшего итератора
        return self
    def next(self):
        # условие прерывания
        if self.rand < 0.1:
            # конец итерации
            raise StopIteration
        # поиск приемлемого кандидата
        else:
            while \
            abs(self.last-self.rand)<0.4:
                # отображение отклонения
                print '*',
                # новый кандидат
                self.rand = random.random()
            # обновление предыдущего значения
            self.last = self.rand
            return self.rand

Применение этого пользовательского итератора аналогично использованию истинного списка, сгенерированного функцией:


# Iterate with Random Walk Class #
for num in randomwalk_iter():
    print num,

На самом деле, выполняется даже конструкция 'if elem in itetator', которая проверяет только столько элементов итератора, сколько нужно для определения истинности (конечно, если она выдаст "ложь", ей потребуется проверить все элементы).

Оставляя след из крошек

Изложенные выше подходы идеальны для решения данной задачи. Однако, ни один из не подходит, если в ходе выполнения программы создается огромное число локальных переменных, а сам код - паутина вложенных циклов и условий. В ситуации, когда класс итератора или функция со статическими (или глобальными) переменными зависит от состояния многочисленных переменных, возникают две проблемы. Первая - это насущная задача создания многочисленных атрибутов объекта или элементов статического списка для сохранения каждого значения данных. Но более важная задача - определить, как точно вернуться в релевантную часть логики потока, которая соответствует состоянию данных. Ведь очень легко позабыть о взаимодействии и взаимообусловленности различных данных.

Генераторы просто обходят всю эту проблему. Генератор "возвращает управление" новым ключевым словом yield, но "помнит" точную точку исполнения, где произошел возврат. При следующем вызове генератора, он начинается с того места, где его оставили до этого, - и в смысле хода исполнения функции, и в смысле значения переменных.

В Python 2.2 генераторы не пишутся непосредственно. Вместо этого пишется функция, возвращающая генератор при вызове. Это может показаться странным, но, поскольку "фабрика функций" является естественной возможностью Python, "фабрика генераторов" кажется ее очевидным концептуальным развитием. Благодаря наличию в теле функции одной или нескольких директив yield, она превращается в фабрику функций. Если в теле кода встречается директива yield, оператор return может встречаться только без возвращаемого значения. Однако лучше составить тело функции так, что исполнение просто "вывалилось с конца" после того, как все директивы yield будут выполнены. Но если встречается оператор return, то он заставляет созданный генератор возбудить исключение StopIteration, а не вернуть дальнейшие значения.

Мне кажется, что выбор подобного синтаксиса для создания фабрик генераторов не совсем оправдан. Директива yield легко может оказаться глубоко в теле функции, и в пределах первых N строк функции будет невозможно определить, является ли функция фабрикой генераторов. Разумеется, это справедливо и в отношении фабрики функций, но реализация фабрики функций не меняет существующий *синтаксис* тела функции (и допускается, что иногда тело функции может вернуть простую величину; хотя, возможно, не от хорошего дизайна). По-моему, новое ключевое слово - generator вместо def - было бы лучшим выбором.

Оставив в стороне полемику о лучшем синтаксисе, отметим, что генераторы могут работать автоматически как итераторы, когда их для этого вызывают. Для этого не требуется никаких методов классов вроде .__iter__(). Каждая директива yield становится возвращаемой величиной для метода .next() генератора. Простейший пример поясняет сказанное:


# Simplest Possible Python 2.2 Generator #
>>>from __future__ import generators
>>>def gen():
        yield 1

>>>g = gen()
>>>g.next()
1
>>>g.next()
Traceback (most recent call last):
  File "", line 1, in ?
    g.next()
StopIteration

Давайте задействуем генератор для решения обсуждавшийся выше задачи:


# RandomWalk_Generator.py #
# нужно только для Python 2.2
from __future__ import generators
import random
def randomwalk_generator():
    # инициализация потенциальных элементов
    last, rand = 1, random.random()
    # условие прерывания
    while rand > 0.1:
        # отображение отклонения
        print '*',
        # принятие числа
        if abs(last-rand) >= 0.4:
            # update предыдущего числа
            last = rand
            # возврат В ЭТОЙ ТОЧКЕ
            yield rand
        # новый потенциальный элемент
        rand = random.random()
    # возврат последнего малого элемента
    yield rand

Простота этого определения более чем привлекательна. Можно использовать этот генератор вручную, либо в качестве итератора. В первом случае генератор может передаваться в пределах программы и вызываться там, где он нужен, и тогда, когда это требуется (что весьма гибко). Простой пример ниже реализует этот случай:


# Manual use of Random Walk Generator #
gen = randomwalk_generator()
try:
    while 1: print gen.next(),
except StopIteration:
    pass

Однако, скорее всего генератор гораздо чаще будет использоваться в качестве итератора, что более компактно (и выглядит как старая добрая последовательность):


# Random Walk Generator as Interator #
for num in randomwalk_generator():
    print_short(num)

Выводы

Потребуется некоторое время, чтобы разработчики, пишущие на Python, освоились со всеми хитростями при использовании генераторов. Мощь, присущая этой простой конструкции, поразительна; я подозреваю, что даже опытные программисты (как разработчики самого Python) будут открывать новые тонкие аспекты применения генераторов.

В заключение, позвольте мне предложить вашему вниманию еще один пример, который можно найти в модуле test_generators.py дистрибутива Python 2.2. Предположим, у вас есть дерево, по всем узлам которого вы хотите пройти слева направо. Используя традиционные переменные состояния, достаточно сложно немедленно получить класс или функцию. Применение генератора делает выполнение этой задачи до смешного простым:


>>>> # A recursive generator that generates
     # Tree leaves in in-order.
>>> def inorder(t):
...    if t:
...        for x in inorder(t.left):
...            yield x
...        yield t.label
...        for x in inorder(t.right):
...            yield x


Ресурсы

Как и в случае с предыдущими версиями Python, Эндрю Качлинг (Andrew Kuchling) написал прекрасную статью о Python 2.2, описав новые возможности этой версии.




Исчерпывающее описание простых генераторов (Simple Generators) можно найти в проекте по развитию Python (Python Enhancement Proposal, PEP255):




Код примеров, которые были использованы в этой статье, можно отыскать в одном исходнике:




(Фотография автора:)

Поскольку постижение без интуиции бесплодно, а интуиция без постижения слепа, Дэйвид Мертц хочет литой бюст Джона Мильтона в свой офис. Запланируйте подарить ему на день рождения. Дэйвид доступен по адресу: mertz@gnosis.cx, а жизнь его описана на . Присылайте свои замечания и предложения касательно этой, прошлых или будущих статей.

Оригинальный текст статьи можно посмотреть здесь:




При перепечатке любого материала с сайта, видимая ссылка на источник www.warayg.narod.ru и все имена, ссылки авторов обязательны.

© 2005