Очаровательный Python

Изящество и неловкость Python. Часть 1

Последовательности и сравнения

Comments

Серия контента:

Этот контент является частью # из серии # статей: Очаровательный Python

Следите за выходом новых статей этой серии.

Этот контент является частью серии:Очаровательный Python

Следите за выходом новых статей этой серии.

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

Проклятие упорядочений

При переходе с Python 2.0 на Python 2.1 произошла загадочная вещь. Сравнимые в прошлом объекты в новой версии при сравнении вызывали исключения. В частности, стало невозможным сравнение комплексных чисел как с другими комплексными (тип complex), так и с действительными (типы int, float и long) числами. В действительности эта проблема появлялась и ранее, при сравнении обычиных и Unicode-строк, но только в некоторых особых случаях.

По моему мнению, это - неудачное и просто очень странное изменение. В старой доброй версии 1.5.2 я был уверен, что оператор неравенства возвратит какое-либо значение вне зависимости от типов сравниваемых объектов. Конечно, зачастую смысла в этом результате не было (нельзя сравнивать строку с числом), но по крайней мере это был результат.

После внесения изменений некоторые адепты Python завели спор о том, что правильно было бы наложить запрет на любые сравнения объектов разных типов - по крайней мере при отсутствии явно определенных операторов сравнения. Мне кажется, что при наличии пользовательских классов и множественного наследования этот вариант вызовет сильные затруднения. К тому же было бы крайне неудобно не иметь возможности сравнивать друг с другом float, int или long (или, скажем, decimal). Хотя, возможно, разумное решение существует.

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

Листинг 1. Возможность сравнения зависит и от типа, и от значения
>>> map(type, (u1, s1, s2))
[<type 'unicode'>, <type 'str'>, <type 'str'>]

>>> u1 < s1
True

>>> s1 < s2
True

>>> u1 < s2
UnicodeDecodeError: 'ascii' codec can't decode byte 0xf0 in position 0:
    ordinal not in range(128)

>>> map(type, (n, j, u1))
[<type 'int'>, <type 'complex'>, <type 'unicode'>]

>>> n < u1
True

>>> j < u1
True

>>> n < j
TypeError: no ordering relation is defined for complex numbers

В качестве особо утонченного издевательства, несмотря на то, что комплексные числа теперь несравнимы с большинством других численных типов, операторы неравенства тем не менее возвращают вполне определенное значение при сравнении с большинством нечисленных типов. Я понимаю, что "чистая" теория утверждает, что 1+1j, например, не меньше и не больше 2-3j, но как тогда следует понимать это:

Листинг 2. "Сюрпризы" при сравнении
>>> 2-3j < 'spam'
True

>>> 4+0j < decimal.Decimal('3.14')
True

>>> 4+0j < 5+0j
TypeError: no ordering relation is defined for complex numbers

С точки зрения "чистой" теории ни одно из этих сравнений недопустимо.

Чудеса клоунады: сортировка гетерогенных последовательностей

Иногда заходит спор о том, корректно ли сравнивать экземпляры несопоставимых типов. Но Python с легкостью производит подобные сравнения, и это хорошо соотносится с принципом "duck typing" (судить об объекте не по его типу, а по его поведению). Коллекции в Python часто состоят из объектов различных типов, в предположении, что удастся сделать что-либо похожее с каждым из объектов. Частый пример такого действия - кодирование нескольких абсолютно различных по типу объектов для передачи по внешним каналам.

Для большинства подобных действий не требуется определять отношения неравенства. Однако есть один очень частый случай, когда наличие сравнений оказывается крайне полезным: сортировка, обычно для списков (lists) или аналогичных пользовательских типов. Зачастую необходимо обрабатывать коллекцию в осмысленном порядке (например, просматривать данные от меньших элементов к большим). Иногда же требуется просто определить жесткий порядок элементов в нескольких коллекциях (например, чтобы определить различия между ними). В таких случаях может понадобиться выполнять одни действия, когда объект содержится в обоих списках, и другие, когда он находится только в одной из коллекций. Вызов if x in otherlist для каждого элемента приволит к степенному увеличению сложности вычислений; параллельный просмотр двух отсортированных списков значительно эффективнее. Например:

