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

Автор:Эндрю Далке и Раймонд Хеттингер
Версия: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 параметра должна быть функция, которая принимает единственный аргумент и возвращает ключ для использования в целях сортировки. Этот метод быстр, потому что ключевая функция вызывается ровно один раз для каждой входной записи.

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

>>> student_tuples = [
...     ('john', 'A', 15),
...     ('jane', 'B', 12),
...     ('dave', 'B', 10),
... ]
>>> sorted(student_tuples, key=lambda student: student[2])   # сортировка по возрасту
[('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)   # сортировка по возрасту
[('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 параметр с логическим значением. Он используется для отметки сортировки по убыванию. Например, чтобы получить данные о студентах в обратном age порядке:

>>> 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), а затем снова отсортировать, используя 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, эффективно выполняет множественную сортировку, поскольку он может использовать любое упорядочение, уже присутствующее в наборе данных.

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

Эта идиома называется «Декорирование-Сортировка-Раздекорирование (DSU,Decorate-Sort-Undecorate)» после трёх шагов:

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

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

>>> decorated = [(student.grade, i, student) for i, student in enumerate(student_objects)]
>>> decorated.sort()
>>> [student for grade, i, student in decorated]               # раздекорирование
[('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__()).

В 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']