Всё о сортировке на Python

В Python есть встроенная функция sorted() для сортировки итерируемых объектов и метод list.sort() для сортировки списка с заменой исходного. Сегодня мы подробно рассмотрим, как они работают сейчас и как работали раньше.

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

Сделать обычную сортировку по возрастанию очень просто — достаточно вызвать функцию 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]

Прим.перев. В Python вернуть None и не вернуть ничего — одно и то же.

Ещё одно отличие заключается в том, что метод list.sort() определён только для списков, в то время как sorted() работает со всеми итерируемыми объектами:

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

Прим.перев. При итерировании по словарю Python возвращает его ключи. Если вам нужны их значения или пары «ключ-значение», используйте методы dict.values() и dict.items() соответственно.

Функции-ключи

С версии Python 2.4 у 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))
        def weighted_grade(self):
            return 'CBA'.index(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() и, начиная с Python 2.6, methodcaller().

С использованием этих функций наши примеры становятся ещё проще:

>>> from operator import itemgetter, attrgetter, methodcaller

>>> 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 дают возможность использовать множественные уровни сортировки. Например, здесь мы сортируем сначала по оценке, а затем по возрасту:

>>> 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)]

В следующем примере мы используем функцию methodcaller() для сортировки учеников по взвешенной оценке:

>>> [(student.name, student.weighted_grade()) for student in student_objects]
[('john', 0.13333333333333333), ('jane', 0.08333333333333333), ('dave', 0.1)]
>>> sorted(student_objects, key=methodcaller('weighted_grade'))
[('jane', 'B', 12), ('dave', 'B', 10), ('john', 'A', 15)]

Сортировка по возрастанию и по убыванию

У list.sort() и sorted() есть параметр reverse, принимающий boolean-значение. Он нужен для обозначения сортировки по убыванию. Например, отсортируем учеников по убыванию возраста:

>>> 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)]

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

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

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

Обратите внимание на то, что две записи с 'blue' сохранили свой изначальный порядок.

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

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

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

Старый способ «декорируем-сортируем-раздекорируем»

Данная идиома так называется по трём её шагам:

  1. Сначала исходный список дополняется новыми значениями, контролирующими порядок сортировки.
  2. Затем новый список сортируется.
  3. После этого добавленные значения убираются, и в итоге остаётся отсортированный список, содержащий только исходные элементы.

Вот так, например, можно отсортировать данные учеников по оценке:

>>> 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)]

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

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

  1. Сортировка стабильна — если у двух элементов одинаковый ключ, то их порядок не изменится.
  2. У исходных элементов не обязательно должна быть возможность сравнения, так как порядок декорированных кортежей будет определяться максимум по первым двум элементам. Например, исходный список может содержать комплексные числа, которые нельзя сравнивать напрямую.

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

Для больших списков и списков, где информацию для сравнения дорого вычислять, а также для версий Python ниже 2.4 «декорируем-сортируем-раздекорируем», наверное, будет самым быстрым способом сортировки. Для версий 2.4+ ту же функциональность предоставляют функции-ключи.

Старый способ с использованием параметра cmp

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

В Python 3.0 от этого параметра полностью избавились в целях упрощения языка и разрешения конфликта между операторами сравнения и методами __cmp__().

В Python 2.x в sort() можно было передать функцию, которая использовалась бы для сравнения элементов. Она должна принимать два аргумента и возвращать отрицательное значение для случая «меньше чем», положительное — для «больше чем» и ноль, если они равны. Например:

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

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

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

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

def cmp_to_key(mycmp):
    'Перевести cmp=функция в key=функция'
    class K(object):
        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 2.7 функция cmp_to_key() была добавлена в модуль functools.

Поддержание порядка сортировки

В стандартной библиотеке Python нет модулей, аналогичных типам данных C++ вроде set и map. Это осознанное решение Гвидо и других для сохранения «единственного очевидного способа сделать это». Python делегирует эту задачу сторонним библиотекам, доступным в Python Package Index. Эти библиотеки используют различные методы для сохранения типов list, dict и set в отсортированном порядке. Поддержание порядка с помощью специальной структуры данных может помочь избежать очень медленного поведения (квадратичного времени выполнения) при наивном подходе с редактированием и постоянной пересортировкой данных. Вот некоторые из модулей, реализующих эти типы данных:

  • SortedContainers — реализация сортированных типов list, dict и set на чистом Python, по скорости не уступает реализациям на Си. Тестирование включает 100% покрытие кода и многие часы стресс-тестирования. В документации можно найти полный справочник по API, сравнение производительности и руководства по внесению своего вклада.
  • rbtree — быстрая реализация на Си для типов dict и set. Реализация использует структуру данных, известную как красно-чёрное дерево.
  • treap — сортированный dict. В реализации используется Декартово дерево, а производительность улучшена с помощью Cython.
  • bintrees — несколько реализаций типов dict и set на основе деревьев на Си. Самые быстрые основаны на АВЛ и красно-чёрных деревьях. Расширяет общепринятый API для предоставления операций множеств для словарей.
  • banyan — быстрая реализация dict и set на Си.
  • skiplistcollections — реализация на чистом Python, основанная на списках с пропусками, предлагает ограниченный API для типов dict и set.
  • blist — предоставляет сортированные типы list, dict и set, основанные на типе данных «blist», реализация на Б-деревьях. Написано на Python и Си.

Прочее

Для сортировки с учётом языка используйте locale.strxfrm() в качестве ключевой функции или locale.strcoll() в качестве функции сравнения.

Параметр reverse всё ещё сохраняет стабильность сортировки. Что интересно, этот эффект можно сымитировать без параметра, использовав встроенную функцию reversed() дважды:

>>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)]
>>> assert sorted(data, reverse=True) == list(reversed(sorted(reversed(data))))

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

>>> Student.__eq__ = lambda self, other: self.age == other.age
>>> Student.__ne__ = lambda self, other: self.age != other.age
>>> Student.__lt__ = lambda self, other: self.age < other.age
>>> Student.__le__ = lambda self, other: self.age <= other.age
>>> Student.__gt__ = lambda self, other: self.age > other.age
>>> Student.__ge__ = lambda self, other: self.age >= other.age
>>> sorted(student_objects)
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

Для типов, сравнение которых работает обычным образом, рекомендуется определять все 6 операторов. Декоратор классов functools.total_ordering упрощает их реализацию.

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

>>> students = ['dave', 'john', 'jane']
>>> newgrades = {'john': 'F', 'jane':'A', 'dave': 'C'}
>>> sorted(students, key=newgrades.__getitem__)
['jane', 'dave', 'john']

Смотрите также: Хочу научиться программировать на Python: инструкция для начинающих и продолжающих

Перевод статьи «Sorting Mini-HOW TO»

Подобрали два теста для вас:
— А здесь можно применить блокчейн?
Серверы для котиков: выберите лучшее решение для проекта и проверьте себя.