Руководство по сортировке¶Sorting HOW TO

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

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

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

Начиная с 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))

>>> 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¶Operator Module Functions

Описанные выше шаблоны ключевых функций очень распространены, поэтому Python предоставляет вспомогательные функции, чтобы сделать функции доступа проще и быстрее. Модуль operator содержит operator.itemgetter(), operator.attrgetter(), а начиная с Python 2.5 – функцию operator.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 позволяют выполнять многоуровневую сортировку. Например, сортировка сначала по оценке, а затем по возрасту:

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

Функция operator.methodcaller() осуществляет вызовы методов с фиксированными параметрами для каждого сортируемого объекта. Например, метод str.count() можно использовать для вычисления приоритета сообщения, подсчитывая количество восклицательных знаков в сообщении:

>>> from operator import methodcaller
>>> messages = ['critical!!!', 'hurry!', 'standby', 'immediate!!']
>>> sorted(messages, key=methodcaller('count', '!'))
['standby', 'hurry!', 'immediate!!', 'critical!!!']

По возрастанию и по убыванию¶Ascending and Descending

Обе функции 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)]

Стабильность сортировки и сложные сортировки¶Sort Stability and Complex Sorts

Начиная с 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', 1) гарантированно предшествует ('blue', 2).

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

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

Старый способ: Decorate-Sort-Undecorate¶The Old Way Using Decorate-Sort-Undecorate

Эта идиома называется 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]               # обратное преобразование
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]

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

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

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

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

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

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

Старый способ с параметром cmp¶The Old Way Using the cmp Parameter

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

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

В Python 2 функция 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]

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

def cmp_to_key(mycmp):
    'Convert a cmp= function into a key= function'
    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 функция functools.cmp_to_key() была добавлена в модуль functools.

Разное¶Odd and Ends

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

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

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

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

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

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