Словари и множества

Перекличка на занятии идёт по списку: староста читает фамилии, в журнал ставится отметка. Но кто-то опоздал, вошёл посреди переклички, и его фамилию прочли второй раз. В журнале оказалось двадцать восемь отметок, а в классе двадцать шесть человек (числа условные). Первая мысль: надо вычеркнуть повторы. Вторая, более полезная: структура, в которой повторы невозможны по определению, уже есть, и называется она множеством.

Рядом живёт задача про голоса. Класс выбирает капитана команды, каждый кладёт в коробку бумажку с именем, и нужно узнать, сколько голосов у каждого. Здесь нужна другая структура, и для неё хватает слов «ключ» и «значение». Оба случая разобраны ниже на том, как их обычно решают сначала неудачно. Со списками вы уже работали? Если нет, сначала загляните в статью про списки и массивы.

Голоса, посчитанные по списку

Первое решение почти всегда такое. Заводится список пар: имя и счётчик, то есть для двух кандидатов что-то вроде «Полина, два голоса» и «Кирилл, один голос». На каждую бумажку из коробки программа проходит по списку пар, ищет в нём нужное имя, а если находит, прибавляет единицу; если не находит, добавляет новую пару с единицей. Вложенный цикл, поиск, условие, добавление: десяток строк, и все они работают.

Для двадцати кандидатов и тысячи бумажек такое решение вполне годится. На каждую бумажку уходит не больше двадцати проверок, всего двадцать тысяч, и компьютер их не заметит. Переписывать такой код на словарь «чтобы было быстрее» не нужно. Выигрыш в скорости на таких размерах невидим, а вот выигрыш в ясности виден сразу: десять строк превращаются в одну, и её труднее написать с ошибкой.

Скорость вмешивается позже. Если голосов миллион, а различных имён сто тысяч, то в среднем на каждый голос приходится пятьдесят тысяч проверок, а на весь подсчёт — десятки миллиардов. Тогда та же программа работает часами там, где на школьных размерах ответ появлялся мгновенно. И знать, откуда это берётся, нужно заранее: поиск по списку пар проверяет их подряд, а размер списка вырос.

Тот же подсчёт словарём

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

• itogi = {}
• for imya in golosa: itogi[imya] = itogi.get(imya, 0) + 1
• print(itogi)

Вторая строка делает всё сразу. Выражение itogi.get(imya, 0) возвращает счётчик имени, а если такого имени ещё нет, то нуль; к нему прибавляется единица, и результат записывается обратно. Для списка голосов Полина, Кирилл, Полина на экране появится {'Полина': 2, 'Кирилл': 1}. Начиная с Python 3.7 порядок ключей в словаре совпадает с порядком, в котором они появились.

В роли ключа выступает то, по чему вы ищете: фамилия, номер в журнале, пара «имя и день недели». Словарь {1: 'Лиза', 2: 'Марк'} отвечает на zhurnal[2] словом «Марк», и в отличие от списка номера здесь не обязаны идти подряд от нуля.

Если обратиться к ключу, которого нет, напрямую, itogi['Тимур'], Python остановит программу ошибкой KeyError: прямое обращение предполагает, что ключ уже есть. Поэтому в подсчёте используют get с запасным значением, а для проверки пишут 'Тимур' in itogi: проверка возвращает «да» или «нет» и ничего не ломает. Пройти по всему словарю можно через itogi.items(), который отдаёт пары «ключ и значение» по очереди.

Для подсчёта в стандартной библиотеке есть готовый Counter из модуля collections: itogi = Counter(golosa), и у него же метод most_common(1), который возвращает победителя вместе с числом голосов. Знать нужно оба способа: Counter короче, но на экзамене и в задачах учителя часто просят написать подсчёт словарём руками, и без этого шага Counter превращается в заклинание.

Множество: перекличка без повторов

Множество хранит только различные элементы. Повторы там отбрасываются при добавлении, и записи об этом не остаётся. Двадцать восемь отметок из журнала превращаются в двадцать шесть выражением len(set(otmetki)): сначала множество, потом его размер.

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

У множества есть особенности, из-за которых его нельзя считать списком без повторов:

• порядка нет: при выводе элементы идут в произвольной последовательности, которая может меняться от запуска к запуску, и обращения по номеру (m[0]) не существует
• элементами могут быть только неизменяемые значения: числа, строки, кортежи; список внутрь множества положить нельзя
• пустое множество записывается set(), потому что пара пустых фигурных скобок создаёт пустой словарь
• нужен порядок на выводе, сортируйте результат: sorted(m)

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

