Словари

Материал из Институт биоинформатики
Перейти к: навигация, поиск
Dict.jpg

Словарем (dictionary) в Python называется тип ассоциативного массива[1] или хеш-таблицы[2], элементом которого являются пара «ключ: значение». Пары «ключ: значение» хранятся в неотсортированном порядке. Ключом в словаре может быть любой уникальный неизменяемый объект: строка, целое число или кортеж. Значений по одному ключу может быть множество, любого типа, включая вложенный словарь.

Структура словаря

Словари в Python реализованы как хеш-таблицы с быстрым доступом. Хеш-таблица — это динамическая структура данных, которая реализует интерфейс ассоциативного массива, то есть позволяет хранить пару «ключ: значение» и выполнять 3 операции: добавление и удаление пары, поиск по ключу.[3] Основным преимуществом хэш-таблиц является минимальное время поиска ключей, и в лучшем случае — это O(1), которое достигается путем присваивания каждому ключу индекса (хэшированием). Этот способ значительно превосходит стандартный поиск по массиву, смысл которого заключается в сравнении подстроки с каждым элементом массива и занимает О(n) времени. Правда, в процессе присвоения индекса может случится коллизия, и у двух элементов окажется одинаковый индекс. Существует много способов для разрешения коллизий, но мы не будем углубляться в них. [4] [5]

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

Создать словарь можно несколькими способами:

Прямым способом

d = {} # с этого момента словарь уже можно считать созданным
dict = {"key": "value"}
dict = {"key1": "value1", "key2": ["value2", 567]} # или такой способ, здесь сразу видно, что по одному ключу можно хранить сразу несколько разных по типу значений, 
# которые записываются в квадратных скобках через запятую

0.png

С использованием функции dict().

d = dict(name="Vasya", age=46, country={"Russia":"Uryupinsk"}, profession=["woodcutter","plowman"])
#обратите внимание, что по ключу "country" можно вызвать новый словарь
d = dict([("name", "Vasya"), ("age", 46), ("country", {"Russia":"Uryupinsk"}), ("profession", ["woodcutter","plowman"])])
#обе сроки при исполнении сделают одно и тоже, только в первом случае не нужно брать названия в кавычки

1.png

С помощью функции fromkeys() — словарь по списку ключей с пустыми значениями.

d = {}.fromkeys(["name", "age", "country", "profession"], )
#ключи с нулевыми значениями
d = {}.fromkeys(["name", "age", "country", "profession"], "NA")
#ключи с одинаковым значением "NA"
d = {}.fromkeys(["name", "age", "country", "profession"], [34, "NA"])
#или сразу со списком одинаковых значений

2.png

Слияние двух списков в словарь. Для слияния необходимы списки одинаковой размерности.

l1 = ('key1', 'key2', 'key3') 
l2 = ('val1', 'val2', 'val3') 
d = dict(zip(l1,l2)) # {'key3': 'val3', 'key2': 'val2', 'key1': 'val1'}


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

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

Методы словарей

Про каждый метод можно прочитать на официальной странице с документацией [6]

Методы словарей
d.dict() Создает словарь
d.clear() Удаляет все элементы из словаря
d.copy() Создает псевдокопию словаря
d.deepcopy() Создает полную копию словаря
d.get('key') Возвращает значение по ключу
d.items() возвращает список значений
d.keys() Возвращает список ключей
d.setdefault() Возвращает значение по ключу
d.pop('key') Извлекает значение по ключу, с последующим удалением ключа
d.popitem() Возвращает произвольную пару «ключ: значение» с последующим удалением
d.update(other_d) Изменяет словарь, вернее изменяет элементы на те, что указанны в другом словаре (other_d)
d.values() Возвращает список значений


Работа этих методов на практике.

Создадим словарь и будем рассматривать работу функций на его примере.

d = {'name': 'Vasya', 'profession': ['woodcutter', 'plowman'], 'country': {'Russia': 'Uryupinsk'}, 'age': 46}

С помощью функции len() можно сосчитать количество элементов в словаре.

l = len(d) # 4

Удалим содержимое словаря.

