Сортировка на Python: функции-ключи и модуль Operator

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

Основы сортировки на 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]

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

Начиная с Python 2.4 у sorted() и list.sort() появился параметр 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)]

По материалам статьи «Sorting Mini-HOW TO».