Python: сортировка списков методом .sort() с ключом — простыми словами

Поводом опубликовать пост стало то, что при детальном изучении списков (массивов) в Python я не смог найти в сети ни одного простого описания метода сортировки элементов с использованием ключа: list.sort(key=...).

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

Итак, что мы имеем. Предположим, у нас есть список, который мы бы хотели отсортировать — и состоит он из трех строк разной длины в определенной последовательности:

sortList = ['a', 'сс', 'bbb']

Сортировка элементов массива методом .sort() производится по умолчанию лексикографически — проще говоря, в алфавитном порядке, а также от меньшего значения к большему. Поэтому если мы выполним:

sortList.sort()

то получим на выходе:

>>> ['a', 'bbb', 'cc']

Однако метод .sort() позволяет нам изменять и принцип, и порядок сортировки.

Для изменения принципа сортировки используется ключевое слово key, которое стало доступным начиная с версии Python 2.4.

Предположим, нам хотелось бы отсортировать наш список двумя способами: 1. в алфавитном порядке; 2. по длине строки. Первый способ, впрочем, уже работает как сортировка по умолчанию, однако мы можем добиться таких же результатов и с помощью параметра key:

sortList = ['a', 'cc', 'bbb']

# Создаем "внешнюю" функцию, которая будет сортировать список в алфавитном порядке:
def sortByAlphabet(inputStr):
        return inputStr[0] # Ключом является первый символ в каждой строке, сортируем по нему

# Вторая функция, сортирующая список по длине строки:
def sortByLength(inputStr):
        return len(inputStr) # Ключом является длина каждой строки, сортируем по длине

print u'Исходный список: ', sortList # >>> ['a', 'cc', 'bbb']

sortList.sort(key=sortByAlphabet) # Каждый элемент массива передается в качестве параметра функции
print u'Отсортировано в алфавитном порядке: ', sortList # >>> ['a', 'bbb', 'cc']

sortList.sort(key=sortByLength) # Каждый элемент массива передается в качестве параметра функции
print u'Отсортировано по длине строки: ', sortList # >>> ['a', 'cc', 'bbb']

# Теперь отсортируем по длине строки, но в обратном порядке:
sortList.sort(key=sortByLength, reverse=True) # В обратном порядке
print u'Отсортировано по длине строки, в обратном порядке: ', sortList # >>> ['bbb', 'cc', 'a']


Обратите внимание, что метод .sort() производит действия с исходным списком, переставляя элементы внутри него самого, и НЕ возвращает отсортированную копию исходного списка. Для получения отсортированной копии нужно использовать метод sorted:

newList = sorted(sortList)

— либо такой же вариант, но с параметром key (аналогично описанному выше):

newList = sorted(sortList, key=sortByLength)

