Структура данных множество python

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

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

Действия, которые можно выполнять с множеством:

1. добавлять и удалять элементы,
2. проверять принадлежность элемента множеству,
3. перебирать его элементы,
4. выполнять операции над множествами (объединение, пересечение, разность).

Операция “проверить принадлежность элемента” выполняется в множестве намного быстрее, чем в списке.

Элементами множества может быть любой неизменяемый тип данных: числа, строки, кортежи.

Изменяемые типы данных не могут быть элементами множества, в частности, нельзя сделать элементом множества список (вместо этого используйте неизменяемый кортеж) или другое множество. Требование неизменяемости элементов множества накладывается особенностями представления множества в памяти компьютера.

Задание множеств

Множество задается перечислением в фигурных скобках. Например:

Исключением явлеется пустое множество:

A = set() # A -- множество D = <> # D -- не пустое множество, а пустой словарь! 

Если функции set передать в качестве параметра список, строку или кортеж, то она вернет множество, составленное из элементов списка, строки, кортежа. Например:

>>> A = set('qwerty') >>> print(A) 'e', 'q', 'r', 't', 'w', 'y'>. 

Каждый элемент может входить в множество только один раз.

>>> A = 1, 2, 3> >>> B = 3, 2, 3, 1> >>> print(A == B) # A и B — равные множества. True >>> set('Hello') 'H', 'e', 'l', 'o'> 

Работа с элементами множеств

Операция	Значение
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 можно перебрать все элементы множества:

Primes = 2, 3, 5, 7, 11> for num im Primes: print(num) 

Из множества можно сделать список при помощи функции list :

>>> A = 1, 2, 3, 4, 5> >>> B = list(A) [1, 2, 3, 4, 5] 

Упражнение №1

Вывести на экран все элементы множества A, которых нет в множестве B.

A = set('bqlpzlkwehrlulsdhfliuywemrlkjhsdlfjhlzxcovt') B = set('zmxcvnboaiyerjhbziuxdytvasenbriutsdvinjhgik') for x in A: . 

Операции с множествами, обычные для математики

Упражнение №2

A = set('0123456789') B = set('02468') C = set('12345') D = set('56789') 

Найти элементы, принадлежащие множеству E :

Словарь (ассоциативный массив)

В массиве или в списке индекс — это целое число. Традиционной является следующая ситуация:

>>> Days = ['Sunday', 'Monday', 'Tuesday', 'Wednessday', 'Thursday', 'Friday', 'Saturday'] >>> Days[0] 'Sunday' >>> Days[1] 'Monday' 

А как реализовать обратное соответствие?

>>> Days['Sunday'] 0 >>> Days['Monday'] 1 

При помощи списка или массива это сделать невозможно, нужно использовать ассоциативный массив или словарь.

В словаре индекс может быть любого неизменяемого типа! Индексы, как и сами хранимые значения, задаются явно:

Days =  'Sunday': 0, 'Monday': 1, 'Tuesday': 2, 'Wednessday': 3, 'Thursday': 4, 'Friday': 5, 'Saturday': 6 > >>> Days['Sunday'] 0 >>> Days['Monday'] 1 >>> Days['Yesterday'] Traceback (most recent call last): File "", line 1, in module> KeyError: 'Yesterday' 

При попытке обратиться к несуществующему элементу ассоциативного массива мы получаем исключение KeyError .

Особенностью ассоциативного массива является его динамичность: в него можно добавлять новые элементы с произвольными ключами и удалять уже существующие элементы.

>>> Days['Yesterday'] = -1 >>> print(Days['Yesterday']) -1 

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

Значения ключей уникальны , двух одинаковых ключей в словаре быть не может. А вот значения могут быть одинаковыми.

>>> Days['Tomorrow'] = -1 >>> Days['Yesterday'] == Days['Tomorrow'] True 

Ключом может быть произвольный неизменяемый тип данных: целые и действительные числа, строки, кортежи. Ключом в словаре не может быть множество, но может быть элемент типа frozenset: специальный тип данных, являющийся аналогом типа set, который нельзя изменять после создания. Значением элемента словаря может быть любой тип данных, в том числе и изменяемый.

