Словари и множества в Python
Множество в языке Python — это структура данных, эквивалентная множествам в математике. Элементы могут быть различных типов. Порядок элементов не определён.
Действия, которые можно выполнять с множеством:
- добавлять и удалять элементы,
- проверять принадлежность элемента множеству,
- перебирать его элементы,
- выполнять операции над множествами (объединение, пересечение, разность).
Операция “проверить принадлежность элемента” выполняется в множестве намного быстрее, чем в списке.
Элементами множества может быть любой неизменяемый тип данных: числа, строки, кортежи.
Изменяемые типы данных не могут быть элементами множества, в частности, нельзя сделать элементом множества список (вместо этого используйте неизменяемый кортеж) или другое множество. Требование неизменяемости элементов множества накладывается особенностями представления множества в памяти компьютера.
Задание множеств
Множество задается перечислением в фигурных скобках. Например:
Исключением явлеется пустое множество:
Если функции set передать в качестве параметра список, строку или кортеж, то она вернет множество, составленное из элементов списка, строки, кортежа. Например:
Каждый элемент может входить в множество только один раз.
Работа с элементами множеств
| Операция | Значение |
|---|---|
| x in A | принадлежит ли элемент x множеству A (возвращают значение типа bool ) |
| x not in A | то же, что not x in A |
| A.add(x) | добавить элемент x в множество A |
| A.discard(x) | удалить элемент x из множества A |
| A.remove(x) | удалить элемент x из множества A |
| A.pop() | удаляет из множества один случайный элемент и возвращает его |
Поведение discard и remove различается тогда, когда удаляемый элемент отсутствует в множестве: discard не делает ничего, а метод remove генерирует исключение KeyError . Метод pop также генерирует исключение KeyError , если множество пусто.
При помощи цикла for можно перебрать все элементы множества:
Из множества можно сделать список при помощи функции list :
Упражнение №1
Вывести на экран все элементы множества A, которых нет в множестве B.
Операции с множествами, обычные для математики
Упражнение №2
Даны четыре множества:
Найти элементы, принадлежащие множеству E :
Словарь (ассоциативный массив)
В массиве или в списке индекс — это целое число. Традиционной является следующая ситуация:
А как реализовать обратное соответствие?
При помощи списка или массива это сделать невозможно, нужно использовать ассоциативный массив или словарь.
В словаре индекс может быть любого неизменяемого типа! Индексы, как и сами хранимые значения, задаются явно:
При попытке обратиться к несуществующему элементу ассоциативного массива мы получаем исключение KeyError .
Особенностью ассоциативного массива является его динамичность: в него можно добавлять новые элементы с произвольными ключами и удалять уже существующие элементы.
При этом размер используемой памяти пропорционален размеру ассоциативного массива. Доступ к элементам ассоциативного массива выполняется хоть и медленнее, чем к обычным массивам, но в целом довольно быстро.
Значения ключей уникальны , двух одинаковых ключей в словаре быть не может. А вот значения могут быть одинаковыми.
Ключом может быть произвольный неизменяемый тип данных: целые и действительные числа, строки, кортежи. Ключом в словаре не может быть множество, но может быть элемент типа frozenset: специальный тип данных, являющийся аналогом типа set, который нельзя изменять после создания. Значением элемента словаря может быть любой тип данных, в том числе и изменяемый.
Создание словаря
Пустой словарь можно создать при помощи функции dict() или пустой пары фигурных скобок <> (вот почему фигурные скобки нельзя использовать для создания пустого множества).
Для создания словаря с некоторым набором начальных значений можно использовать следующие конструкции:
Также можно использовать генерацию словаря через Dict comprehensions:
Это особенно полезно, когда нужно «вывернуть» словарь наизнанку:
Операции с элементами словарей
Перебор элементов словаря по ключу
Представления элементов словаря
Представления во многом похожи на списки, но они остаются связанными со своим исходным словарём и изменяются, если менять значения элементов словаря.
- Метод keys возвращает представление ключей всех элементов.
- Метод values возвращает представление всех значений.
- Метод items возвращает представление всех пар (кортежей) из ключей и значений.
Учтите что итерироваться по представлениям изменяя словарь нельзя
Можно, если в начале скопировать представление в список
Пример использования словаря
Когда нужно использовать словари
Словари нужно использовать в следующих случаях:
- Подсчет числа каких-то объектов. В этом случае нужно завести словарь, в котором ключами являются объекты, а значениями — их количество.
- Хранение каких-либо данных, связанных с объектом. Ключи — объекты, значения — связанные с ними данные. Например, если нужно по названию месяца определить его порядковый номер, то это можно сделать при помощи словаря Num[‘January’] = 1; Num[‘February’] = 2; .
- Установка соответствия между объектами (например, “родитель—потомок”). Ключ — объект, значение — соответствующий ему объект.
- Если нужен обычный массив, но при этом масимальное значение индекса элемента очень велико, но при этом будут использоваться не все возможные индексы (так называемый “разреженный массив”), то можно использовать ассоциативный массив для экономии памяти.
Практическая работа по использованию словарей
Упражнение №3. Подсчет слов
Дан текст на некотором языке. Требуется подсчитать сколько раз каждое слово входит в этот текст и вывести десять самых часто употребяемых слов в этом тексте и количество их употреблений.
В качестве примера возьмите файл с текстом лицензионного соглашения Python /usr/share/licenses/python/LICENSE .
Подсказка №1: Используйте словарь, в котором ключ — слово, а знчение — количество таких слов.
Подсказка №2: Точки, запятые, вопросы и восклицательные знаки перед обработкой замените пробелами(используйте punctuation из модуля string).
Подсказка №3: Все слова приводите к нижнему регистру при помощи метода строки lower() .
Подсказка №4: По окончании сбора статистики нужно пробежать по всем ключам из словаря и найти ключ с максимальным значением.
Упражнение №4. Перевод текста
Дан словарь task4/en-ru.txt с однозначным соответствием английских и русских слов в таком формате:
cat — кошка
dog — собака
mouse — мышь
house — дом
eats — ест
in — в
too — тоже
Здесь английское и русское слово разделены двумя табуляциями и минусом: ‘\t-\t’ .
В файле task4/input.txt дан текст для перевода, например:
Требуется сделать подстрочный перевод с помощью имеющегося словаря и вывести результат в output.txt . Незнакомые словарю слова нужно оставлять в исходном виде.
Упражнение №5. Страны и Языки
Дан список стран и языков на которых говорят в этой стране в формате <Название Страны> : <язык1> <язык2> <язык3> . в файле task5/input.txt. На ввод задается N — длина списка и список языков. Для каждого языка укажите, в каких странах на нем говорят.
| Ввод | Вывод |
|---|---|
| 3 | |
| азербайджанский | Азербайджан |
| греческий | Кипр Греция |
| китайский | Китай Сингапур |
Упражнение №6. Сделать русско-английский словарь
В файле task6/en-ru.txt находятся строки англо-русского словаря в таком формате:
Здесь английское слово (выражение) и список русских слов (выражений) разделены двумя табуляциями и минусом: ‘\t-\t’ .
Требуется создать русско-английский словарь и вывести его в файл ru-en.txt в таком формате:
Порядок строк в выходном файле должен быть словарным с человеческой точки зрения (так называемый лексикографический порядок слов). То есть выходные строки нужно отсортировать.
Упражнение №7. Синхронизация словарей
Даны два файла словарей: task7/en-ru.txt и task7/ru-en.txt (в формате, описанном в упражнении №6).
Требуется синхронизировать и актуализировать их содержимое.
Упражнение №8. Добродушные соседи
В одном очень дружном доме, где живет Фёдор, многие жильцы оставляют ключи от квартиры соседям по дому, например на случай пожара или потопа, да и просто чтобы покормили животных или полили цветы.
Вернувшись домой после долгих странствий, Фёдор обнаруживает, что потерял свои ключи и соседей дома нет. Но вдруг у домофона он находит чужие ключи. Помогите Федору найти ключи от своей квартиры в квартирах соседей.
На ввод подается файл input.txt, в котором в первой строке записано три числа через пробел N — номер квартиры Фёдора, M — номер квартиры от которой Федор нашел ключи, K — ключ от этой квартиры. Далее i-я строка хранит описание ключей запертых в i-й квартире в формате <m_i0 — номер квартиры> <k_i0 — ключ>,<m_i1 — номер квартиры> <k_i1 — ключ>. , причем реальные номера квартир «зашифрованы» ключем от i-й квартиры(Ki) и находятся по формуле m_ij’ = m_ij — Ki. Номера квартир начинаются с 0 (кпримеру вторая строка файла соответствует 0-й квартире).
Нужно вывести ключ от квартиры Федора или None если его найти не получилось.
| Ввод | Вывод |
|---|---|
| 4 0 1 | 1 |
| 1 1,2 0,3 1,4 0 | |
| 3 0 | |
| 5 1,6 0 | |
| 1 1 | |
| 2 1 |
Подсказка: используйте словарь для хранения ключей от еще не открытых комнат и множество для уже проверенных комнат.
Упражнение №9. Факультативно: генератор бреда
Дан текст-образец, по которому требуется сделать генератор случайного бреда на основе Марковских цепей.
Sets in Python
In today’s article we will explore sets in Python. You must have learnt in your Math class about sets and if you remember a set is a collection of elements but today we will dig into the details of sets in Python which is close to, but not the same as, mathematical sets. Set is one of the four built-in data types in Python along with List, Tuple, and Dictionary, all with different qualities and usage. It is used to store collections of data and are written with curly brackets.
In Python, sets store unordered values and cannot have multiple occurrences of the same element. It makes sets highly useful to efficiently remove duplicate values from a list or tuple and to perform common math operations like unions and intersections. For example, let S be a set of even numbers less than or equal to 10.
As I said, sets can neither have any order nor have repeated values.
You can see in the above code each element can appear in the set only once. Now, Let W be a set
In the example above, the order of the set W is not preserved.
Initialize a Set
In order to create a new empty set, you use set()
Add and Delete Values from a Set
We can use update() to add new elements to a set. It adds elements from a set (passed as an argument) to the set. In the example below, I have used update() to add new elements to the empty set S.
To delete an element from a set. We can use remove() and it only works if the element to be deleted is present in the set.
Whereas discard() works whether the element to be deleted is present in the set or not.
We can use pop() to remove a random element from the set.
In order to get a sorted list from a set, we use sorted() function.
Immutable Elements
Although a set is mutable i.e. we can add or remove elements from it, the elements of a set are immutable (cannot be changed). Immutable objects include numbers, strings and tuples. In the example below you can see that the elements of a set can be tuples.
but they cannot be lists.
Operations on sets
Python defines many operations on sets. Most operations come in two forms, as a method and as an overload of mathematical operators.
Element of or belongs to: To check if an element is in a set or not we use “in” and “not in” operators.
Subset (A⊆B ): A is a subset of B if set A is included in set B. In other words, all the elements in set A are also elements of set B. You can see in the diagram below. To investigate in Python, whether a set A is a subset of another set B or not, we use issubset() or <=.
Superset (B⊇A): B is a superset of A is another way of saying that A is a subset of B. To examine it in Python, we use issuperset() or >=.
Union (A⋃B): A⋃B has all the elements that belong either to set A or to set B. To find union in Python, we use union() or |.
Intersection (A⋂B): A⋂B has all the elements that belong to both set A and set B. To determine intersection in Python, we use intersection() or &.
Difference (B-A): B-A contains all elements that are in B and not in A. To evaluate difference in Python, we use difference() or -.
Symmetric Difference (A △ B): A △ B comprises all elements that belong to A or B but not to their intersection or contains all elements that are in one of the two sets, but not in both. We use the method symmetric_difference() or ^, to find symmetric difference in Python.
Computing the cartesian Product
The Cartesian product of two sets A and B, denoted A × B, is the set of all possible ordered pairs where the elements of A are first and the elements of B are second. In set-builder notation, A × B = <(a, b) : a ∈ A and b ∈ B>. The code snippet below computes the cartesian product of two sets A and B in Python.
Conclusion
In this article, we have learnt about sets in Python, how to create a set, how to add and remove elements from a set. We went over the operations that can be applied on sets. We also saw that sets themselves are mutable but their elements are immutable. Thank you for reading. I hope you found this article useful. If you have any questions, feel free to reach out in the comments below or through Twitter. Happy Pythoning!
Как создать множество в питоне
- Теория
- Практика
- Stepik.org
Множество (set)
Множество (set) — неупорядоченная коллекция, хранящая набор уникальных значений и поддерживающая для них операции добавления, удаления и определения вхождения.
Также объект множество в Python поддерживает операции, аналогичные операциям с математическими множествами: объединение, пересечение, симметричная разность и вычитание множеств
Создание множества
Множество создается перечислением через запятую всех элементов внутри фигурных скобках.
В случае, если имеются повторяющиеся элементы внутри фигурных скобок, дубли во множестве все равно исчезнут. Множество не терпит среди элементов повторения.
Пустое множество создается при помощи функции set()
Также при помощи функции set() можно создавать множества из других объектов. Если передать строку, то получим множество из символов этой строки.
Также можно передавать функции set() списки и функцию range().
Добавление элемента в множество
Первый способ добавить элемент в множество это вызвать метод add(). При попытке добавить уже существующий элемент во множество никаких ошибок не возникнет
Второй способ добавить элемент в множество это вызвать метод update() и передать ему итерируемый объект: список, строку, range() или множество. Метод update() будет поочередно добавлять каждый элемент итерируемого объекта внутрь множества.
Удаление элемента из множество
Первый способ удалить элемент из множества это вызвать метод discard(value) и передать ему значение, которое хотите удалить. В случае, если в множестве нет значения, исключений не будет.
Второй способ удалить элемент — это вызвать метод remove(value). В случае, если указанного значения в множестве нет, возбуждается исключение KeyError.
Третий способ удалить элемент — вызвать метод pop(). Т.к. множество является неупорядоченной коллекцией, данный метод удалит случайный элемент. При попытке удалить элемент из пустого множества возникнет исключение KeyError.
Операции над множеством
Нахождение длины
Проверка вхождения элемента во множество
Пересечение множеств
При помощи оператора & можно выполнить пересечение множеств. В результат попадут те элементы, которые одновременно принадлежат двум множествам. При этом сами множества не меняются. Если нужно изменить само множество используйте эту операцию с присвоением &=.
Объединение множеств
При помощи оператора | можно выполнить объединение множеств. В результат попадут те элементы, которые принадлежат хотя бы одному из множеств. При этом сами множества не меняются. Если нужно изменить само множество используйте эту операцию с присвоением |=.
Вычитание множеств
При помощи оператора — можно выполнить вычитание множеств. В результат попадут только те элементы, которые принадлежат первому множеству за исключение тех, которые входят во второе.
Python и теория множеств
В Python есть очень полезный тип данных для работы с множествами – это set. Об этом типе данных, примерах использования, и небольшой выдержке из теории множеств пойдёт речь далее.
Следует сразу сделать оговорку, что эта статья ни в коем случае не претендует на какую-либо математическую строгость и полноту, скорее это попытка доступно продемонстрировать примеры использования множеств в языке программирования Python.
Множество
Множество – это математический объект, являющийся набором, совокупностью, собранием каких-либо объектов, которые называются элементами этого множества. Или другими словами:
Что значит неупорядоченная? Это значит, что два множества эквивалентны, если содержат одинаковые элементы. 
Элементы множества должны быть уникальными, множество не может содержать одинаковых элементов. Добавление элементов, которые уже есть в множестве, не изменяет это множество. 
Множества, состоящие из конечного числа элементов, называются конечными, а остальные множества – бесконечными. Конечное множество, как следует из названия, можно задать перечислением его элементов. Так как темой этой статьи является практическое использование множеств в Python, то я предлагаю сосредоточиться на конечных множествах.
Множества в Python
Множество в Python можно создать несколькими способами. Самый простой – это задать множество перечислением его элементов в фигурных скобках:
Единственное ограничение, что таким образом нельзя создать пустое множество. Вместо этого будет создан пустой словарь:
Для создания пустого множества нужно непосредственно использовать set() :
Также в set() можно передать какой-либо объект, по которому можно проитерироваться (Iterable):
Ещё одна возможность создания множества – это использование set comprehension. Это специальная синтаксическая конструкция языка, которую иногда называют абстракцией множества по аналогии с list comprehension (Списковое включение).
Хешируемые объекты
Существует ограничение, что элементами множества (как и ключами словарей) в Python могут быть только так называемые хешируемые (Hashable) объекты. Это обусловлено тем фактом, что внутренняя реализация set основана на хеш-таблицах. Например, списки и словари – это изменяемые объекты, которые не могут быть элементами множеств. Большинство неизменяемых типов в Python (int, float, str, bool, и т.д.) – хешируемые. Неизменяемые коллекции, например tuple, являются хешируемыми, если хешируемы все их элементы.
Объекты пользовательских классов являются хешируемыми по умолчанию. Но практического смысла чаще всего в этом мало из-за того, что сравнение таких объектов выполняется по их адресу в памяти, т.е. невозможно создать два «равных» объекта.
Скорее всего мы предполагаем, что объекты City(«Moscow») должны быть равными, и следовательно в множестве cities должен находиться один объект.
Этого можно добиться, если определить семантику равенства для объектов класса City :
Чтобы протокол хеширования работал без явных и неявных логических ошибок, должны выполняться следующие условия:
- Хеш объекта не должен изменяться, пока этот объект существует
- Равные объекты должны возвращать одинаковый хеш
Свойства множеств
Тип set в Python является подтипом Collection (про коллекции), из данного факта есть три важных следствия:
- Определена операция проверки принадлежности элемента множеству
- Можно получить количество элементов в множестве
- Множества являются iterable-объектами
Принадлежность множеству
Проверить принадлежит ли какой-либо объект множеству можно с помощью оператора in . Это один из самых распространённых вариантов использования множеств. Такая операция выполняется в среднем за O(1) с теми же оговорками, которые существуют для хеш-таблиц.
Мощность множества
Мощность множества – это характеристика множества, которая для конечных множеств просто означает количество элементов в данном множестве. Для бесконечных множеств всё несколько сложнее.
Перебор элементов множества
Как уже было отмечено выше, множества поддерживают протокол итераторов, таким образом любое множество можно использовать там, где ожидается iterable-объект.
Отношения между множествами
Между множествами существуют несколько видов отношений, или другими словами взаимосвязей. Давайте рассмотрим возможные отношения между множествами в этом разделе.
Равные множества
Тут всё довольно просто – два множества называются равными, если они состоят из одних и тех же элементов. Как следует из определения множества, порядок этих элементов не важен.
Непересекающиеся множества
Если два множества не имеют общих элементов, то говорят, что эти множества не пересекаются. Или другими словами, пересечение этих множеств является пустым множеством.
Подмножество и надмножество
Подмножество множества S – это такое множество, каждый элемент которого является также и элементом множества S. Множество S в свою очередь является надмножеством исходного множества.
Пустое множество является подмножеством абсолютно любого множества.
Само множество является подмножеством самого себя.
Операции над множествами
Рассмотрим основные операции, опредяляемые над множествами.
Объединение множеств
Объединение множеств – это множество, которое содержит все элементы исходных множеств. В Python есть несколько способов объединить множества, давайте рассмотрим их на примерах.
Добавление элементов в множество
Добавление элементов в множество можно рассматривать как частный случай объединения множеств за тем исключением, что добавление элементов изменяет исходное множество, а не создает новый объект. Добавление одного элемента в множество работает за O(1) .
Пересечение множеств
Пересечение множеств – это множество, в котором находятся только те элементы, которые принадлежат исходным множествам одновременно.
При использовании оператора & необходимо, чтобы оба операнда были объектами типа set . Метод intersection , в свою очередь, принимает любой iterable-объект. Если необходимо изменить исходное множество, а не возращать новое, то можно использовать метод intersection_update , который работает подобно методу intersection , но изменяет исходный объект-множество.
Разность множеств
Разность двух множеств – это множество, в которое входят все элементы первого множества, не входящие во второе множество.
Удаление элементов из множества
Удаление элемента из множества можно рассматривать как частный случай разности, где удаляемый элемент – это одноэлементное множество. Следует отметить, что удаление элемента, как и в аналогичном случае с добавлением элементов, изменяет исходное множество. Удаление одного элемента из множества имеет вычислительную сложность O(1) .
Также у множеств есть метод differenсe_update , который принимает iterable-объект и удаляет из исходного множества все элементы iterable-объекта. Этот метод работает аналогично методу difference , но изменяет исходное множество, а не возвращает новое.
Симметрическая разность множеств
Симметрическая разность множеств – это множество, включающее все элементы исходных множеств, не принадлежащие одновременно обоим исходным множествам. Также симметрическую разность можно рассматривать как разность между объединением и пересечением исходных множеств.
Как видно из примера выше, число 0 принадлежит обоим исходным множествам, и поэтому оно не входит в результирующее множество. Для операции симметрической разности, помимо оператора ^ , также существует два специальных метода – symmetric_difference и symmetric_difference_update . Оба этих метода принимают iterable-объект в качестве аргумента, отличие же состоит в том, что symmetric_difference возвращает новый объект-множество, в то время как symmetric_difference_update изменяет исходное множество.
Заключение
Я надеюсь, мне удалось показать, что Python имеет очень удобные встроенные средства для работы с множествами. На практике это часто позволяет сократить количество кода, сделать его выразительнее и легче для восприятия, а следовательно и более поддерживаемым. Я буду рад, если у вас есть какие-либо конструктивные замечания и дополнения.