Листинг 3. Выполнение различных действий в зависимости от вхождения элемента в два списка
list1.sort()
list2.sort()
list2_xtra = []
list2_ndx = 0
for it1 in list1:
    it2 = list2[list2_ndx]
    while it1 < it2:
        list2_ndx += 1
        it2 = list2[list2_ndx]
        if it1 == it2:
            item_in_both(it1)
        elif it1 > it2:
            item_in_list1(it1)
        else:
            list2_xtra.appen(it2)
 for it2 in list2_xtra:
     item_in_list2(it2)

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

Проблемы сортировки

Естественно, приведенный выше алгоритм зачастую вызывает ошибки, причем практически случайным образом. Например, вот небольшой набор списков, которые могут встретиться в подобной программе в роли list1 и list2. Попробуйте догадаться, какие из них отсортируются:

Листинг 4. Винегрет из сортируемых и несортируемых списков
['x','y','z', 1],
['x','y','z', 1j],
['x','y','z', 1j, 1],       # Adding an element makes it unsortable
[0j, 1j, 2j],               # An obvious "natural" order
[0j, 1, 2],
[0, 1, 2],                  # Notice that 0==0j --> True
[chr(120), chr(240)],
[chr(120), chr(240), 'x'],
[chr(120), chr(240), u'x'], # Notice u'x'=='x' --> True
[u'a', 'b', chr(240)],
[chr(240), u'a', 'b']       # Same items, different initial order

Я написал небольшую программу, которая пытается отсортировать каждый список:

Листинг 5. Результаты сортировки
% python compare.py
(0)  ['x', 'y', 'z', 1] --> [1, 'x', 'y', 'z']
(1)  ['x', 'y', 'z', 1j] --> [1j, 'x', 'y', 'z']
(2)  ['x', 'y', 'z', 1j, 1] --> exceptions.TypeError
(3)  [0j, 1j, 2j] --> exceptions.TypeError
(4)  [0j, 1, 2] --> exceptions.TypeError
(5)  [0, 1, 2] --> [0, 1, 2]
(6)  ['x', '\xf0'] --> ['x', '\xf0']
(7)  ['x', '\xf0', 'x'] --> ['x', 'x', '\xf0']
(8)  ['x', '\xf0', u'x'] --> exceptions.UnicodeDecodeError
(9)  [u'a', 'b', '\xf0'] --> [u'a', 'b', '\xf0']
(10) ['\xf0', u'a', 'b'] --> exceptions.UnicodeDecodeError

Часть полученных результатов следует из ранее описанных проблем. Однако обратите внимание на списки (9) и (10), которые содержат одни и те же элементы в разном порядке: успех сортировки зависит не только от типов и значений элементов, но и от деталей конкретной реализации list.sort()!

Устраняем проблемы сравнения

После версии 1.5.2 в Python появился очень полезный тип данных: множества (sets), сначала как стандартный модуль, а впоследствии и во встроенном варианте (хотя некоторые дополнительные возможности по-прежнему вынесены в модуль). Во многих аналогичных только что описанным случаях для получения объединения или пересечения достаточно вместо того, чтобы писать собственные программы сравнения, просто использовать вместо списков (lists) множества (sets). Например:

Листинг 6. Множества и операции на них
>>> set1 = set([1j, u'2', 3, 4.0])

>>> set2 = set([4, 3, 2, 1])

>>> set1 | set2
set([3, 1, 2, 1j, 4.0, u'2'])

>>> set1 & set2
set([3, 4])

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

Листинг 7. Странные результаты операций над множествами
>>> set2 & set1
set([3, 4.0])

>>> set([3, 4.0, 4, 4+0j])
set([3, 4.0])

