Метка: itemgetter

Ключ сортировки key

Методы sort, sorted могут принимать именованный аргумент key. Он должен быть функцией (или чем-то другим вызываемым – callable) с одним аргументом. Смысл key в том, что он вызывается ровно один раз для каждого из элементов списка (итератора и т.п.), которой мы сортируем, и указывает порядок сортировки: элементы выстраиваются ровно в том порядке, в каком бы выстроился сортированный список результатом вызова key на всех элементах:

  1. Применить key ко всем элементам
  2. Отсортировать результаты key по порядку, используя обычное сравнение «больше-меньше» для (чисел, строк и т.п.)
  3. Выстроить исходные данные согласно этому порядку.

key нужен, чтобы либо сортировать данные по нестандартному признаку или нескольким признакам сразу.

С числами все понятно: 10 > 6, 5 < 7. Строки сортируются лексикографически (как статьи в словаре: А < АА < ААА < ААБ < ААВ < АБ < Б < … < ЯЯЯ). А вот сортировка по длине строки потребует использовать key , потому что признак уже нестандартный:

>>> sorted(['Wolf', 'Sparrow', 'Cat'], key=len)
['Cat', 'Wolf', 'Sparrow']

>>> len('Cat')
3
>>> len('Wolf')
4
>>> len('Sparrow')
7

Или другой пример. У нас есть список координат точек [(x, y), ...]. Хотим расположить их по расстоянию от начала координат (0, 0):

pts = [(10, 20), (-100, 150), (0, 0), (40, -30)]

print(sorted(pts, key=lambda p: p[0] ** 2 + p[1] ** 2))

# [(-100, 150), (40, -30), (10, 20), (0, 0)]

Но, что если у нас, скажем, список кортежей? По умолчанию (стандартно) кортежи сравниваются сначала по первому элементу, а потом, если первые равны – по второму, и так далее. Если нужно игнорировать первый элемент и сразу сравнивать по второму – это уже и есть нестандартный признак.

drinks = [
    # напиток, цена
    ('Juice', 100),
    ('Beer', 200),
    ('Soda', 50),
    ('Cocktail', 400),
    ('Water', 20)
]

print(sorted(drinks, key=lambda drink: drink[1]))
# [('Water', 20), ('Soda', 50), ('Juice', 100), ('Beer', 200), ('Cocktail', 400)]


# без key:
print(sorted(drinks))  # отсортирует по названию напитка
# [('Beer', 200), ('Cocktail', 400), ('Juice', 100), ('Soda', 50), ('Water', 20)]

Бонус: если хотите поменять порядок сортировки на обратный, можно либо в лямбде поставить минус перед возвращаемым значениям, но лучше в sorted передать reverse=True.

print(sorted(drinks, key=lambda drink: -drink[1]))
# или лучше
print(sorted(drinks, key=lambda drink: drink[1], reverse=True))
# [('Cocktail', 400), ('Beer', 200), ('Juice', 100), ('Soda', 50), ('Water', 20)]

Сортировка по нескольким признакам сразу

Задача на примере тех же напитков. Отсортировать сначала по числу букв в названии, а если название одинаковой длины, то отсортировать по цене от дорогих к дешевым:

print(sorted(drinks, key=lambda dr: (len(dr[0]), -dr[1])))

# [('Beer', 200), ('Soda', 50), ('Juice', 100), ('Water', 20), ('Cocktail', 400)]

Здесь использовано свойство сравнения кортежей. Давайте прогоним нашу лямбду по элементам и посмотрим на те ключи, которые действительно будет сравнивать sorted:

>>> list(map(lambda dr: (len(dr[0]), -dr[1]), drinks))
[(5, -100), (4, -200), (4, -50), (8, -400), (5, -20)]

Видите, первым теперь идет длина строки, а потом цена с минусом. Поэтому первыми после сортировки пойдут элементы с четверкой в ключе, а среди двух (4, -200), (4, -50) порядок сохранится, потому что -200 < -50.

Модуль operator

Вместо лямбды можно взять одну из библиотечных функций из модуля operator. Есть несколько вариантов для разных ситуаций.

Функция itemgetter(i) берет i-тый элемент кортежа или списка (или ищет по ключу i в dict):

from operator import itemgetter

print(sorted(drinks, key=itemgetter(1)))
# [('Water', 20), ('Soda', 50), ('Juice', 100), ('Beer', 200), ('Cocktail', 400)]

Для словарей:

