Сортировка КАК¶

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

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

Функции модуля оператора¶

Приведенные выше шаблоны ключ-функция встречаются очень часто, поэтому 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)]

Восходящий и нисходящий¶

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

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

Эта идиома называется «украсить-сортировать-украсить» в честь трех ее этапов:

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

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

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

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

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

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

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

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

>>> 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:
        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__():

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

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

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