Все же в первом приближении множества очень полезны. Тем не менее стоит помнить о возможности обойти проблему при помощи собственных функций сравнения. В Python до версии 2.4 была возможность определить собственную функцию сравнения cmp() и передать ее методу list.sort(). Такой способ позволял определить сравнение для объектов, которые иначе сравнить было нельзя; однако проблема аргумента cmp() - в том, что его приходится вызывать при каждом сравнении: в Python вызов функции - довольно дорогостоящая операция. Более того, в конце концов оказывалось, что для некоторых пар элементов значения функции сравнения вычисляются несколько раз.

Решением проблемы неэффективности использования cmp может послужить преобразование Шварца (Schwartzian Transform): сначала создать для каждого элемента сортируемую оболочку, отсортировать и убрать оболочки. К сожалению, для этого потребуется написание дополнительного кода (помимо самого вызова list.sort(). ). Python 2.4 предлагает хорошее решение этой проблемы с использованием нового аргумента key. Его значением должна быть функция, возвращающая оболочку с объектом; таким образом, детали преобразования Шварца остаются невидимыми для программиста. Помня, что комплексные числа несравнимы даже друг с другом, в то время как строки Unicode вызывают ошибки только при сравнении с некоторыми обычными строками, можно написать:

Листинг 8. Стабильный и универсальный алгоритм сортировки
def stablesort(o):
    # Use as: mylist.sort(key=stablesort)
    if type(o) is complex:
        return (type(o), o.real, o.imag)
    else:
        return (type(o), o)

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

Генераторы как "не вполне последовательности"

В своем развитии Python значительно увеличивал ориентированность на итераторы (laziness). Уже в нескольких последних версиях языка есть возможность определения генераторов при помощи ключевого слова yield в функции. Также при развитии языка появился модуль itertools для операций над итераторами. В языке есть встроенная функция iter() для получения итераторов на последовательностях. В Python 2.4 появились выражения-генераторы (generator expressions), а в версии 2.5 появились расширенные генераторы, облегчающие написание сопрограмм. Многие объекты Python стали поддерживать итерирование; например, режим чтения файлов, требовавший вызова .xreadlines() (ранее модуля xreadlines ), теперь реализован по умолчанию в самом конструкторе open().

Итерирование по dict ранее требовало использования метода .iterkeys(); теперь того же результата можно добиться, просто написав for key in dct. Функции, подобные xrange(), необычны тем, что, с одной стороны, возвращают генератор, но, с другой стороны, это не совсем "правильный" итератор (нет метода .next()), но и не полнофункциональный список вроде возвращаемого range() . В то же время enumerate() возвращает "настоящий" генератор - то, для чего ранее использовался конструктор xrange(). А itertools.count() - еще одна функция с отложенным вычислением, делающая почти то же самое, что и xrange(), но возвращающая полнофункциональный итератор.

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

Проблема заключается в некоторой "шизофреничности" Python в том, что касается сходств и различий между "настоящими" последовательностями и итераторами. Основная сложность в том, что такой подход нарушает принцип "duck typing" - возможность работать с объектом до тех пор, пока он правильно воспринимает запросы, не налагая каких-либо ограничений на его тип. Многие итераторы (или другие подобные объекты) иногда работают как последовательности, а иногда нет, и наоборот: последовательности могут вести себя как итераторы, но не всегда. Такое поведение может быть далеко не очевидно для находящихся вне узкого круга погруженных в священные таинства Python.

Различия

Главное общее свойство и итераторов, и последовательностей - в том, что каждый из них поддерживает собственно итерирование по себе - с использованием ли цикла for, списочных выражений (list comprehensions) или генераторных выражений (generator comprehensions). Дальше начинаются различия. Наиболее важное из них - то, что последовательности поддерживают индексацию, а итераторы - нет. Но индексация - это, наверное, главное, что можно сделать с последовательностью - почему же итераторы настолько бесповоротно отказываются от нее? Например:

