Сортировка, key и lambda
sorted и sort
nums = [5, 2, 9, 1, 7]
print(sorted(nums)) # новый список; nums не меняется
print(sorted(nums, reverse=True))
nums.sort() # на месте, возвращает None
print(nums)
print(sorted("питон"), sorted({3, 1, 2}), sorted({"b": 1, "a": 2})) # любое итерируемое
sorted(iterable) |
list.sort() |
|
|---|---|---|
| Что сортирует | любое итерируемое | только список |
| Результат | новый список | изменяет список, возвращает None |
Параметр key
key — функция, которая для каждого элемента вычисляет ключ сравнения:
words = ["банан", "Яблоко", "арбуз", "киви"]
print(sorted(words)) # заглавные буквы «меньше» строчных
print(sorted(words, key=str.lower)) # без учёта регистра
print(sorted(words, key=len)) # по длине
print(sorted(words, key=lambda w: w[-1])) # по последней букве
Ключ вычисляется один раз для каждого элемента, а не при каждом сравнении.
lambda
lambda аргументы: выражение — короткая безымянная функция, удобная как key:
people = [{"name": "Анна", "age": 30}, {"name": "Борис", "age": 25}, {"name": "Вера", "age": 35}]
print(sorted(people, key=lambda p: p["age"]))
by_age = lambda p: p["age"] # так писать не принято — для этого есть def
Сортировка по нескольким полям
Кортежи сравниваются поэлементно, поэтому ключ-кортеж задаёт порядок полей:
employees = [("Анна", "IT", 120), ("Борис", "HR", 90), ("Вера", "IT", 150), ("Глеб", "HR", 90)]
# по отделу, затем по зарплате по убыванию (минус для чисел), затем по имени
for e in sorted(employees, key=lambda e: (e[1], -e[2], e[0])):
print(e)
Убывание для строк
Минус работает только с числами. Чтобы отсортировать по строковому полю по убыванию, а по другому — по возрастанию, используйте стабильность: сортируйте в несколько проходов, начиная с второстепенного ключа.
data = [("Анна", 90), ("Вера", 85), ("Борис", 90)]
data.sort(key=lambda r: r[0], reverse=True) # второстепенный: имя по убыванию
data.sort(key=lambda r: r[1]) # главный: балл по возрастанию
print(data) # при равном балле сохранён порядок из первой сортировки
operator.itemgetter и attrgetter
Быстрее и короче lambda для типичных случаев:
from operator import itemgetter, attrgetter
from collections import namedtuple
rows = [("Анна", 30), ("Борис", 25)]
print(sorted(rows, key=itemgetter(1)))
Person = namedtuple("Person", "name age")
ps = [Person("Анна", 30), Person("Борис", 25)]
print(sorted(ps, key=attrgetter("age")))
print(sorted([{"a": 2, "b": 1}, {"a": 1, "b": 5}], key=itemgetter("a", "b")))
min, max и key
scores = {"Анна": 90, "Борис": 75, "Вера": 97}
print(max(scores, key=scores.get)) # ключ с максимальным значением
print(min(["кот", "гиппопотам", "ёж"], key=len))
print(max([], default="пусто")) # без default — ValueError
import heapq
from operator import itemgetter
print(heapq.nlargest(2, scores.items(), key=itemgetter(1))) # top-k без полной сортировки
Как сортирует Python: Timsort
Встроенная сортировка — Timsort (Тим Питерс, 2002): находит уже упорядоченные участки («пробеги»), досортировывает короткие вставками и сливает пробеги слиянием.
- O(n log n) в худшем случае, O(n) на почти отсортированных данных;
- стабильная;
- требует O(n) дополнительной памяти.
С Python 3.11 для слияния используется улучшенная стратегия Powersort, но свойства те же.
Разные типы не сравниваются
sorted([3, "a", 1]) → TypeError: '<' not supported between instances of 'str' and 'int'. В Python 3 нет «общего порядка» для разных типов. Используйте key, приводящий к одному типу.
Итог
sorted()— новый список из любого итерируемого;.sort()— на месте, возвращаетNone.key=функциявычисляет ключ сравнения;reverse=True— по убыванию.- Несколько полей — ключ-кортеж; убывание числа — минус; сложные случаи — несколько проходов благодаря стабильности.
itemgetter/attrgetter,min/max(key=...),heapq.nlargestдля top-k.- Timsort: O(n log n), стабильный, быстрый на частично упорядоченных данных.
Практика решено 0 из 5
Отсортируйте список студентов students (кортежи «имя, балл») по убыванию балла,
а при равных баллах — по имени по алфавиту. Результат сохраните в ranked.
Какие тесты проверяют код (1)
assert ranked == [("Борис", 90), ("Вера", 90), ("Анна", 85), ("Глеб", 70)]
students = [("Вера", 90), ("Анна", 85), ("Борис", 90), ("Глеб", 70)]
ranked = sorted(students, key=lambda s: (-s[1], s[0]))
Напишите функцию longest_word(words): вернуть самое длинное слово, а при равной длине —
первое из них. Используйте max с key.
Какие тесты проверяют код (2)
assert longest_word(["кот", "слон", "жираф", "зебра"]) == "жираф" assert longest_word(["a"]) == "a"
def longest_word(words):
return max(words, key=len)
Что значит «сортировка в Python стабильна»?
Напишите функцию sort_files(names), которая сортирует имена файлов по расширению,
а при одинаковом расширении — по имени без учёта регистра. Файлы без точки считайте имеющими пустое расширение.
Какие тесты проверяют код (2)
assert sort_files(["b.txt", "A.py", "a.txt", "README", "c.py"]) == ["README", "A.py", "c.py", "a.txt", "b.txt"] assert sort_files([]) == []
def sort_files(names):
def key(name):
base, dot, ext = name.rpartition(".")
if not dot:
base, ext = name, ""
return ext.lower(), base.lower()
return sorted(names, key=key)
Какая сложность у sorted() в худшем случае?
Войдите, чтобы отмечать пройденные уроки.