d.clear() # d = {}

При использовании метода copy() создается переменная с привязкой к словарю d. Это значит, что все операции выполняемые с каждым из них изменяют один словарь, на который они оба ссылаются.

t = d.copy() # t = {'name': 'Vasya', 'profession': ['woodcutter', 'plowman'], 'country': {'Russia': 'Uryupinsk'}, 'age': 46}
# если мы выполним t.clear(), то t = {} и d = {} станут пустыми

Создание полной копии словаря.

h = d.deepcopy() # создаем копию, не привязанную к d

Реализация поиска значения по ключу, d.get(<Ключ>[, <Значение по умолчанию>]) - если ключ присутствует в словаре, то метод возвращает значение, соответствующее этому ключу. Если ключ отсутствует, то возвращается значение None или значение, указанное во втором параметре.

d.get('profession') #  ['woodcutter', 'plowman']
d.get('children', 0) # y = 0

Создание списка из всех пар «ключ: значение».

d.items() # dict_items([('country', {'Russia': 'Uryupinsk'}), ('age', 46), ('name', 'Vasya'), ('profession', ['woodcutter', 'plowman'])])

Список из ключей.

d.keys() # dict_keys(['age', 'country', 'profession', 'name'])

Значение по ключу. Метод d.setdefault(<Ключ>[, <Значение по умолчанию>]) возвращает значение, если ключ присутствует в словаре. Если ключ отсутствует, то вставляется новый элемент со значением, указанным во втором параметре. Если второй параметр не указан, значением нового элемента будет None.

d.setdefault("children") # {'name': 'Vasya', 'profession': ['woodcutter', 'plowman'], 'country': {'Russia': 'Uryupinsk'}, 'age': 46, 'children': None}
d.setdefault("children", 0) # {'name': 'Vasya', 'profession': ['woodcutter', 'plowman'], 'country': {'Russia': 'Uryupinsk'}, 'age': 46, 'children': 0}

Метод pop() возвращает пару по ключу и удаляет её из массива, в случае отсутствия возвращается значение из второго параметра. Если ключ отсутствует и второй параметр не указан, то бросается исключение 'KeyError'.

d.pop('key') # ['woodcutter', 'plowman'], d = {'name': 'Vasya', 'country': {'Russia': 'Uryupinsk'}, 'age': 46}

Метод popitems() возвращает и удаляет случайную пару.

d.popitems() # ('age', 46)
# d = {'name': 'Vasya', 'country': {'Russia': 'Uryupinsk'},'profession': ['woodcutter', 'plowman']}

"Склеивание" двух словарей. Происходит объединение ключей и значений одного словаря с ключами и значениями другого, просто перезаписывая значения с одинаковыми ключами.

new_d = {"maried":"yes"}
d.update(new_d) # d = {'name': 'Vasya', 'maried': 'yes', 'country': {'Russia': 'Uryupinsk'}}

Создание кортежа из значений.

d.values() # values_d = [['woodcutter', 'plowman'], 'yes', 'Vasya', 46, {'Russia': 'Uryupinsk'}]

Операции со словарями

Словари являются изменяемым типом данных: можно изменять, добавлять и удалять элементы. Также к словарям можно применять стандартные операторы сравнения или использовать для работы вcтроенные функции.

Запись элементов

Словари изначально можно создавать пустыми и потом добавлять в него пары «ключ: значение». Добавить или изменить элемент можно с помощью следующей записи. Здесь важно помнить, что если вы передаете значению по уже существующему ключу, то значение меняется на новое, старое при этом удаляется. В качестве значения можно присваивать строки, числа, списки или новый словарь.

d = {'name': 'Vasya', 'profession': ['woodcutter', 'plowman'], 'country': {'Russia': 'Uryupinsk'}, 'age': 46}
d["married"] = "Yes" # добавили новую пару ключ-значение
d["age"] = 48 # заменили значение

4.PNG

Удаление элементов

Удаление элемента словаря осуществляется с помощью функции del. Обращаемся к удаляемому элементу по ключу, и из словаря удаляется сразу пара «ключ: значение».