Листинг 9. Последовательности и итераторы
>>> r = range(10)

>>> i = iter(r)

>>> x = xrange(10)

>>> g = itertools.takewhile(lambda n: n<10, itertools.count())

#...etc...

Для каждого из данных объектов можно написать for n in thing. И если "конкретизировать" какой-либо из них при помощи list(thing), результат будет одинаков для всех. Но если вам нужно получить определенный элемент (или несколько), придется вспомнить точный тип объекта thing. Например:

Листинг 10. Успех и ошибки индексации
>>> r[4]
4

>>> i[4]
TypeError: unindexable object

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

Листинг 11. Эмулируем индексирование
>>> thing, temp = itertools.tee(thing)

>>> zip(temp, '.'*5)[-1][0]
4

Предварительный вызов itertools.tee() сохраняет исходный итератор неизменным. Чтобы получить несколько элементов, можно использовать функцию itertools.islice() и некоторое количество дополнительного кода.

Листинг 12. Достаем несколько элементовe
>>> r[4:9:2]
[4, 6, 8]

>>> list(itertools.islice(r,4,9,2))  # works for iterators
[4, 6, 8]

Класс-оболочка

Для удобства приведенные процедуры можно объединить в класс-оболочку:

Листинг 13. Индексация на итераторах
>>> class Indexable(object):
...     def __init__(self, it):
...         self.it = it
...     def __getitem__(self, x):
...         self.it, temp = itertools.tee(self.it)
...         if type(x) is slice:
...             return list(itertools.islice(self.it, x.start, x.stop, x.step))
...         else:
...             return zip(temp, range(x+1))[-1][0]
...     def __iter__(self):
...         self.it, temp = itertools.tee(self.it)
...         return temp
...

>>> integers = Indexable(itertools.count())

>>> integers[4]
4
>>> integers[4:9:2]
[4, 6, 8]

При некотором желании можно заставить объект работать и как последовательность, и как итератор. Но количество усилий, которое для этого требуется, неоправданно велико; индексирование должно бы "просто" работать, вне зависимости от того, используется ли оно для последовательности или для итератора.

Следует заметить, что оболочка Indexable не так хороша, как хотелось бы. Основной недостаток в том, что каждый раз приходится создавать новую копию итератора. Другой, более быстрый вариант - кэшировать начало последовательности при извлечении блоков и впоследствии использовать его для быстрого доступа к уже просмотренным элементам. Конечно, следует соблюдать баланс между объемом используемой памяти и издержками на итерирование. Тем не менее было бы лучше, если бы все это уже было реализовано в самом Python - адепты языка могут заниматься оптимизацией, но среднестатистичесикй программист не должен об этом думать.

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


Ресурсы для скачивания


Похожие темы

  • Оригинал статьи Python elegance and warts, Part 1. (EN)
  • Ознакомьтесь с последней версией latest Gnosis Utilities Дэвида Мертца -- включая добавленные в версии 1.2.0 инструменты для работы с Unicode его соавтора Фрэнка Мак-Ингвейла (Frank McIngvale). (EN)
  • All About Python and Unicode... and even more about Unicode (EN) (Все о Python и Unicode... и еще о Unicode) - эссе Фрэнка Мак-Ингвейла, соавтора Дэвида в работе над Gnosis Utilities. В этой замечательной работе Фрэнк рассматривает проблемы совместного использования Python и Unicode, включая причины для добавления в Gnosis Utilities некоторых расширенных средств обработки Unicode.(EN)
  • Обратите внимание на другие ресурсы для Linux-разработчиков в разделе Linux сайта developerWorks.
  • Используйте в своей следующей разработке для Linux ознакомительное ПО от IBM, которое можно загрузить непосредственно с сайта developerWorks.(EN)

Комментарии

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

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=40
Zone=Linux, Open source
ArticleID=277997
ArticleTitle=Очаровательный Python: Изящество и неловкость Python. Часть 1
publish-date=12182007