Если нужно убрать повторы и при этом оставить порядок, на выручку приходит словарь: list(dict.fromkeys(otmetki)) сохраняет первое появление каждой фамилии и выбрасывает остальные, потому что ключи словаря не повторяются, а их порядок запоминается.

Кто был на обоих занятиях

Два занятия, понедельник и среда, и два множества отметившихся:

• ponedelnik = {"Дина", "Егор", "Жанна"}
• sreda = {"Егор", "Жанна", "Игорь"}

Теперь вопросы к ним решаются одной операцией. Кто был на обоих занятиях: ponedelnik & sreda даёт Егора и Жанну. Кто хоть раз пришёл: ponedelnik | sreda даёт четверых. Кто был только в понедельник: ponedelnik - sreda, это Дина. Кто пришёл на одно из двух, но не на оба: ponedelnik ^ sreda, Дина и Игорь.

Как бы это решалось списками? Для каждого из понедельника пройти по списку среды и проверить, есть ли там тот же человек: [x for x in spisok_pn if x in spisok_sr]. Решение работает и даже короткое, но у него два изъяна. Каждая проверка in просматривает список среды подряд, так что для больших списков вы получаете то же самое замедление, что и с голосами. А если Егор отмечен в понедельник дважды, то в результате он окажется дважды: список не знает, что повтор нужно убрать. Множество исправляет оба изъяна сразу, и потому на задачи вида «кто есть там и там» его и стоит применять первым делом.

Где данные портятся до множества

Самая обидная ошибка со словарями и множествами случается не в них. Имя кандидата, написанное на одной бумажке как «Полина», на другой как «полина», а на третьей «Полина » с пробелом на конце, словарь сочтёт тремя разными людьми. Поэтому ключ и элемент множества приводят к одному виду до вставки; как это делается со строками, разобрано в статье про строки и работу с текстом, а строки из файла приходят с переводом строки на конце, о чём рассказано в статье про работу с файлами.

На экзамене и на занятиях

В заданиях ЕГЭ по информатике с файлами нередко требуется посчитать, сколько раз встречается каждое значение, или проверить, есть ли значение в наборе: обе задачи решаются словарём или множеством, и список на больших файлах работает слишком долго. Какие это задания, показывает карта первой части, а как устроена вся работа, описано в статье про структуру ЕГЭ по информатике. Порядок тем школьного курса, в который эта тема входит, изложен в статье про информатику в школе.

Словарь стоит давать раньше, чем принято, сразу после списков. Ученик, который однажды написал подсчёт перебором пар, а потом увидел ту же задачу в одну строку, запоминает различие надолго. Если же словарь приходит в конце курса, он выглядит ещё одной надстройкой, и неудобство, которое он снимает, ученик уже успел забыть.

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

Начать поиск:

• репетиторы по информатике, все предложения каталога
• репетиторы по информатике для подготовки к ЕГЭ
• репетиторы по информатике для 10–11 класса
• репетиторы по информатике для студентов

Вопросы и ответы

Можно ли использовать список как ключ словаря? Нет, Python сообщит об ошибке «unhashable type». Ключом может быть только неизменяемое значение: число, строка, кортеж. Если ключ составной (например, пара «имя и день»), берите кортеж.

Почему множество при выводе идёт в другом порядке, чем я его записал? Множество порядка не хранит и выводит элементы в том виде, как они лежат внутри. Для строк этот порядок способен меняться от запуска к запуску. Если важна последовательность, перед выводом нужно вызвать sorted.

Чем множество отличается от списка без повторов? Список помнит порядок и допускает повторы; к его элементам можно обратиться по номеру. Множество не помнит порядок, не допускает повторов и номеров не знает, зато быстро отвечает на вопрос «есть ли такой элемент» и умеет объединять, пересекать и вычитать себя из других множеств. Если порядок и номера нужны, а повторы мешают, делайте sorted от множества и получайте уже новый список.

Что быстрее: in для списка или для множества? Для множества в среднем быстрее, и время почти не растёт с размером. Но на создание множества уходит проход по всему списку, так что для однократной проверки список остаётся быстрее.

Нужны ли словари на экзамене? Прямого вопроса «что такое словарь» нет. Зато в задачах с файлами встречается такая постановка: в файле записаны значения, нужно найти то, что встречается чаще остальных. Список справится с маленьким файлом и застрянет на большом, а словарь уложится в разумное время на обоих, поэтому знать его стоит даже тем, кто идёт на экзамен только за порогом.