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

Список (list)

Для начала вспомним операции работы со списками.

У разработчиков типа данных list Python было много вариантов каким сделать его во время реализации. Каждый выбор повлиял на то, как быстро список мог выполнять операции. Одно из решений было сделать список оптимальным для частых операций.

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

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

A = {1, 2, 3}

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

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'}

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

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

Поведение 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]

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

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

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

>>> 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 "<stdin>", line 1, in <module>
KeyError: 'Yesterday'

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

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

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

Пустой словарь можно создать при помощи функции 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 "<stdin>", 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

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

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

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

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

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

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

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