HOWTO по сортировке¶

Автор:	Andrew Dalke and Raymond Hettinger
Релиз:	0.1

Списки Python имеют встроенный list.sort() метод, который изменяет список на месте. Существует также встроенная функция sorted(), которая создает новый отсортированный список из итерируемого.

В этом документе рассматриваются различные методы сортировки данных с использованием Python.

Основы сортировки¶

Простая сортировка по возрастанию очень проста: просто вызовите функцию sorted(). Возвращает новый отсортированный список:

>>> sorted([5, 2, 3, 1, 4])
[1, 2, 3, 4, 5]

Также можно использовать list.sort() метод. Он изменяет список на месте (и возвращает None, чтобы избежать путаницы). Обычно это менее удобно, чем sorted(), но если вам не нужен первоначальный список, он немного эффективнее.

>>> a = [5, 2, 3, 1, 4]
>>> a.sort()
>>> a
[1, 2, 3, 4, 5]

Другое отличие заключается в том, что list.sort() метод определяется только для списков. В противоположность этому функция sorted() принимает любые итерируемые.

>>> sorted({1: 'D', 2: 'B', 3: 'B', 4: 'E', 5: 'A'})
[1, 2, 3, 4, 5]

Ключевые функции¶

И list.sort(), и sorted() содержат параметр key для указания функции, которая должна вызываться в каждом элементе списка перед проведением сравнений.

Например, вот не чувствительное к регистру сравнение строки:

>>> sorted("This is a test string from Andrew".split(), key=str.lower)
['a', 'Andrew', 'from', 'is', 'string', 'test', 'This']

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

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

>>> student_tuples = [
...     ('john', 'A', 15),
...     ('jane', 'B', 12),
...     ('dave', 'B', 10),
... ]
>>> sorted(student_tuples, key=lambda student: student[2])   # sort by age
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

Та же техника работает для объектов с именем атрибуты. Для примера:

>>> class Student:
...     def __init__(self, name, grade, age):
...         self.name = name
...         self.grade = grade
...         self.age = age
...     def __repr__(self):
...         return repr((self.name, self.grade, self.age))

>>> student_objects = [
...     Student('john', 'A', 15),
...     Student('jane', 'B', 12),
...     Student('dave', 'B', 10),
... ]
>>> sorted(student_objects, key=lambda student: student.age)   # sort by age
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

Функции модуля operator¶

Показанные выше шаблоны «ключ-функция» очень распространены, поэтому Python обеспечивает удобные функции для упрощения и ускорения функций доступа. Модуль operator содержит функции itemgetter(), attrgetter() и methodcaller().

Используя эти функции, вышеприведённые примеры становятся проще и быстрее:

>>> from operator import itemgetter, attrgetter

>>> sorted(student_tuples, key=itemgetter(2))
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

>>> sorted(student_objects, key=attrgetter('age'))
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

Функции модуля operator позволяют выполнять сортировку на нескольких уровнях. Например, сортировать по grade, а затем по age:

>>> sorted(student_tuples, key=itemgetter(1,2))
[('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]

>>> sorted(student_objects, key=attrgetter('grade', 'age'))
[('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]

По возрастанию и убыванию¶

И list.sort(), и sorted() принимают параметр reverse с логическим значением. Это - используемый к видам спуска флага. Например, чтобы получить студенческие данные обратный порядок возрастов:

>>> sorted(student_tuples, key=itemgetter(2), reverse=True)
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]

>>> sorted(student_objects, key=attrgetter('age'), reverse=True)
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]

Стабильность сортировки и сложные сортировки¶

Сортировка гарантированно должна быть стабильной. Это означает, что если несколько записей имеют один и тот же ключ, их исходный порядок сохраняется.

>>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)]
>>> sorted(data, key=itemgetter(0))
[('blue', 1), ('blue', 2), ('red', 1), ('red', 2)]

Обратите внимание, как две записи для blue сохраняют свой исходный порядок, чтобы ('blue', 1) гарантированно предшествовал ('blue', 2).

Это замечательное свойство позволяет строить сложные сортировки в серии шагов сортировки. Например, чтобы сортировать студенческие данные, спускаясь по grade и затем поднимаясь на age, сделайте вид age сначала и затем вид, снова используя grade:

>>> s = sorted(student_objects, key=attrgetter('age'))     # сортировка по вторичному ключу
>>> sorted(s, key=attrgetter('grade'), reverse=True)       # теперь сортировка по первичному ключу, по убыванию
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

Это можно абстрагировать в функцию-обёртку, которая может взять список и кортежи поля и приказать сортировать их по нескольким проходам.

>>> def multisort(xs, specs):
...     for key, reverse in reversed(specs):
...         xs.sort(key=attrgetter(key), reverse=reverse)
...     return xs

>>> multisort(list(student_objects), (('grade', True), ('age', False)))
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

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

Старый способ использования декорирование-сортировка-раздекорирование¶

Эта идиома называется декорирование-сортировка-раздекорирование после трех ее шагов:

