Занятие 2

Занятие 2: Множества и словари в Python и асимптотика стандартных операций

Цель: Познакомиться с новыми структурами данных — множество (set) и словарь (dir)

Введение

Понятие сложности алгоритмов уже было рассмотрено в первом семестре, при рассмотрении алгоритмов, связанных с сортировками. В данной работе будет рассмотрена трудоемкость стандартных процедур в языке Python а так же рассмотрены две мощные концепциии - множество(set) и словарь(dict).

Трудоемкость будет рассмотренна на примере встроенных методов и операций классов dict и set.

Множество (set)

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

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

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

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

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

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

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

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

A = {1, 2, 3}

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

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

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

In [ ]:
A = set('qwerty')
print(A)

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

In [ ]:
A = {1, 2, 3}
B = {3, 2, 3, 1}
print(A == B) # A и B — равные множества.
In [ ]:
set('Hello')

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

Операция Значение Трудоемкость
x in A принадлежит ли элемент x множеству A (возвращают значение типа bool) $O(1)$
x not in A то же, что not x in A $O(1)$
A.add(x) добавить элемент x в множество A $O(1)$
A.discard(x) удалить элемент x из множества A $O(1)$
A.remove(x) удалить элемент x из множества A $O(1)$
A.pop() удаляет из множества один случайный элемент и возвращает его $O(1)$

Как мы видим, по времени стандартные оперцаии с одним элементом множества выполняются за $O(1)$.

Поведение discard() и remove() различается тогда, когда удаляемый элемент отсутствует в множестве: discard() не делает ничего, а метод remove() генерирует исключение KeyError. Метод pop() также генерирует исключение KeyError, если множество пусто.

При помощи цикла for можно перебрать все элементы множества:

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

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

In [ ]:
A = {1, 2, 3, 4, 5}
B = list(A)

Задание 1 — Вывести на экран все элементы множества A, которых нет в множестве B:

In [ ]:
A = set('bqlpzlkwehrlulsdhfliuywemrlkjhsdlfjhlzxcovt')
B = set('zmxcvnboaiyerjhbziuxdytvasenbriutsdvinjhgik')
for x in A:
    #fix me

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

Операция Значение Трудоемкость
A | B A.union(B) Возвращает множество, являющееся объединением множеств A и B. O(len(A)+len(B))
A | = B A.update(B) Записывает в A объединение множеств A и B. O(len(A)+len(B))
A & B A.intersection(B) Возвращает множество, являющееся пересечением множеств A и B. O(min(len(A), len(B))
A &= B A.intersection_update(B) Записывает в A пересечение множеств A и B. O(min(len(A), len(B))
A - B A.difference(B) Возвращает разность множеств A и B (элементы, входящие в A, но не входящие в B). O(len(A)+len(B))
A -= B A.difference_update(B) Записывает в A разность множеств A и B. O(len(A)+len(B))
A ^ B A.symmetric_difference(B) Возвращает симметрическую разность множеств A и B (элементы, входящие в A или в B, но не в оба из них одновременно). O(len(A)+len(B))
A ^= B A.symmetric_difference_update(B) Записывает в A симметрическую разность множеств A и B. O(len(A)+len(B))
A <= B A.issubset(B) Возвращает True, если A является подмножеством B. O(len(A))
A >= B A.issuperset(B) Возвращает True, если B является подмножеством A. O(len(B))
A < B Эквивалентно A <= B and A != B. O(len(A))
A > B Эквивалентно A >= B and A != B. O(len(B))

В случае, если нужно провести процедуру, затрагивающую все элементы множества, то его трудоемкость будет O(N).

Задание 2 — Даны четыре множества:

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

Найти элементы, принадлежащие множеству $E = ((A\backslash B) \cap (C\backslash D)) \cup ((D\backslash A) \cap (B\backslash C))$

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

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

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

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

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

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

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

In [ ]:
Days = {
    'Sunday': 0,
    'Monday': 1,
    'Tuesday': 2,
    'Wednessday': 3,
    'Thursday': 4,
    'Friday': 5,
    'Saturday': 6
}
Days['Sunday']
In [ ]:
Days['Sunday']
In [ ]:
Days['Yesterday']

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

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

In [ ]:
Days['Yesterday'] = -1
print(Days['Yesterday'])

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

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

In [ ]:
Days['Tomorrow'] = -1
Days['Yesterday'] == Days['Tomorrow']

Ключом может быть произвольный неизменяемый тип данных: целые и действительные числа, строки, кортежи. Ключом в словаре не может быть множество, но может быть элемент типа 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}

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

Операция Значение Трудоемкость
value = A[key] Получение элемента по ключу. Если элемента с заданным ключом в словаре нет, то возникает исключение KeyError. O(1)
value = A.get(key) Получение элемента по ключу. Если элемента в словаре нет, то get возвращает None. O(1)
value = A.get(key, default_value) То же, но вместо None метод get возвращает default_value. O(1)
key in A Проверить принадлежность ключа словарю. O(1)
key not in A То же, что not key in A. O(1)
A[key] = value Добавление нового элемента в словарь. O(1)
del A[key] Удаление пары ключ-значение с ключом key. Возбуждает исключение KeyError, если такого ключа нет. O(1)
if key in A: del A[key] Удаление пары ключ-значение с предварительной проверкой наличия ключа. O(1)
try: del A[key] except KeyError: pass Удаление пары ключ-значение с перехватыванием и обработкой исключения. O(1)
value = A.pop(key) Удаление пары ключ-значение с ключом key и возврат значения удаляемого элемента.Если такого ключа нет, то возбуждается KeyError. O(1)
value = A.pop(key, default_value) То же, но вместо генерации исключения возвращается default_value. O(1)
A.pop(key, None) Это позволяет проще всего организовать безопасное удаление элемента из словаря. O(1)
len(A) Возвращает количество пар ключ-значение, хранящихся в словаре. O(1)

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

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

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

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

  • Метод keys() возвращает представление ключей всех элементов.
  • Метод values() возвращает представление всех значений.
  • Метод items() возвращает представление всех пар (кортежей) из ключей и значений.
In [ ]:
A = dict(a='a', b='b', c='c')
k = A.keys()
v = A.values()
k, v
In [ ]:
A['d'] = 'a'
k, v

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

In [ ]:
for key in A.keys():
    del A[key]

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

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

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

In [ ]:
# Создадим пустой словать 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

Трудоемкость стандартных операций со словарем

Наиболее важной характеристикой словаря является то, что получение и присваивание элемента в словаре являются операциями за $O(1)$. Словари были созданы специально для того, чтобы как можно быстрее получить и установить значения по ключу.

Другая важная операция словаря - проверка наличия ключа в словаре. Операция contains() также работает за $O(1)$ (в случае со списками это занимало $O(N)$), потому что проверка для данного ключа подразумевает простое получение элемента по ключу, которое делается за $O(1)$.

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

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

  • Подсчет числа каких-то объектов. В этом случае нужно завести словарь, в котором ключами являются объекты, а значениями — их количество.
  • Хранение каких-либо данных, связанных с объектом. Ключи — объекты, значения — связанные с ними данные. Например, если нужно по названию месяца определить его порядковый номер, то это можно сделать при помощи словаря 
    Num['January'] = 1 
Num['February'] = 2
...
  • Установка соответствия между объектами (например, “родитель—потомок”). Ключ — объект, значение — соответствующий ему объект.
  • Если нужен обычный массив, но при этом масимальное значение индекса элемента очень велико, но при этом будут использоваться не все возможные индексы (так называемый “разреженный массив”), то можно использовать ассоциативный массив для экономии памяти.
In [ ]: