Знакомство со словарями

Ассоциативные структуры данных

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

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

  • Названия переменных являются ключами к данным, с которыми эти переменные связаны.

  • Аргументы некоторой функции являются ключом к значению, которое эта функция вычисляет, получив такие аргументы.

  • Номер элемента массива является ключом к этому элементу.

У каждой из вышеперичисленных схем есть свои сильные и слабые стороны. Переменные обычно нельзя (а в тех случаях, когда можно, то не рекомендуется без надобности) создавать «изнутри» программы. Номера элементов массива обязаны быть целыми числами (да ещё и в пределах некоторого «непрерывного» диапазона). Функции совершенно универсальны, но многие языки программирования (python, в том числе) по тем или иным причинам накладывают существенные ограничения на процесс их вычисления.

Неким компромиссом между этими тремя ситуациями является тип данных «ассоциативный массив» или, как его называют в python, словарь. Можно считать, что у словарей следующий интерфейс:

# литералы {k1: v1, k2: v2, ... kn: vn}, например
foo = {1: 2, "foo": 3, "bar": "baz"}

# запись
foo[2] = 4  
foo[1] = 3  # изменяет уже записанное значение
del foo[1]  # удаление элемента; выдаёт ошибку, если по указанному 
            # ключу ничего не хранится

# считывание
2 in foo  # == True, если в foo есть элемент по ключу 2
foo[2]    # сам элемент по ключу 2
foo[10]   # если по ключу не хранится элемент, python выдаст ошибку

x = ...
y = foo[x] if x in foo else 3  # безопасное считывание

# вспомогательные операции
len(foo)   # количество хранимых элементов
foo.keys() # последовательность ключей, хранимых в словаре

Пример программы, использующей словари

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

Вот решение, использующее словарь:

def add_word(d,w):
    if w in d: d[w] += 1
    else:      d[w]  = 1

def main():
    text = input()
    words = text.split()
    counts = {}

    for word in words: add_word(counts, word)

    for word in counts: print(word, '->', counts[word])
    
main()

Упражнения

  1. Модифицируйте программу из примера так, чтобы она выводила слова в порядке убывания их количества. Указание: вам могут пригодиться функции sorted и reversed.

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

  3. На вход подаётся строчка с целыми неотрицательными числами. Назовём \(N\) количество этих чисел. Для всех \(k\) от \(1\) до \(N\) программа должна вывести минимальное целое неотрицательное число, которого нет среди первых \(k\) чисел строчки. Асимптотическая сложность алгоритма по-прежнему должна быть ниже квадратичной.

Достаточно удобный способ моделирования всевозможных графов — словарь словарей. А именно, если из вершины x в вершину y идёт ребро с весом w, то его можно задать функцией

def add_edge(g,x,y,w):
    if x in g: g[x][y] = w
    else:      g[x] = {y:w}

Если разрешены множественные рёбра, то вместо одного веса можно хранить массив весов. Неориентированное ребро можно моделировать парой ориентированных.

  1. Напишите программу, получающую в первой строчке числа \(N\) и \(X\), а затем, в каждой из следующих \(N\) строчек — пара чисел, описывающих начало и конец ребра ориентированного невзвешенного графа с кратными рёбрами. Множество вершин этого графа считать множеством целых неотрицательных чисел. Программа должна вычислять следующее:

    1. максимальную исходящую степень вершин
    2. максимальную кратность ребра
    3. наличие ориентированного пути между $0$ и $X$
    4. наличие ориентированного цикла, содержащего вершину $X$
    5. количество нетривиальных компонент связности
    6. количество рёбер после снятия ориентаций и кратностей
    7. остов после снятия ориентаций и кратностей

Пример входа и выхода:

8 3
0 1
0 1
1 0
1 2
2 0
3 4
3 3
3 5

3  # из тройки идёт три ребра
2  # из нуля в единицу идут два ребра
NO
YES  # петля в 3
2
6
0 1, 1 2, 3 4, 3 5