Сначала исходный список украшается новыми значениями, которые управляют порядком сортировки.
Во-вторых, отсортирован декорированный список.
Наконец, декорации удаляются, создавая список, содержащий только начальные значения в новом порядке.

Например, чтобы сортировать студенческие данные grade, используя DSU подход:

>>> decorated = [(student.grade, i, student) for i, student in enumerate(student_objects)]
>>> decorated.sort()
>>> [student for grade, i, student in decorated]               # undecorate
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]

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

Не обязательно во всех случаях включать индекс i в оформленный список, но в том числе он дает две выгоды:

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

Другое название этой идиомы - Преобразование Шварца, в честь Рэндала Л. Шварца, популяризировавшего её среди программистов Perl.

Теперь, когда сортировка Python обеспечивает ключевые функции, эта техника не часто необходима.

Старый способ используя параметр cmp¶

Многие конструкции, приведенные в этом HOWTO, предполагают Python 2.4 или выше. Перед этим было встроенный не sorted(), и list.sort() не взял аргументы ключевой. Вместо этого все версии Py2.x поддерживали параметр cmp для обработки определенных пользователем функций сравнения.

В Py3.0 параметр cmp был удален полностью (в рамках более крупных усилий по упрощению и унификации языка, устранив конфликт между богатыми сравнениями и методом __cmp__() magic).

В Py2.x сортировка позволяет использовать необязательную функцию, которая может быть вызвана для сравнения. Эта функция должна использовать два аргумента для сравнения, а затем возвращать отрицательное значение для «меньше», возвращать ноль, если они равны, или возвращать положительное значение для «больше». Например, мы можем сделать:

>>> def numeric_compare(x, y):
...     return x - y
>>> sorted([5, 2, 4, 1, 3], cmp=numeric_compare) # doctest: +SKIP
[1, 2, 3, 4, 5]

Также можно изменить порядок сравнения с:

>>> def reverse_numeric(x, y):
...     return y - x
>>> sorted([5, 2, 4, 1, 3], cmp=reverse_numeric) # doctest: +SKIP
[5, 4, 3, 2, 1]

При портировании код с Python 2.x на 3.x может возникнуть ситуация, когда пользователь предоставляет функцию сравнения и необходимо преобразовать ее в ключевую функцию. Следующая обертка делает это легко сделать:

def cmp_to_key(mycmp):
    'Convert a cmp= function into a key= function'
    class K:
        def __init__(self, obj, *args):
            self.obj = obj
        def __lt__(self, other):
            return mycmp(self.obj, other.obj) < 0
        def __gt__(self, other):
            return mycmp(self.obj, other.obj) > 0
        def __eq__(self, other):
            return mycmp(self.obj, other.obj) == 0
        def __le__(self, other):
            return mycmp(self.obj, other.obj) <= 0
        def __ge__(self, other):
            return mycmp(self.obj, other.obj) >= 0
        def __ne__(self, other):
            return mycmp(self.obj, other.obj) != 0
    return K

Чтобы преобразовать в ключевую функцию, просто поместите старую функцию сравнения:

>>> sorted([5, 2, 4, 1, 3], key=cmp_to_key(reverse_numeric))
[5, 4, 3, 2, 1]

В Python 3.2 функция functools.cmp_to_key() была добавлена в модуль functools в стандартной библиотеке.

Нечётные и концы¶

Для сортировки с учетом языкового стандарта используйте locale.strxfrm() для функции ключа или locale.strcoll() для функции сравнения.
Параметр reverse сохраняет стабильность сортировки (так что записи с равными ключами сохраняют исходный порядок). Интересно, тот эффект может быть моделирован без параметра при помощи встроенной функции дважды reversed():
```
>>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)]
>>> standard_way = sorted(data, key=itemgetter(0), reverse=True)
>>> double_reversed = list(reversed(sorted(reversed(data), key=itemgetter(0))))
>>> assert standard_way == double_reversed
>>> standard_way
[('red', 1), ('red', 2), ('blue', 1), ('blue', 2)]
```
Процедуры сортировки гарантируют использование __lt__() при проведении сравнений между двумя объектами. Таким образом, легко добавить стандартный порядок сортировки к класс путем определения метода __lt__():
```
>>> Student.__lt__ = lambda self, other: self.age < other.age
>>> sorted(student_objects)
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
```
Ключевые функции не должны напрямую зависеть от сортируемых объектов. Ключевая функция также может обращаться к внешним ресурсам. Например, если оценки учеников хранятся в словаре, их можно используемый для сортировки отдельного списка имен студентов:
```
>>> students = ['dave', 'john', 'jane']
>>> newgrades = {'john': 'F', 'jane':'A', 'dave': 'C'}
>>> sorted(students, key=newgrades.__getitem__)
['jane', 'dave', 'john']
```

HOWTO по сортировке¶

Основы сортировки¶

Ключевые функции¶

Функции модуля operator¶

По возрастанию и убыванию¶

Стабильность сортировки и сложные сортировки¶

Старый способ использования декорирование-сортировка-раздекорирование¶

Старый способ используя параметр cmp¶

Нечётные и концы¶

Содержание

Предыдущий раздел

Следующий раздел

Эта страница