Словари и множества в Python
Множества
Множество в языке Питон — это структура данных, эквивалентная множествам в математике. Множество может состоять из различных элементов, порядок элементов в множестве не определен. В множество можно добавлять и удалять элементы, можно перебирать элементы множества, можно выполнять операции над множествами (объединение, пересечение, разность). Можно проверять принадлежность элементу множества.
В отличии от массивов, где элементы хранятся в виде последовательного списка, в множествах порядок хранения элементов не определен (более того, элементы множества хранятся не подряд, как в списке, а при помощи хитрых алгоритмов). Это позволяет выполнять операции типа «проверить принадлежность элемента множеству» быстрее, чем просто перебирая все элементы множества.
Элементами множества может быть любой неизменяемый тип данных: числа, строки, кортежи. Изменяемые типы данных не могут быть элементами множества, в частности, нельзя сделать элементом множества список (но можно сделать кортеж) или другое множество. Требование неизменяемости элементов множества накладывается особенностями представления множества в памяти компьютера.
Задание множеств
Множество задается перечислением всех его элементов в фигурных скобках. Например:
A = {1, 2, 3}
Исключением является пустое множество, которое можно создать при помощи функции set(). Если функции set передать в качестве параметра список, строку или кортеж, то она вернет множество, составленное из элементов списка, строки, кортежа. Например:
A = set('qwerty')
print(A)
выведет {'e', 'q', 'r', 't', 'w', 'y'}.
Каждый элемент может входить в множество только один раз, порядок задания элементов не важен. Например, программа:
A = {1, 2, 3}
B = {3, 2, 3, 1}
print(A == B)
выведет True, так как A и B — равные множества.
Каждый элемент может входить в множество только один раз. set('Hello') вернет множество из четырех элементов: {'H', 'e', 'l', 'o'}.
Работа с элементами множеств
Узнать число элементов в множестве можно при помощи функции len.
Перебрать все элементы множества (в неопределенном порядке!) можно при помощи цикла for:
C = {1, 2, 3, 4, 5}
for elem in C:
print(elem)
Проверить, принадлежит ли элемент множеству можно при помощи операции in, возвращающей значение типа bool:
i in A
Аналогично есть противоположная операция not in.
Для добавления элемента в множество есть метод add:
A.add(x)
Для удаления элемента x из множества есть два метода: discard и remove. Их поведение различается только в случае, когда удаляемый элемент отсутствует в множестве. В этом случае метод discard не делает ничего, а метод remove генерирует исключение KeyError.
Наконец, метод pop удаляет из множества один случайный элемент и возвращает его значение. Если же множество пусто, то генерируется исключение KeyError.
Из множества можно сделать список при помощи функции list.
Перебор элементов множества
При помощи цикла for можно перебрать все элементы множества:
Primes = {2, 3, 5, 7, 11}
for num in Primes:
print(num)
Операции с множествами
С множествами в питоне можно выполнять обычные для математики операции над множествами.
A | B A.union(B) | Возвращает множество, являющееся объединением множеств A и B. |
A |= B A.update(B) | Добавляет в множество A все элементы из множества B. |
A & B A.intersection(B) | Возвращает множество, являющееся пересечением множеств A и B. |
A &= B A.intersection_update(B) | Оставляет в множестве A только те элементы, которые есть в множестве B. |
A - B A.difference(B) | Возвращает разность множеств A и B (элементы, входящие в A, но не входящие в B). |
A -= B A.difference_update(B) | Удаляет из множества A все элементы, входящие в B. |
A ^ B A.symmetric_difference(B) | Возвращает симметрическую разность множеств A и B (элементы, входящие в A или в B, но не в оба из них одновременно). |
A ^= B A.symmetric_difference_update(B) | Записывает в A симметрическую разность множеств A и B. |
A <= B A.issubset(B) | Возвращает true, если A является подмножеством B. |
A >= B A.issuperset(B) | Возвращает true, если B является подмножеством A. |
A < B | Эквивалентно A <= B and A != B |
A > B | Эквивалентно A >= B and A != B |
Словари
Обычные списки (массивы) представляют собой набор пронумерованных элементов, то есть для обращения к какому-либо элементу списка необходимо указать его номер. Номер элемента в списке однозначно идентифицирует сам элемент. Но идентифицировать данные по числовым номерам не всегда оказывается удобно. Например, маршруты поездов в России идентифицируются численно-буквенным кодом (число и одна цифра), также численно-буквенным кодом идентифицируются авиарейсы, то есть для хранения информации о рейсах поездов или самолетов в качестве идентификатора удобно было бы использовать не число, а текстовую строку.
Структура данных, позволяющая идентифицировать ее элементы не по числовому индексу, а по произвольному, называется словарем или ассоциативным массивом. Соответствующая структура данных в языке Питон называется dict.
Рассмотрим простой пример использования словаря. Заведем словарь Capitals, где индексом является название страны, а значением — название столицы этой страны. Это позволит легко определять по строке с названием страны ее столицу.
# Создадим пустой словарь Capitals
Capitals = dict()
# Заполним его несколькими значениями
Capitals['Russia'] = 'Moscow'
Capitals['Ukraine'] = 'Kyiv'
Capitals['USA'] = 'Washington'
# Считаем название страны
print('В какой стране вы живете?')
country = input()
# Проверим, есть ли такая страна в словаре Capitals
if country in Capitals:
# Если есть - выведем ее столицу
print('Столица вашей страны', Capitals[country])
else:
# Запросим название столицы и добавив его в словарь
print('Как называется столица вашей страны?')
city = input()
Capitals[country] = city
Итак, каждый элемент словаря состоит из двух объектов: ключа и значения. В нашем примере ключом является название страны, значением является название столицы. Ключ идентифицирует элемент словаря, значение является данными, которые соответствуют данному ключу. Значения ключей — уникальны, двух одинаковых ключей в словаре быть не может.
В жизни широко распространены словари, например, привычные бумажные словари (толковые, орфографические, лингвистические). В них ключом является слово-заголовок статьи, а значением — сама статья. Для того, чтобы получить доступ к статье, необходимо указать слово-ключ.
Другой пример словаря, как структуры данных — телефонный справочник. В нем ключом является имя, а значением — номер телефона. И словарь, и телефонный справочник хранятся так, что легко найти элемент словаря по известному ключу (например, если записи хранятся в алфавитном порядке ключей, то легко можно найти известный ключ, например, бинарным поиском), но если ключ неизвествен, а известно лишь значение, то поиск элемента с данным значением может потребовать последовательного просмотра всех элементов словаря.
Особенностью ассоциативного массива является его динамичность: в него можно добавлять новые элементы с произвольными ключами и удалять уже существующие элементы. При этом размер используемой памяти пропорционален размеру ассоциативного массива. Доступ к элементам ассоциативного массива выполняется хоть и медленнее, чем к обычным массивам, но в целом довольно быстро.
В языке Питон как ключом может быть произвольный неизменяемый тип данных: целые и действительные числа, строки, кортежи. Ключом в словаре не может быть множество, но может быть элемент типа frozenset: специальный тип данных, являющийся аналогом типа set, который нельзя изменять после создания. Значением элемента словаря может быть любой тип данных, в том числе и изменяемый.
Когда нужно использовать словари
Словари нужно использовать в следующих случаях:
- Подсчет числа каких-то объектов. В этом случае нужно завести словарь, в котором ключами являются объекты, а значениями — их количество.
- Хранение каких-либо данных, связанных с объектом. Ключи — объекты, значения — связанные с ними данные. Например, если нужно по названию месяца определить его порядковый номер, то это можно сделать при помощи словаря Num['January'] = 1; Num['February'] = 2; ....
- Установка соответствия между объектами (например, «родитель—потомок»). Ключ — объект, значение — соответствующий ему объект.
- Если нужен обычный массив, но при этом масимальное значение индекса элемента очень велико, но при этом будут использоваться не все возможные индексы (так называемый «разреженный массив»), то можно использовать ассоциативный массив для экономии памяти.
Создание словаря
Пустой словарь можно создать при помощи функции dict() или пустой пары фигурных скобок {} (вот почему фигурные скобки нельзя использовать для создания пустого множества). Для создания словаря с некоторым набором начальных значений можно использовать следующие конструкции:
Capitals = {'Russia': 'Moscow', 'Ukraine': 'Kyiv', 'USA': 'Washington'}
Capitals = dict(Russia = 'Moscow', Ukraine = 'Kyiv', USA = 'Washington')
Capitals = dict([("Russia", "Moscow"), ("Ukraine", "Kyiv"), ("USA", "Washington")])
Capitals = dict(zip(["Russia", "Ukraine", "USA"], ["Moscow", "Kyiv", "Washington"]))
Первые два способа можно использовать только для создания небольших словарей, перечисляя все их элементы. Кроме того, во втором способе ключи передаются как именованные параметры функции dict, поэтому в этом случае ключи могут быть только строками, причем являющимися корректными идентификаторами. В третьем и четвертом случае можно создавать большие словари, если в качестве аргументов передавать уже готовые списки, которые могут быть получены не обязательно перечислением всех элементов, а любым другим способом построены по ходу исполнения программы. В третьем способе функции dict нужно передать список, каждый элемент которого является кортежем из двух элементов: ключа и значения. В четвертом способе используется функция zip, которой передается два списка одинаковой длины: список ключей и список значений.
Работа с элементами словаря
Основная операция: получение значения элемента по ключу, записывается так же, как и для списков: A[key]. Если элемента с заданным ключом не существует в словаре, то возникает исключение KeyError.
Другой способ определения значения по ключу — метод get: A.get(key). Если элемента с ключом get нет в словаре, то возвращается значение None. В форме записи с двумя аргументами A.get(key, val) метод возвращает значение val, если элемент с ключом key отсутствует в словаре.
Проверить принадлежность элемента словарю можно операциями in и not in, как и для множеств.
Для добавления нового элемента в словарь нужно просто присвоить ему какое-то значение: A[key] = value.
Для удаления элемента из словаря можно использовать операцию del A[key] (операция возбуждает исключение KeyError, если такого ключа в словаре нет. Вот два безопасных способа удаления элемента из словаря. Способ с предварительной проверкой наличия элемента:
if key in A:
del A[key]
Способ с перехватыванием и обработкой исключения:
try:
del A[key]
except KeyError:
pass
Еще один способ удалить элемент из словаря: использование метода pop: A.pop(key). Этот метод возвращает значение удаляемого элемента, если элемент с данным ключом отсутствует в словаре, то возбуждается исключение. Если методу pop передать второй параметр, то если элемент в словаре отсутствует, то метод pop возвратит значение этого параметра. Это позволяет проще всего организовать безопасное удаление элемента из словаря: A.pop(key, None).
Перебор элементов словаря
Можно легко организовать перебор ключей всех элементов в словаре:
for key in A:
print(key, A[key])
Следующие методы возвращают представления элементов словаря. Представления во многом похожи на множества, но они изменяются, если менять значения элементов словаря. Метод keys возвращает представление ключей всех элементов, метод values возвращает представление всех значений, а метод items возвращает представление всех пар (кортежей) из ключей и значений.
Соответственно, быстро проверить, если ли значение val среди всех значений элементов словаря A можно так: val in A.values(), а организовать цикл так, чтобы в переменной key был ключ элемента, а в переменной val было его значение можно так:
for key, val in A.items():
print(key, val)
Задача №3749. Количество различных чисел
Дан список чисел, который может содержать до 100000 чисел. Определите, сколько в нем встречается различных чисел.
Примечание. Эту задачу на Питоне можно решить в одну строчку.
Входные данные
Вводится список целых чисел. Все числа списка находятся на одной строке.
Выходные данные
Выведите ответ на задачу.
Примеры
Ввод | Вывод |
1 2 3 2 1 | 3 |
Ввод | Вывод |
1 2 3 4 5 6 7 8 9 10 | 10 |
Ввод | Вывод |
1 2 3 4 5 1 2 1 2 7 3 | 6 |
Решение
print(len(set([int(i) for i in input().split()])))
Задача №3750. Количество совпадающих
Даны два списка чисел, которые могут содержать до 100000 чисел каждый. Посчитайте, сколько чисел содержится одновременно как в первом списке, так и во втором.
Примечание. Эту задачу на Питоне можно решить в одну строчку.
Входные данные
Вводятся два списка чисел. Все числа каждого списка находятся на отдельной строке.
Выходные данные
Выведите ответ на задачу.
Примеры
Ввод | Вывод |
1 3 2 4 3 2 |
2 |
Решение
print(len(set(input().split()) & set(input().split())))
Задача №3751. Пересечение множеств
Даны два списка чисел, которые могут содержать до 10000 чисел каждый. Выведите все числа, которые входят как в первый, так и во второй список в порядке возрастания.
Примечание. И даже эту задачу на Питоне можно решить в одну строчку.
Входные данные
Вводятся два списка целых чисел. Все числа каждого списка находятся на отдельной строке.
Выходные данные
Выведите ответ на задачу.
Примеры
Ввод | Вывод |
1 3 2 4 3 2 |
2 3 |
Решение
a = sorted(list(set([int(i) for i in input().split()]) & set([int(i) for i in input().split()])))
for row in a:
print(row, end=' ')
Задача №3752. Встречалось ли число раньше
Во входной строке записана последовательность чисел через пробел. Для каждого числа выведите слово YES (в отдельной строке), если это число ранее встречалось в последовательности или NO, если не встречалось.
Входные данные
Вводится список чисел. Все числа списка находятся на одной строке.
Выходные данные
Выведите ответ на задачу.
Примеры
Ввод | Вывод |
1 2 3 2 3 4 | NO NO NO YES YES NO |
Решение
a = [int(i) for i in input().split()]
f = set()
for i in a:
if i in f:
print("YES")
else:
print("NO")
f.add(i)
Задача №3754. Количество слов в тексте
Во входном файле (вы можете читать данные из файла input.txt) записан текст. Словом считается последовательность непробельных символов идущих подряд, слова разделены одним или большим числом пробелов или символами конца строки.
Определите, сколько различных слов содержится в этом тексте.
Входные данные
Вводится текст.
Выходные данные
Выведите ответ на задачу.
Примеры
Ввод | Вывод |
She sells sea shells on the sea shore; The shells that she sells are sea shells I'm sure. So if she sells sea shells on the sea shore, I'm sure that the shells are sea shore shells. |
19 |
Решение
print(len(set(open('input.txt').read().split())))
Задача №3760. Словарь синонимов
Вам дан словарь, состоящий из пар слов. Каждое слово является синонимом к парному ему слову. Все слова в словаре различны. Для одного данного слова определите его синоним.
Входные данные
Программа получает на вход количество пар синонимов N. Далее следует N строк, каждая строка содержит ровно два слова-синонима. После этого следует одно слово.
Выходные данные
Программа должна вывести синоним к данному слову.
Примечание
Эту задачу можно решить и без словарей (сохранив все входные данные в списке), но решение со словарем будет более простым.
Примеры
Ввод | Вывод |
3 Hello Hi Bye Goodbye List Array Goodbye |
Bye |
Решение
n = int(input())
s = {}
for i in range(n):
a = input().split()
s[a[0]] = a[1]
s[a[1]] = a[0]
print(s[input()])
Задача №3767. Англо-латинский словарь
Однажды, разбирая старые книги на чердаке, школьник Вася нашёл англо-латинский словарь. Английский он к тому времени знал в совершенстве, и его мечтой было изучить латынь. Поэтому попавшийся словарь был как раз кстати.
К сожалению, для полноценного изучения языка недостаточно только одного словаря: кроме англо-латинского необходим латинско-английский. За неимением лучшего он решил сделать второй словарь из первого.
Как известно, словарь состоит из переводимых слов, к каждому из которых приводится несколько слов-переводов. Для каждого латинского слова, встречающегося где-либо в словаре, Вася предлагает найти все его переводы (то есть все английские слова, для которых наше латинское встречалось в его списке переводов), и считать их и только их переводами этого латинского слова.
Помогите Васе выполнить работу по созданию латинско-английского словаря из англо-латинского.
Входные данные
В первой строке содержится единственное целое число N — количество английских слов в словаре. Далее следует N описаний. Каждое описание содержится в отдельной строке, в которой записано сначала английское слово, затем отделённый пробелами дефис (символ номер 45), затем разделённые запятыми с пробелами переводы этого английского слова на латинский. Переводы отсортированы в лексикографическом порядке. Порядок следования английских слов в словаре также лексикографический.
Все слова состоят только из маленьких латинских букв, длина каждого слова не превосходит 15 символов. Общее количество слов на входе не превышает 100000.
Выходные данные
Выведите соответствующий данному латинско-английский словарь, в точности соблюдая формат входных данных. В частности, первым должен идти перевод лексикографически минимального латинского слова, далее — второго в этом порядке и т.д. Внутри перевода английские слова должны быть также отсортированы лексикографически.
Примеры
Ввод | Вывод |
3 apple - malum, pomum, popula fruit - baca, bacca, popum punishment - malum, multa |
7 baca - fruit bacca - fruit malum - apple, punishment multa - punishment pomum - apple popula - apple popum - fruit |
Решение
from collections import defaultdict
d = defaultdict(list)
N = int(input())
for i in range(N):
latin = [str(j) for j in input().replace(',' , '').split()]
english = latin[0]
latin.remove('-')
for slovo in latin[1:]:
d[slovo].append(english)
print(len(d))
for i in sorted(d.keys()):
print(i, '-', ', ' .join(d[i]))