# преобразуем список кортежей в список словарей
drinks_dict = [{'n': name, 'pr': price} for name, price in drinks]  
print(drinks)

# вывод: [{'n': 'Juice', 'pr': 100}, {'n': 'Beer', 'pr': 200}, {'n': 'Soda', 'pr': 50}, {'n': 'Cocktail', 'pr': 400}, {'n': 'Water', 'pr': 20}]

print(sorted(drinks, key=itemgetter('pr')))

# вывод: [{'n': 'Water', 'pr': 20}, {'n': 'Soda', 'pr': 50}, {'n': 'Juice', 'pr': 100}, {'n': 'Beer', 'pr': 200}, {'n': 'Cocktail', 'pr': 400}]

Теперь представим, что у нас есть класс Drink, и нужно сортировать по атрибуту price. Это можно сделать лямбдой или функцией attrgetter, которая получает атрибут объекта по имени этого атрибута:

class Drink:
    def __init__(self, name, price):
        self.name = name
        self.price = price
    def __repr__(self):
        return f'Drink("{self.name}", {self.price})'

drinks_cls = [
    # напиток, цена
    Drink('Juice', 100),
    Drink('Beer', 200),
    Drink('Soda', 50),
    Drink('Cocktail', 400),
    Drink('Water', 20)
]

print(sorted(drinks_cls, key=lambda drink: drink.price))

# или
from operator import attrgetter
print(sorted(drinks_cls, key=attrgetter('price')))

Еще есть methodcaller, она вызывает метод по имени и использует результат его, как ключ для сортировки.

from operator import methodcaller

sorted(items, key=methodcaller('get_reserve', category='home'))

# тоже самое что:

sorted(items, key=lambda item: item.get_reserve(category='home'))

Исследование производительности

Вариант с лямбдой немного медленнее (потому что операторы написаны на Си, а лямбду – мы пишем на Python). Проведем тесты производительности:

from random import shuffle
from timeit import timeit
from operator import itemgetter

data = [{'ident': x, 'value': 'foo'} for x in range(1000)]
shuffle(data)

def sort_itemgetter(data):
    data.sort(key=itemgetter('ident'))

def sort_lambda(data):
    data.sort(key=lambda it: it['ident'])

print('sort_itemgetter:', timeit('sort_itemgetter(list(data))', globals=globals(), number=10000))
print('sort_lambda:', timeit('sort_lambda(list(data))', globals=globals(), number=10000))

# sort_itemgetter: 1.6157471220000001
# sort_lambda: 1.8793544059999998

Потому что:

ig = itemgetter('ident')
la = lambda it: it['ident']
di = {'ident': 10}

print('itemgetter:', timeit('ig(di)', globals=globals(), number=1000000))
print('lambda:', timeit('la(di)', globals=globals(), number=1000000))

# itemgetter: 0.083
# lambda: 0.11

itemgetter быстрее, чем lambda, ибо он написан на Си.

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

min и max

Методы min и max также поддерживают key. Они вернут соответственно элемент, у которого key вернет наименьшее или наибольшее значение. На примере длины строк:

names = ['Wolf', 'Sparrow', 'Cat']
min(names, key=len)  # 'Cat'
max(names, key=len)  # 'Sparrow'

Самая ближняя от начала координат точка и самая дальняя:

pts = [(10, 20), (-100, 150), (0, 0), (40, -30)]
min(pts, key=lambda p: p[0] ** 2 + p[1] ** 2)  # (0, 0)
max(pts, key=lambda p: p[0] ** 2 + p[1] ** 2)  # (-100, 150)

Специально для канала @pyway. Подписывайтесь на мой канал в Телеграм @pyway 👈 

Встроенная сортировка Python

В Python сортировка производится встроенной функцией sorted. Первым аргументом она принимает итерируемый объект. Это может быть список, кортеж, генератор, итератор и т.п. Возвращает отсортированный список.

>>> sorted([4, 2, 3, 1, 0])
[0, 1, 2, 3, 4]

>>> sorted((3, 1, 2))
[1, 2, 3]

>>> sorted(x * x for x in range(-5, 6))
[0, 1, 1, 4, 4, 9, 9, 16, 16, 25, 25]

Для словаря вернет сортированный список ключей:

>>> sorted({1: "abc", 3: "foo", -1: "baz"}) 
[-1, 1, 3] 

Если хотим значение, надо прямо это указать:

>>> sorted({1: "abc", 3: "foo", -1: "baz"}.values())
['abc', 'baz', 'foo']

Можно сортировать в обратном порядке:

