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

[Duha666]

А в чем сложность? Элементы сортируются по ключам(по возрастанию). Некоторая вариация компаратора, с которым sort тоже умеет работать.

[lorc]

wiki.python.org/moin/HowTo/Sorting — не оно? Всё расписано.

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

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

Также, что бы не плодить лишние функции утилитарные можно использовать лямбды.

[ashdesigner]

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

Что касается ссылки на вики питона, то да, там все написано, просто лично у меня возник «затык» с пониманием, как работает именно key, поэтому я «разжевал» все более простыми словами — в первую очередь, для самого себя. Возможно, у кого-то тоже есть проблемы с пониманием этого параметра, и мой пост поможет (для этого и опубликовал).

[AreD]

лучший способ понять — объяснить другому

[ashdesigner]

Да, все верно))

[Astynax]

Иногда удобно использовать не 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) первые.

[ashdesigner]

Да, это очень наглядно — и просто одновременно, спасибо. Нужно точно знать, что содержится в сортируемом списке, чтобы правильно использовать параметры lambda.

[leron]

В данном случае намного удобней именно `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).

[ashdesigner]

Правильно ли я понимаю, что эта конструкция означает, что ключом являются по очереди первый, а затем последний элемент в сравниваемых списках, при этом последний (в нашем случае — второй, l[-1]) элемент сравнивается только в случае, если первые элементы сравниваемых списков равны?

[Astynax]

Стандартное поведение при сравнении списков/кортежей:
(a1, b1) > (a2, b2) если a1 > a2, или b1 > b2 при a1 = a2
[::-1] разворачивает пары задом-наперед, чтобы сравнивались сначала вторые элементы

[ashdesigner]

Да, я именно это и имел в виду, спасибо.

[Astynax]

У key и cmp смысл разный: cmp позволяет нам сравнивать элементы, в то время как key дает нам возможность предоставить ключ для сортировки. Первый случай гибче, но не так часто нужен.

[leron]

`key` намного более понятен. Мне сложно представить реальный пример, в котором использование `cmp` будет оправдано.

[Astynax]

На самом деле, ИМХО, key vs cmp — дело вкуса, ни один вариант не сложнее понимать, при наличии, собственно, понимания принципов работы сортировки.

[ashdesigner]

Вот это то, что я осознал, но побоялся озвучить))

[aml]

Хм. Я только cmp и пользуюсь. Причём повсеместно. Как ещё удобно можно провести сортировку по нескольким полям?

lst.sort(cmp=lambda x, y: cmp(x[«order»], y[«order»]) or cmp(x[«name»], y[«name»]))

[leron]

lst.sort(key=lambda x: (x['order'], x['name'])) разве не проще?

[aml]

О, спасибо. Проще, конечно. Упустил, что key умеет кортежи.

[Astynax]

самое интересное, что два ключа внутри sort/sorted, скорее всего, все равно «скармливаются» функции cmp — она определяет порядок следования элементов ))

[svetlov]

1. Используем functools.cmp_to_key если не получается сообразить, как делать с key напрямую.
2. Сортировка с использованием key гораздо быстрее. Реализация считает ключ один раз на элемент, cmp будет вызываться столько раз сколько нужно будет сравнить пар. Почувствуйте разницу.

[Astynax]

По поводу 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

[svetlov]

Вы упустили один момент: если длины равны — то сумма будет считаться раз за разом. Плюс overhead на каждый вызов. Ленивость вычислений лучше спрятать куда-нибудь. В ленивое свойство, к примеру.

[Astynax]

Посмотрел исходник 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 немалый!
ИМХО, очень некрасиво реализовано.

[svetlov]

Лучше не сделаешь. Это — костыль. Официальная рекомендация — использовать key везде.

[Astynax]

Есть у моего способа сортировки папа преимуществ:
1) если для сравниваемых пар вторые элементы уже позволяют определить порядок, первые не будут сравниваться, В варианте с key, ключ-пара будет создаваться в любом случае.
2) получение ключа каждый раз, это создание/«уборка» нового объекта, поэтому накладные расходы всё равно будут.

[Astynax]

"… пара..." конечно же

[leron]

Так и быть, держите развернутый ответ habrahabr.ru/blogs/python/138625/ :)

[Astynax]

Не знал, спасибо большое за информацию. Как раз подумывал замеры провести. Похоже key вычисляется один на элемент в первом проходе, а далее сортировка одних лишь ключей происходит, а cmp вызывается многократно для каждого конкретного элемента при сравнении его с другими.

[leron]

Пожалуйста:)

[Astynax]

Придумал пример, немного синтетический, правда, того случая, когда 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]

Причем порядок чисел внутри групп не поменялся!

[Astynax]

О, получилось!

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