Журнал ВРМ World

Мировая история развития технологий управления эффективностью бизнеса – обзоры зарубежных публикаций

Использование комбинаторных функций в модуле itertools

В конце июля произошло знаменательное событие: вышла версия 2.3 популярного
языка программирования Python. О новом модуле itertools и его возможностях
расскажет наш старый знакомый Дэвид Мертц.

Функциональное программирование на Python стало отложенным

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

Объяснение новой концепции

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

Привлекательность итераторов объясняется двумя причинами. Работа с данными как последовательностями - часто наиболее простой подход, а последовательность, обрабатываемая в линейном порядке, на самом деле зачастую не должна существовать вся сразу.

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

Большую часть времени итератор используется в цикле for точно так же, как и истинная последовательность. Итераторы предоставляют метод .next(), который может быть явно запущен, но в 99% времени то, что вы увидите - это что-нибудь вроде:


for x in iterator:
    do_something_with(x)

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

Питоновское прогрессирующее раздвоение личности

В отношении Python к функциональному программированию есть что-то шизофреническое. С одной стороны, многие разработчики Python недооценивают традиционные функции функционального программирования: map(), filter() и reduce() - обычно рекомендуя использовать вместо них списочные включения (list comprehensions). Но весь модуль itertools составлен из функций точно такого же вида и просто оперирует над "отложенными последовательностями" (итераторами), а не над законченными последовательностями (списками, кортежами). Более того, в Python 2.3 отсутствует синтаксис для "итераторных включений" (iterator comprehensions), которые казалось бы имеют те же мотивы, что и списочные включения.

Я подозреваю, что Python в конечном счёте разовьет некую форму итераторных включений, но это зависит от нахождения подходящего естественного синтаксиса для них. Между тем, у нас имеется ряд удобных комбинаторных функций в модуле itertools. Вообще каждая из этих функций принимает некоторые параметры (обычно включая некоторые базовые итераторы) и возвращает новый итератор. Например, функции ifilter(), imap() и izip() полностью эквивалентны соответствующим встроенным функциям, у которых отсутствует начальное i.

Отсутствующие эквиваленты

В itertools нет ireduce(), хотя это могло бы показаться естественным; возможная Питоновская реализация такова:

Листинг 1. Пример реализации ireduce()

def ireduce(func, iterable, init=None):
    if init is None:
        iterable = iter(iterable)
        curr = iterable.next()
    else:
        curr = init
    for x in iterable:
        curr = func(curr, x)
        yield curr

Случай использования ireduce() подобен варианту с reduce(). Например, предположим, что вы хотите суммировать список чисел, находящихся в большом файле, но остановиться, когда выполняется условие. Вы могли бы контролировать текущий итог с помощью:

Листинг 2. Добавление списка чисел и подведение итога

