Техника сортировки

Автор:

Эндрю Дальке и Раймонд Хеттингер

В списках 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.casefold)
['a', 'Andrew', 'from', 'is', 'string', 'test', 'This']

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

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

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

Объекты с именованными атрибутами могут быть созданы обычным классом, как показано выше, или же они могут быть экземплярами dataclass или named tuple.

Функции операторного модуля и частичное оценивание функций

Шаблоны key function, показанные выше, очень распространены, поэтому 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)]

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

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

Модуль functools предоставляет еще один полезный инструмент для создания ключевых функций. Функция partial() может уменьшить arity многоаргументной функции, что делает ее пригодной для использования в качестве ключевой функции.

>>> from functools import partial
>>> from unicodedata import normalize

>>> names = 'Zoë Åbjørn Núñez Élana Zeke Abe Nubia Eloise'.split()

>>> sorted(names, key=partial(normalize, 'NFD'))
['Abe', 'Åbjørn', 'Eloise', 'Élana', 'Nubia', 'Núñez', 'Zeke', 'Zoë']

>>> sorted(names, key=partial(normalize, 'NFC'))
['Abe', 'Eloise', 'Nubia', 'Núñez', 'Zeke', 'Zoë', 'Åbjørn', 'Élana']

Восходящие и нисходящие

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

Устойчивость сортировки и сложные сортировки

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

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

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

>>> s = sorted(student_objects, key=attrgetter('age'))     # sort on secondary key
>>> sorted(s, key=attrgetter('grade'), reverse=True)       # now sort on primary key, descending
[('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, эффективно выполняет множественную сортировку, поскольку он может использовать любое упорядочивание, уже присутствующее в наборе данных.

Украсить-сохранить-не украсить

Эта идиома называется Decorate-Sort-Undecorate (украсить-сохранить-украсить) в честь трех ее этапов:

  • Сначала исходный список украшается новыми значениями, которые управляют порядком сортировки.

  • Во-вторых, украшенный список сортируется.

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

Например, чтобы отсортировать данные о студентах по классу, используя подход 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 в декорированный список не является строго необходимым во всех случаях, но его включение дает два преимущества:

  • Сортировка стабильна - если два элемента имеют одинаковый ключ, их порядок сохранится в отсортированном списке.

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

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

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

Функции сравнения

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

Например, функция balance scale сравнивает два образца, задавая относительный порядок: легче, равнее или тяжелее. Аналогично, функция сравнения, например cmp(a, b), вернет отрицательное значение, если входные данные меньше, ноль, если они равны, или положительное значение, если больше.

При переводе алгоритмов с других языков часто приходится сталкиваться с функциями сравнения. Кроме того, некоторые библиотеки предоставляют функции сравнения как часть своего API. Например, locale.strcoll() - это функция сравнения.

Для таких ситуаций в Python предусмотрена функция functools.cmp_to_key, которая оборачивает функцию сравнения и делает ее пригодной для использования в качестве ключевой функции:

sorted(words, key=cmp_to_key(strcoll))  # locale-aware sort order

Нестандартные ситуации

  • Для сортировки с учетом локали используйте 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__():

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

    Однако обратите внимание, что < может вернуться к использованию __gt__(), если __lt__() не реализован (подробности механики см. в object.__lt__()). Чтобы избежать неожиданностей, PEP 8 рекомендует реализовать все шесть методов сравнения. Для облегчения этой задачи предусмотрен декоратор total_ordering().

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

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

Частичные сортировки

В некоторых приложениях требуется упорядочить только часть данных. Стандартная библиотека предоставляет несколько инструментов, которые выполняют меньше работы, чем полная сортировка:

  • min() и max() возвращают наименьшее и наибольшее значения, соответственно. Эти функции выполняют один проход по входным данным и почти не требуют вспомогательной памяти.

  • heapq.nsmallest() и heapq.nlargest() возвращают n наименьших и наибольших значений, соответственно. Эти функции выполняют один проход по данным, сохраняя в памяти только n элементов за один раз. Для значений n, которые малы по сравнению с количеством входов, эти функции выполняют гораздо меньше сравнений, чем полная сортировка.

  • heapq.heappush() и heapq.heappop() создают и поддерживают частично отсортированное расположение данных, в котором наименьший элемент находится на позиции 0. Эти функции подходят для реализации приоритетных очередей, которые обычно используются для планирования задач.