>>> sorted([4, 2, 3, 1, 0], reverse=True)
[4, 3, 2, 1, 0]

Если сортируемые элементы – списки, словари или объекты, то воспользуемся параметром key. Мы передаем в key нечто вызываемое (имя функции, lambda и т.п), и при сортировки элементы сравниваются по результату вызова key на элементе. Результатом key должно быть число, строка или что-то другое сравнимое между собой.

📎 Пример. Сортировка списка строк по длине строки:

>>> sorted(["foo", "bazooka", "", "game"], key=len)
['', 'foo', 'game', 'bazooka']

📎 Пример. Сортировка списка кортежей по 0 или 1 элементу каждого.

>>> people = [("Bill", "Gates"), ("Tim", "Cook"), ("Donald", "Trump")]

>>> sorted(people, key=lambda t: t[0])
[('Bill', 'Gates'), ('Donald', 'Trump'), ('Tim', 'Cook')]

>>> sorted(people, key=lambda t: t[1])
[('Tim', 'Cook'), ('Bill', 'Gates'), ('Donald', 'Trump')]

Для этой же цели удобно использовать функцию operator.itemgetter:

>>> import operator
>>> sorted(people, key=operator.itemgetter(0))
[('Bill', 'Gates'), ('Donald', 'Trump'), ('Tim', 'Cook')]

Еще полезные функции из operator:
attrgetter(name) – для получение значения атрибута объекта с именем name
methodcaller(name[, args…]) – для получения результата вызова метода name у объекта. Опционально с аргументами args.

Вот пример использования этих функций:

import operator

class Item:
    def __init__(self, name, price, qty):
        self.name = name
        self.price = price
        self.qty = qty

    def total_cost(self):
        return self.price * self.qty

    def __repr__(self):
        return f'({self.name} ${self.price} x {self.qty} = ${self.total_cost()})'


items = [
    Item("iPhone", 999, 5),
    Item("iMac", 2999, 2),
    Item("iPad", 599, 11)
]

def print_items(title, item_list):
    print(title)
    print(*item_list, sep=', ', end='\n\n')


print_items('Original:', items)

items_by_price = sorted(items, key=operator.attrgetter('price'))
print_items('Sorted by price:', items_by_price)

items_by_total_cost = sorted(items, key=operator.methodcaller('total_cost'))
print_items('Sorted by total cost:', items_by_total_cost)

"""
Original:
(iPhone $999 x 5 = $4995), (iMac $2999 x 2 = $5998), (iPad $599 x 11 = $6589)
Sorted by price:
(iPad $599 x 11 = $6589), (iPhone $999 x 5 = $4995), (iMac $2999 x 2 = $5998)
Sorted by total cost:
(iPhone $999 x 5 = $4995), (iMac $2999 x 2 = $5998), (iPad $599 x 11 = $6589)
"""

Для списков (list) определен метод sort(), который модифицирует исходный список, выстраивая элемента по порядку.

>>> arr = [3, 4, 1, 2, 5, 6, 0]
>>> arr.sort()
>>> arr
[0, 1, 2, 3, 4, 5, 6]

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

>>> names = ["John", "Tim", "Bill", "Max"]
>>> sorted(names, key=len)
['Tim', 'Max', 'John', 'Bill']

Tim и Max — оба длины 3, Tim был перед Max, так и осталось. John остался перед Bill. Зачем это нужно? Чтобы можно было сортировать сначала по одному признаку, потому по другому (если первый совпадает).

📎 Пример. Первичный признак – оценка ученика. Вторичный – имя. Внимание: сначала сортируем по вторичному, потому по первичному:

>>> students = [(3, "Xi"), (5, "Kate"), (5, "Max"), (3, "Fil"), (5, "Abby")]
>>> students_by_name = sorted(students, key=operator.itemgetter(1))
>>> sorted(students_by_name, key=operator.itemgetter(0))
[(3, 'Fil'), (3, 'Xi'), (5, 'Abby'), (5, 'Kate'), (5, 'Max')]

Внутри Python использует Timsort – гибридный алгоритм сортировки, сочетающий сортировку вставками и сортировку слиянием. Смысл в том, что в реальном мире часто встречаются частично отсортированные данные, на которых Timsort работает ощутимо быстрее прочих алгоритмов сортировки. Сложность по времени: O(n log n) в худшем случае и O(n) – в лучшем.

⚠️ CPython: не пытайтесь модифицировать сортируемый список во время сортировки. Эффект непредсказуем.

Специально для канала @pyway.