У метода .sorted() есть и другие параметры, но мне они показались не настолько запутанными для самостоятельного разбора.
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 32

    0
    А в чем сложность? Элементы сортируются по ключам(по возрастанию). Некоторая вариация компаратора, с которым sort тоже умеет работать.
      +6
      wiki.python.org/moin/HowTo/Sorting — не оно? Всё расписано.

      Кстати, вместо
      sortList.sort(key=sortByLength)

      можно просто писать
      sortList.sort(key=len)

      Также, что бы не плодить лишние функции утилитарные можно использовать лямбды.
        –2
        Насчет лямбды — согласен, просто не стал усложнять. Key=len — тоже лучше, но пример с функцией я привел для наглядности.

        Что касается ссылки на вики питона, то да, там все написано, просто лично у меня возник «затык» с пониманием, как работает именно key, поэтому я «разжевал» все более простыми словами — в первую очередь, для самого себя. Возможно, у кого-то тоже есть проблемы с пониманием этого параметра, и мой пост поможет (для этого и опубликовал).
          0
          лучший способ понять — объяснить другому
            0
            Да, все верно))
        +1
        Иногда удобно использовать не key, а cmp.
        К примеру, нужно сортировать список пар сначала по второму элементу:
        >>> l = [(1, 2), (4, 5), (100, 1)]
        >>> l.sort(cmp=lambda (x1, y1), (x2, y2): cmp(y1, y2) or cmp(x1, x2))
        >>> l
        [(100, 1), (1, 2), (4, 5)]
        

        ИМХО, весьма наглядно: для сравнения (cmp) пар, нужно сравнить (cmp) вторые элементы, а потом сравнить (cmp) первые.
          0
          Да, это очень наглядно — и просто одновременно, спасибо. Нужно точно знать, что содержится в сортируемом списке, чтобы правильно использовать параметры lambda.
            0
            В данном случае намного удобней именно `key`:

            >>> l = [(1, 2), (4, 5), (100, 1)]
            >>> sorted(l, key=lambda x: x[::-1])
            [(100, 1), (1, 2), (4, 5)]


            Кроме того, `cmp` параметер уже де-факто устарелый (был удален в Python 3.0).
              0
              Правильно ли я понимаю, что эта конструкция означает, что ключом являются по очереди первый, а затем последний элемент в сравниваемых списках, при этом последний (в нашем случае — второй, l[-1]) элемент сравнивается только в случае, если первые элементы сравниваемых списков равны?
                0
                Стандартное поведение при сравнении списков/кортежей:
                (a1, b1) > (a2, b2) если a1 > a2, или b1 > b2 при a1 = a2
                [::-1] разворачивает пары задом-наперед, чтобы сравнивались сначала вторые элементы
                  0
                  Да, я именно это и имел в виду, спасибо.
                +1
                У key и cmp смысл разный: cmp позволяет нам сравнивать элементы, в то время как key дает нам возможность предоставить ключ для сортировки. Первый случай гибче, но не так часто нужен.
                  0
                  `key` намного более понятен. Мне сложно представить реальный пример, в котором использование `cmp` будет оправдано.
                    0
                    На самом деле, ИМХО, key vs cmp — дело вкуса, ни один вариант не сложнее понимать, при наличии, собственно, понимания принципов работы сортировки.
                      0
                      Вот это то, что я осознал, но побоялся озвучить))
                    • НЛО прилетело и опубликовало эту надпись здесь
                        0
                        Хм. Я только cmp и пользуюсь. Причём повсеместно. Как ещё удобно можно провести сортировку по нескольким полям?

                        lst.sort(cmp=lambda x, y: cmp(x[«order»], y[«order»]) or cmp(x[«name»], y[«name»]))
                          +1
                          lst.sort(key=lambda x: (x['order'], x['name'])) разве не проще?

                            0
                            О, спасибо. Проще, конечно. Упустил, что key умеет кортежи.
                              0
                              самое интересное, что два ключа внутри sort/sorted, скорее всего, все равно «скармливаются» функции cmp — она определяет порядок следования элементов ))
                          0
                          1. Используем functools.cmp_to_key если не получается сообразить, как делать с key напрямую.
                          2. Сортировка с использованием key гораздо быстрее. Реализация считает ключ один раз на элемент, cmp будет вызываться столько раз сколько нужно будет сравнить пар. Почувствуйте разницу.
                            0
                            По поводу functools.cmp_to_key — только в Pyhton версии 2.7+, при том, что 2.6 ещё в ходу.

                            cmp может быть ленивой. Пример:
                            cmp = lambda x, y: cmp(len(x), len(y)) or cmp(sum(x), sum(y))

                            Суммы считаться не будут пока длины не равны. В общем случае сумма будет считаться не для каждого элемента.
                            Теперь key:
                            key = lambda x: (len(x), sum(x))

                            Сумма будет посчитана для каждого элемента, даже если не будет использоваться.
                            Резюмирую: key не всегда лучше cmp
                              0
                              Вы упустили один момент: если длины равны — то сумма будет считаться раз за разом. Плюс overhead на каждый вызов. Ленивость вычислений лучше спрятать куда-нибудь. В ленивое свойство, к примеру.
                              0
                              Посмотрел исходник cmp_to_key. Вот он:
                              def cmp_to_key(mycmp):
                                   """Convert a cmp= function into a key= function"""
                                   class K(object):
                                       __slots__ = ['obj']
                                       def __init__(self, obj):
                                           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
                                       __hash__ = None
                                   return K
                              

                              И что мы видим? Сравнение экземпляров разных классов (синглтонов, по сути), причем при каждом сравнении происходит вызов cmp. В итоге имеем те же затраты на cmp + overhead от ООП-обёртки, причем overhead немалый!
                              ИМХО, очень некрасиво реализовано.
                                0
                                Лучше не сделаешь. Это — костыль. Официальная рекомендация — использовать key везде.
                            0
                            Есть у моего способа сортировки папа преимуществ:
                            1) если для сравниваемых пар вторые элементы уже позволяют определить порядок, первые не будут сравниваться, В варианте с key, ключ-пара будет создаваться в любом случае.
                            2) получение ключа каждый раз, это создание/«уборка» нового объекта, поэтому накладные расходы всё равно будут.
                              0
                              "… пара..." конечно же
                                0
                                Так и быть, держите развернутый ответ habrahabr.ru/blogs/python/138625/ :)
                                  0
                                  Не знал, спасибо большое за информацию. Как раз подумывал замеры провести. Похоже key вычисляется один на элемент в первом проходе, а далее сортировка одних лишь ключей происходит, а cmp вызывается многократно для каждого конкретного элемента при сравнении его с другими.
                                    0
                                    Пожалуйста:)
                            0
                            Придумал пример, немного синтетический, правда, того случая, когда cmp не применишь, по крайней мере в лоб.
                            Задача: нужно распределить числа в массиве по группам отрицательные, ноль(ноли) и положительные.
                            key вполне работает.
                            >>> import random
                            >>> l = [x - 10 for x in xrange(20)]
                            >>> random.shuffle(l)
                            >>> l
                            [7, 8, -10, -9, 3, 0, 4, -5, -1, 6, -7, -3, -4, -8, 2, 9, -6, -2, 5, 1]
                            >>> sign = lambda x: -1 if x < 0 else (0 if x == 0 else 1)
                            >>> sorted(l, key=sign)
                            [-10, -9, -5, -1, -7, -3, -4, -8, -6, -2, 0, 7, 8, 3, 4, 6, 2, 9, 5, 1]
                            

                            Причем порядок чисел внутри групп не поменялся!
                              0
                              О, получилось!
                              . . .
                              >>> sorted(l, cmp=lambda x, y: 0 if sign(x) == sign(y) else cmp(x, y))
                              [-10, -9, -5, -1, -7, -3, -4, -8, -6, -2, 0, 7, 8, 3, 4, 6, 2, 9, 5, 1]
                              

                            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                            Самое читаемое