Создание словаря

Пустой словарь можно создать при помощи функции dict() или пустой пары фигурных скобок <> (вот почему фигурные скобки нельзя использовать для создания пустого множества).

Для создания словаря с некоторым набором начальных значений можно использовать следующие конструкции:

Capitals = 'Russia': 'Moscow', 'Ukraine': 'Kiev', 'USA': 'Washington'> Capitals = dict(Russia = 'Moscow', Ukraine = 'Kiev', USA = 'Washington') Capitals = dict([("Russia", "Moscow"), ("Ukraine", "Kiev"), ("USA", "Washington")]) Capitals = dict(zip(["Russia", "Ukraine", "USA"], ["Moscow", "Kiev", "Washington"])) 

Также можно использовать генерацию словаря через Dict comprehensions:

Cities = ["Moscow", "Kiev", "Washington"] States = ["Russia", "Ukraine", "USA"] CapitalsOfState = state: city for city, state in zip(Cities, States)> 

Это особенно полезно, когда нужно «вывернуть» словарь наизнанку:

StateByCapital = CapitalsOfState[state]: state for state in CapitalsOfState> 

Операции с элементами словарей

Перебор элементов словаря по ключу

for key in A: print(key, A[key]) 

Представления элементов словаря

Представления во многом похожи на списки, но они остаются связанными со своим исходным словарём и изменяются, если менять значения элементов словаря.

• Метод keys возвращает представление ключей всех элементов.
• Метод values возвращает представление всех значений.
• Метод items возвращает представление всех пар (кортежей) из ключей и значений.

>>> A = dict(a='a', b='b', c='c') >>> k = A.keys() >>> v = A.values() >>> k, v (dict_keys(['c', 'b', 'a']), dict_values(['c', 'b', 'a'])) >>> A['d'] = 'a' >>> k, v (dict_keys(['d', 'c', 'b', 'a']), dict_values(['a', 'c', 'b', 'a'])) 

Учтите что итерироваться по представлениям изменяя словарь нельзя

>>> for key in A.keys(): . del A[key] . Traceback (most recent call last): File "", line 1, in module> RuntimeError: dictionary changed size during iteration 

Можно, если в начале скопировать представление в список

>>> for key in list(A.keys()): . del A[key] . >>> A <> 

Пример использования словаря

# Создадим пустой словать Capitals Capitals = dict() # Заполним его несколькими значениями Capitals['Russia'] = 'Moscow' Capitals['Ukraine'] = 'Kiev' Capitals['USA'] = 'Washington' # Считаем название страны print('В какой стране вы живете?') country = input() # Проверим, есть ли такая страна в словаре Capitals if country in Capitals: # Если есть - выведем ее столицу print('Столица вашей страны', Capitals[country]) else: # Запросим название столицы и добавим его в словарь print('Как называется столица вашей страны?') city = input() Capitals[country] = city 

Когда нужно использовать словари

Словари нужно использовать в следующих случаях:

• Подсчет числа каких-то объектов. В этом случае нужно завести словарь, в котором ключами являются объекты, а значениями — их количество.
• Хранение каких-либо данных, связанных с объектом. Ключи — объекты, значения — связанные с ними данные. Например, если нужно по названию месяца определить его порядковый номер, то это можно сделать при помощи словаря 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. Страны и Языки

Дан список стран и языков на которых говорят в этой стране в формате : . в файле 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-й квартире в формате , . , причем реальные номера квартир «зашифрованы» ключем от 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. Факультативно: генератор бреда

Дан текст-образец, по которому требуется сделать генератор случайного бреда на основе Марковских цепей.

Подробности спрашивайте у семинариста.

Сайт построен с использованием Pelican. За основу оформления взята тема от Smashing Magazine. Исходные тексты программ, приведённые на этом сайте, распространяются под лицензией GPLv3, все остальные материалы сайта распространяются под лицензией CC-BY-SA.

Источник