from operator import add
from itertools import *
nums = open('numbers')
for tot in takewhile(condition, ireduce(add, imap(int, nums)):
    print "total =", tot

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

Фабрики базовых итераторов

Все функции в модуле itertools могут быть легко реализованы на чистом Python как генераторы. Основной смысл этого модуля в Python 2.3+ - обеспечить стандартное поведение и имена для некоторых полезных функций. Хотя программисты могли бы написать свои собственные версии, на практике каждый создал бы слегка несовместимые вариации. Помимо этого, еще одна причина - эффективная реализация итераторных комбинаторов на С. Использование функций itertools будет заметно быстрее, чем написание своих собственных комбинаторов. В стандартной документации показаны эквивалентные реализации на чистом Python для каждой функции itertools, так что нет необходимости повторять их в этой статье.

Функции в модуле itertools настолько базовые - и достаточно четко поименованные - что, вероятно, имеет смысл импортировать все имена из этого модуля. Функция enumerate(), например, вполне могла бы существовать в itertools, но вместо этого является встроенной функцией в Python 2.3+. В частности, вы можете легко выразить enumerate() в терминах функций itertools:


from itertools import *
enumerate = lambda iterable: izip(count(), iterable)

Давайте рассмотрим несколько функций itertools, которые не используют другие итераторы в качестве базиса, а просто создают итераторы "с нуля". times() возвращает итератор, который выдает идентичный объект множество раз; сама по себе эта возможность довольно удобна, но по-настоящему она хороша при избыточном использовании xrange() и индексной переменной для простого повторения действия. То есть вместо:


for i in xrange(1000):
    do_something()

Вы можете теперь использовать более нейтральное:


for _ in times(1000):
    do_something()

Если второй аргумент не передается в times(), она просто повторно выдает None. Функция repeat() подобна times(), но неограниченно возвращает тот же самый объект. Этот итератор удобен либо если у цикла имеется независимое условие break, либо в комбинаторах, как izip() и imap().

Функция count() похожа на помесь repeat() и range(). count() неограниченно возвращает последовательно идущие целые (начиная с факультативного аргумента). Однако, с учетом того, что в настоящий момент count() корректно не поддерживает автоматическое преобразование к long при переполнении, вы могли бы с равным успехом по-прежнему использовать xrange(n,sys.maxint); она не является неограниченной буквально, но для большинства целей приводит к тому же. Как и repeat(), count() особенно удобна в других итераторных комбинаторах.

Комбинаторные функции

Несколько реальных комбинаторных функций в itertools уже были вскользь упомянуты. ifilter(), izip() и imap() ведут себя именно так, как следовало бы ожидать от соответствующих функций над последовательностями. ifilterfalse() - вспомогательная функция, так что вам не нужно инвертировать предикатную функцию в lambda и def (и это значительно экономит накладные расходы на вызов функции). Но функционально вы могли бы определить ifilterfalse() (приблизительно, игнорируя предикат None) как:


def ifilterfalse(predicate, iterable):
    return ifilter(lambda predicate: not predicate, iterable)

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

Функция islice(), по существу, просто итераторная версия среза списка. Вы можете задать начало, останов и шаг, как с регулярными срезами. Если начало задано, ряд элементов отбрасывается, пока передаваемый итератор не достигнет требуемого элемента. Это еще один случай, когда, как я думаю, возможно усовершенствовать Python - самое лучшее для итераторов было бы просто распознать разрезы, как делают списки (в качестве синонима того, что делает islice()).

Последняя функция starmap() - это легкая вариация imap(). Если функция, которая передается как аргумент, принимает набор аргументов, переданный итератор должен выдавать кортежи надлежащего размера. По существу, это то же самое, что и imap() с несколькими передаваемыми итерируемыми аргументами, только с набором итерируемых аргументов, предварительно комбинированных izip().

Больше чем основы

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

Одна категория, которая могла бы в общем показаться полезной- это функции, принимающие набор итерируемых аргументов, затем выдающие отдельные элементы из каждого итерируемого аргумента. В противоположность этому, izip() выдает кортежи элементов, а imap() выдает значения, вычисленные из основных элементов. Два очевидных решения, по моему мнению, это chain() и weave(). Первая функция, по существу, подобна конкатенации последовательностей (уместно отложенной). То есть где для простых последовательностей вы использовали бы, например:


for x in ('a','b','c') + (1, 2, 3):
    do_something(x)

для обычных итерируемых аргументов вы могли бы использовать:


for x in chain(iter1, iter2, iter3):
    do_something(x)

Питоновская реализация такова:

Листинг 3. Пример реализации chain()

for x in chain(iter1, iter2, iter3):
    do_something(x)

Вы также могли бы комбинировать итераторы, перемежая их. Встроенный синтаксис, чтобы сделать то же самое с последовательностями, отсутствует, однако сама weave() также прекрасно работает для конечных последовательностей. Возможная реализация приведена ниже (Магнус Лай Хетленд (Magnus Lie Hetland) привел похожую функцию на comp.lang.python):

Листинг 4. Пример реализации weave()

def weave(*iterables):
    "Intersperse several iterables, until all are exhausted"
    iterables = map(iter, iterables)
    while iterables:
        for i, it in enumerate(iterables):
            try:
                yield it.next()
            except StopIteration:
                del iterables[i]

Позвольте мне проиллюстрировать поведение weave(), поскольку оно может быть не сразу очевидно из этой реализации:


>>> for x in weave('abc', xrange(4), [10,11,12,13,14]):
...    print x,
...
a 0 10 b 1 11 c 2 12 13 3 14

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

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

Ниже - возможная реализация icompose():

Листинг 5. Пример реализации icompose():

def icompose(functions, initval):
    currval = initval
    for f in functions:
        currval = f(currval)
        yield currval

Заключение

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

Ресурсы

Об авторе

Хотя Дэвиду Мертцу нравятся надменность и нетерпение, эта статья о лености. Дэвид доступен по адресу: mertz@gnosis.cx, а жизнь его описана на его личной Web-странице. Его книга "Текстовая обработка в Python (Text Processing in Python) была недавно опубликована в издательстве Addison-Wesley; познакомьтесь с ней. Присылайте свои замечания и предложения касательно этой, прошлых или будущих статей.

Автор: Дэвид Мертц (David Mertz), разработчик, Gnosis Software, Inc.