Множества, словари, сортировка

set: множество

Множество похоже на список, но в нём нет повторов и нет порядка. Пишется в фигурных скобках или через set(...):

a = [3, 1, 3, 2, 1, 3]
s = set(a)
print(s)
print(len(s))      # сколько различных значений

Это первое применение: узнать, сколько различных элементов. Второе: проверка in. В списке Python ищет элемент, перебирая всё подряд, а в множестве находит сразу. На списке в сто тысяч чисел разница огромная.

a = [int(x) for x in open('chisla.txt')]
s = set(a)
print('Всего чисел:', len(a), 'различных:', len(s))
print(468 in s, 469 in s)

У множеств есть операции, как в математике:

a = {1, 2, 3, 4}
b = {3, 4, 5}
print(a & b)    # пересечение: есть в обоих
print(a | b)    # объединение: есть хотя бы в одном
print(a - b)    # разность: есть в a, но нет в b

dict: словарь

Словарь хранит пары «ключ: значение». В списке элемент находят по номеру, а в словаре по ключу, который может быть строкой, числом, чем угодно.

points = {'Аня': 78, 'Боря': 91, 'Вика': 85}
print(points['Боря'])        # значение по ключу
points['Гоша'] = 64          # добавили новую пару
points['Аня'] = 80           # поменяли значение
print(points)
print('Вика' in points)      # in проверяет ключи

Перебирать словарь удобно через items(), тогда на каждом шаге есть и ключ, и значение:

points = {'Аня': 78, 'Боря': 91, 'Вика': 85}
for name, p in points.items():
    print(name, p)

Подсчёт через словарь

Главное применение словаря на ЕГЭ: посчитать, сколько раз встречается каждая буква или каждое число. Ключ это то, что считаем, значение это сколько раз встретилось.

s = open('stroka.txt').readline().strip()
d = {}
for c in s:
    d[c] = d.get(c, 0) + 1    # get(c, 0): значение по ключу c, а если его нет, то 0
print(d)

Запись d.get(c, 0) + 1 читается так: возьми, сколько раз уже видели c (или 0, если ни разу), и прибавь один. Без get первая же новая буква дала бы ошибку, потому что ключа ещё нет.

Какая буква встречается чаще всех? max умеет искать по значениям словаря, если подсказать ему key=d.get:

s = open('stroka.txt').readline().strip()
d = {}
for c in s:
    d[c] = d.get(c, 0) + 1
best = max(d, key=d.get)
print(best, d[best])

sorted и key

sorted из темы 6 сортирует числа по возрастанию. Но в №26 сортировать нужно по хитрому правилу: пары по сумме, слова по длине, отрезки по концу. Правило задают через key: это функция, которая говорит, по чему сравнивать.

words = ['кот', 'информатика', 'баг', 'питон']
print(sorted(words))               # по алфавиту
print(sorted(words, key=len))      # по длине

Для своего правила пишут короткую функцию прямо внутри sorted через lambda. lambda p: p[1] значит «функция, которая из p берёт второй элемент»:

pairs = [(5, 2), (1, 9), (3, 2), (4, 7)]
print(sorted(pairs, key=lambda p: p[1]))           # по второму числу
print(sorted(pairs, key=lambda p: p[0] + p[1]))    # по сумме

Несколько правил сразу

«По второму числу, а при равенстве по первому». Для этого key возвращает пару значений: Python сравнивает по первому, а при равенстве по второму. Минус перед числом разворачивает порядок для этого правила:

pairs = [(5, 2), (1, 9), (3, 2), (4, 7)]
print(sorted(pairs, key=lambda p: (p[1], p[0])))      # по второму, потом по первому
print(sorted(pairs, key=lambda p: (-p[1], p[0])))     # второе по убыванию, первое по возрастанию

Пары (5, 2) и (3, 2) равны по второму числу, и их порядок решило первое.

Сломай код

KeyError: такого ключа нет

d = {}
for c in 'АББ':
    d[c] = d[c] + 1

KeyError: 'А'. Буква А встретилась впервые, и d['А'] ещё не существует. Нужно d.get(c, 0) + 1.

TypeError: у множества нет индексов

s = {5, 3, 8}
print(s[0])

'set' object is not subscriptable. У множества нет порядка, поэтому нет и «первого элемента». Если нужен порядок, преврати его в отсортированный список: sorted(s)[0].

Тихая ошибка: {} это не множество

s = {}
print(type(s))

Пустые фигурные скобки дают пустой словарь, а не множество. Пустое множество пишется только как set().

Тихая ошибка: забыли минус

pairs = [(5, 2), (1, 9), (4, 7)]
print(sorted(pairs, key=lambda p: p[1])[0])    # хотели пару с наибольшим вторым числом

Вышла пара с наименьшим. По умолчанию сортировка по возрастанию. Нужен минус -p[1] или reverse=True.

Где пригодится на ЕГЭ

Пример как в №17: пары соседних чисел, где сумма пары тоже есть в файле. Проверка «есть в файле» через множество работает мгновенно, через список было бы заметно дольше:

a = [int(x) for x in open('chisla.txt')]
s = set(a)
k = 0
for i in range(len(a) - 1):
    if a[i] + a[i + 1] in s:
        k += 1
print(k)

Это была последняя тема. Всё, что нужно из Python для ЕГЭ, у тебя есть. Дальше в уроках по номерам эти кирпичи будут собираться в решения.