Logo    
Деловая газета CitCity.ru CITKIT.ru - все об Open Source Форумы Все публикации Учебный центр Курилка
CitForum    CITForum на CD    Подписка на новости портала Море(!) аналитической информации! :: CITFORUM.RU
IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware

26.01.2017

Google
WWW CITForum.ru
С Новым годом!
2003 г

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

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

Функциональное программирование на 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; познакомьтесь с ней. Присылайте свои замечания и предложения касательно этой, прошлых или будущих статей.

Оригинальный текст статьи можно посмотреть здесь:
Using combinatorial functions in the itertools module

Подписка на новости IT-портала CITForum.ru
(библиотека, CITKIT.ru, CitCity)

Новые публикации:

24 декабря

CITKIT.ru:

  • Новогодние поздравления
  • Сергей Кузнецов. Цикл Операционные системы: Ностальгия по будущему:

  • Алексей Федорчук. OpenSolaris 2008.11 Release

  • Сергей Голубев:

  • Евгений Чайкин aka StraNNik (Блогометки):

    17 декабря

  • С.Д.Кузнецов. Базы данных. Вводный курс

    10 декабря

    CITKIT.ru:

  • OpenSolaris 2008.11 Release

  • Альтернативные ОС: две грустные истории (С.Кузнецов)
  • Nokia N810 — доведение до ума
  • CitCity:

  • Платформа 2009: заоблачные перспективы Microsoft

    4 декабря

  • Лекция С.Д.Кузнецова Понятие модели данных. Обзор разновидностей моделей данных

    CITKIT.ru:

  • OpenSolaris 2008.11 Release. Первые впечатления

  • Linux vs FreeBSD: продолжим "Священные войны"?

  • Nokia N810 as is

  • Индульгенция для FOSS

  • Друзья СПО'2008

    26 ноября

  • Нечеткое сравнение коллекций: семантический и алгоритмический аспекты

    CitCity:

    CITKIT.ru:

  • Глава из книги А.Федорчука
    Сага о FreeBSD:
  • 19 ноября

  • Проблемы экономики производства крупных программных продуктов

  • Язык модификации данных формата XML функциональными методами

    CITKIT.ru:

  • Главы из книги А.Федорчука
    Сага о FreeBSD:

    Заметки к книге:

  • FreeBSD: монтирование сменных устройств и механизм HAL
  • Текстовый редактор ee

    12 ноября

  • Правило пяти минут двадцать лет спустя, и как флэш-память изменяет правила (Гоц Грейф, перевод: Сергей Кузнецов)

    CITKIT.ru:

  • Главы из книги А.Федорчука
    Сага о FreeBSD:
  • OSS в России: взгляд правоведа (В.Житомирский)

  • Новая статья из цикла С.Голубева "Железный марш":

    29 октября

  • О некоторых задачах обратной инженерии

  • Веб-сервисы и Ruby

  • Тестирование web-приложений с помощью Ruby

    CITKIT.ru:

  • Главы из книги А.Федорчука
    Сага о FreeBSD:

  • PuppyRus Linux - беседа с разработчиком (С.Голубев)

  • Сергей Кузнецов. Заметка не про Linux

    22 октября

  • Обзор методов описания встраиваемой аппаратуры и построения инструментария кросс-разработки

    CITKIT.ru:

  • Сергей Кузнецов. Почему я равнодушен к Linux

  • Глава из книги А.Федорчука
    Сага о FreeBSD:
  • Что надо иметь
    3. Базовые познания

    CitCity:

  • Управление IT-инфраструктурой на основе продуктов Microsoft

    15 октября

  • Методы бикластеризации для анализа интернет-данных

    CitCity:

  • Разъемы на ноутбуках: что они дают и зачем их так много?
  • AMD Puma и Intel Centrino 2: кто лучше?

    CITKIT.ru:

  • Новый цикл статей С.Голубева
    Железный марш:

  • Главы из книги А.Федорчука
    Сага о FreeBSD:

    8 октября

  • Автоматизация тестирования web-приложений, основанных на скриптовых языках
  • Опыт применения технологии Azov для тестирования библиотеки Qt3

    Обзоры журнала Computer:

  • SOA с гарантией качества
  • Пикоджоуль ватт бережет
  • ICT и всемирное развитие

    CitCity:

  • Пиррова победа корпорации Microsoft

    CITKIT.ru:

  • Главы из книги А.Федорчука
    Сага о FreeBSD:

    Статья из архива:

  • Я живу в FreeBSD (Вадим Колонцов)

    Новые Блогометки:

  • Перекройка шаблона Blogger или N шагов к настоящему
  • Blogger. Comment style
  • Screenie или глянцевый снимок экрана

    2 октября

    CITKIT.ru:

  • Сага о FreeBSD (А. Федорчук)

    Zenwalk: пакет недели

  • Банинг — интеллектуальное развлечение (С.Голубев)

    CitCity:

    25 сентября

  • Клермонтский отчет об исследованиях в области баз данных

    CITKIT.ru:

  • Пользователям просьба не беспокоиться... (В.Попов)

  • Снова про ZFS: диск хорошо, а два лучше
  • Командная оболочка tcsh (А.Федорчук)

    Zenwalk: пакет недели

    17 сентября

  • T2C: технология автоматизированной разработки тестов базовой функциональности программных интерфейсов
  • Технология Azov автоматизации массового создания тестов работоспособности

    CITKIT.ru:

  • FreeBSD: ZFS vs UFS, и обе-две — против всех (А.Федорчук)

    Zenwalk: пакет недели

  • Дачнет — практика без теории (С.Голубев)

    10 сентября

  • За чем следить и чем управлять при работе приложений с Oracle
  • Планировщик заданий в Oracle
    (В.Пржиялковский)

    CITKIT.ru:

  • Microsoft: ответный "боян" (С.Голубев)

  • Причуды симбиоза, или снова "сделай сам" (В.Попов)

  • Файловые системы современного Linux'а: последнее тестирование
  • Zsh. Введение и обзор возможностей
    (А.Федорчук)

    Описания пакетов Zenwalk: Zsh, Thunar, Thunar-bulk-rename, Xfce4-places-plugin, Xfce4-fsguard-plugin

    Блогометки:

  • Google Chrome
  • Лончер для ASUS Eee PC 701

    3 сентября

    CITKIT.ru:

  • Заметки о ядре (А.Федорчук):

    Добавлены описания пакетов Zenwalk: Galculator, Screenshot, Gnumeric, Pidgin

    В дискуссинном клубе:

  • И еще о Википедии и Google Knol

  • Лекция для начинающего линуксоида (С.Голубев)

    26 августа

  • Транзакционная память (Пересказ: С. Кузнецов)

    CITKIT.ru:

  • Открыт новый проект Zenwalk: пакет недели

  • Статья Текстовые процессоры и их быстродействие: конец еще одной легенды?

    21 августа

    CITKIT.ru:

  • Почему школам следует использовать только свободные программы (Ричард Столлман)
  • Беседа Сергея Голубева с учителем В.В.Михайловым

  • Википедия или Гуглезнание? Приглашение к обсуждению (Алексей Федорчук)
  • Народная энциклопедия от Google (StraNNik)

  • Обзор Mandriva 2009.0 Beta 1 Thornicrofti
  • Новичок в Линукс: Оптимизируем Mandriva 2008.1

  • Книга Zenwalk. Приобщение к Linux:

    13 августа

    CitCity:

  • Мирный Atom на службе человеку. Обзор платы Intel D945GCLF с интегрированным процессором
  • Обзор процессоров Intel Atom 230 на ядре Diamondville

  • iPhone - год спустя. Скоро и в России?

    CITKIT.ru:

  • Интермедия 3.4. GRUB: установка и настройка (из книги Zenwalk. Приобщение к Linux)

    6 августа

  • СУБД с хранением данных по столбцами и по строкам: насколько они отличаются в действительности? (Пересказ: С. Кузнецов)

    CITKIT.ru:

  • Интермедия 2.2. Что неплохо знать для начала (из книги Zenwalk. Приобщение к Linux)

  • И снова про шрифты в Иксах (А.Федорчук)

  • 20 самых быстрых и простых оконных менеджеров для Linux

  • Дело о трех миллиардах (С.Голубев)

    30 июля

  • OLTP в Зазеркалье (Пересказ: С. Кузнецов)

    CitCity:

  • Будущее BI в облаках?
  • Тиражные приложения и заказная разработка. Преимущества для заказчика
  • Дискуссия со сторонниками заказной разработки

    CITKIT.ru:

  • Новые главы книги Zenwalk. Приобщение к Linux:
  • Глава 8. Пакеты: средства установки, системы управления, системы построения
  • Глава 9. Zenwalk: репозитории, пакеты, методы установки

    23 июля

    CITKIT.ru:

  • Все против всех. 64 vs 32, Intel vs AMD, tmpfs vs ext3
  • Две головы от Intel

  • Zenwalk: обзор штатных приложений (глава из книги "Zenwalk. Приобщение к Linux")

  • Нормально, Григорий...

    16 июля

    Обзоры журнала Computer:

  • Перспективы и проблемы программной инженерии в XXI веке
  • Большие хлопоты с большими объемами данных
  • Перспективы наноэлектроники

    CITKIT.ru:

  • Интермедия о лицензиях (А.Федорчук. "Zenwalk. Приобщение к Linux")

  • Есть ли будущее у KDE?

  • Linux в школе: альтернативный вариант в задачах

  • Шифр (приключения агента Никодима)

    10 июля

    CITKIT.ru:

  • Новые разделы книги А. Федорчука Zenwalk. Приобщение к Linux:
  • Интермедия вступительная. Linux или GNU/Linux? Как вас теперь называть?
  • Глава 5. Среда Xfce
  • Глава 6. Xfce: приложения и плагины

  • ZUR (Zenwalk User Repository) FAQ

    2 июля

  • Персистентность данных в объектно-ориентированных приложениях (С. Кузнецов)

    CITKIT.ru:

  • Новые разделы книги А. Федорчука Zenwalk. Приобщение к Linux:
  • Интермедия 1.2. Дорога к Zenwalk'у. Период бури и натиска
  • Интермедия 3.3. Немного о Linux'е и "железе"
  • Глава 4. Настройка: инструментами и руками
  • Интермедия 4.1. Zenpanel и конфиги: поиски корреляции

  • Интервью с Жан-Филиппом Гийоменом, создателем дистрибутива Zenwalk

  • Linux в школе: первые итоги (С. Голубев)

    25 июня

    CITKIT.ru:

  • Zenwalk. Приобщение к Linux (А. Федорчук)

  • Логика и риторика (С.Голубев)

  • Технология Tru64 AdvFS

  • Ханс Райзер предлагает отвести полицейских к телу Нины

    18 июня

  • Проекты по управлению данными в Google (Пересказ: С. Кузнецов)

    CITKIT.ru:

  • ОС и поддержка "железа": мифы и реальность (А. Федорчук)

  • Linux в школе: другие дистрибутивы

  • Пинок (С. Голубев)

    4 июня

  • Ландшафт области управления данными: аналитический обзор (С. Кузнецов)

    CITKIT.ru:

  • Linux в школе: слово заинтересованным лицам

  • SlackBuild: пакеты своими руками

  • Linux от компании Novell. Установка и обзор openSUSE Linux

    Все публикации >>>




  • IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware

    Информация для рекламодателей Пресс-релизы — pr@citcity.ru
    Послать комментарий
    Информация для авторов
    Rambler's Top100 This Web server launched on February 24, 1997
    Copyright © 1997-2017 CIT, © 2001-2017 CIT Forum
    Внимание! Любой из материалов, опубликованных на этом сервере, не может быть воспроизведен в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Подробнее...