d = {'name': 'Vasya', 'profession': ['woodcutter', 'plowman'], 'country': {'Russia': 'Uryupinsk'}, 'age': 46}
del d["age"]
d = {'name': 'Vasya', 'profession': ['woodcutter', 'plowman'], 'country': {'Russia': 'Uryupinsk'}}

Сортировка словаря

Как мы помним, ключи и привязанные к ним значения хранятся в словаре в случайном порядке, собственно, при выводе словаря целиком это можно увидеть. Но если мы хотим отсортировать ключи, например, в алфавитном порядке или по величине значения ключа, то следует воспользоваться функцией sorted. Правда, этот метод работает только тогда, типы ключей одинаковые, т.е. все ключи являются str или только int. После сортировки формируется список ключей.

d = {'name': 'Vasya', 'profession': ['woodcutter', 'plowman'], 'country': {'Russia': 'Uryupinsk'}, 'age': 46}
t = sorted(d) # t = ['age', 'country', 'name', 'profession']

Сортировать словарь по значениям с помощью встроенных функций невозможно, но мы рассмотрим ниже, как можно инвертировать словарь и вывести отсортированные значения.

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

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

Учет повторов

Словари можно использовать, когда нам нужно что-то сосчитать: число вхождения букв в фразу или слов в текст, тогда мы можем написать следующий скрипт.

d = {} # создаем пустой словарь
string = "Now is better than never"
for i in string: # для каждого символа в строке
    if i not in d: # если символа нет словаре, тогда создаем ключ со значением 1
        d[i] = 1
    else: # если символ уже есть
        d[i] += 1 # то увеличиваем его значение на один
for i, value in d.items(): # для каждой пары ключ и значения в словаре d 
    print (i, value) # выводим ключ и его значение

Для подсчета слов нужно только добавить string.split( ) — разделить строку на слова.

Инвертирование словаря

Что делать, если нам нужно поменять местами ключ-значение.

def invert_dict(d):
    new_dict = {}# создаем словарь
    for key, value in d.items(): # для каждой пары ключ и значения в словаре d
        new_dict.setdefault(value, []).append(key) #  создаем ключ равный значению и присваиваем ему значение равное ключу
    return new_dict # возвращаем словарь
d = {'box': 'red','ball': 'black','pyramid': 'red','pen': 'black'}
invert_dict(d)

5.PNG

Графы в словарях

Графами называются сети, состоящие из вершин (узлов), соединенных ребрами или дугами. В ориентированных графах соединения между узлами имеют направление и называются дугами; в неориентированных графах соединения не имеют направления и называются ребрами. Мы сосредоточимся на реализации ориентированных графах. Графы легко реализуются с помощью списков и словарей.

6 1.png

Запишем этот граф через словарь, где ключи будут вершинами графа. Для каждого ключа соответствующее значение - это список, содержащий вершины, соединенные прямой дугой из данной вершины

graph = {
         7: [11, 8],
         5: [11],
         3: [8, 10],
         11: [2, 9, 10],
         8: [9]}

Дальше этот словарь можно использовать для операций, применяемых для работы с графами.

Литература

  1. Ассоциативный массив, https://ru.wikipedia.org/wiki/%D0%90%D1%81%D1%81%D0%BE%D1%86%D0%B8%D0%B0%D1%82%D0%B8%D0%B2%D0%BD%D1%8B%D0%B9_%D0%BC%D0%B0%D1%81%D1%81%D0%B8%D0%B2
  2. Хеш-таблица, https://ru.wikipedia.org/wiki/%D0%A5%D0%B5%D1%88-%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D0%B0
  3. Введение в хеш-таблицы, https://bitsofmind.wordpress.com/2008/07/28/introduction_in_hash_tables/
  4. Хеш-таблицы, http://neerc.ifmo.ru/wiki/index.php?title=%D0%A5%D0%B5%D1%88-%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D0%B0
  5. Хеш-таблицы в Python, https://habrahabr.ru/post/247843/
  6. Документация, https://docs.python.org/3/tutorial/datastructures.html?highlight=dictionary#dictionaries