Словари

• Списки и индексирование
  • Недостаток: индекс — только 0…N

Что нужно? Таблица вида

•  произвольный ключ1: произвольный объект
   произвольный ключ2: произвольный объект
   …

  • с уникальными ключами

• Вариант моделирования: список пар [(ключ0, объект0), (ключ1, объект1), …]

  • Недостатки: медленный поиск (линия против константы)
  • Упражнения с индексом

• Вариант: упорядоченный список пар

  • Бинарный поиск

  • Медленные аналоги push() и pop() (с сохранением упорядоченности)

Есть решение: хеш-таблица

• Ключ должен быть хешируемый — т. е. неизменяемый

• Значение произвольное
• Если хеш-функция идеальна, поиск практически как по индексу
• Немножко кушает память, потому что хеш-таблица должна быть не очень заполнена

Словари

• Задание
  • Циклический конструктор тоже есть
• Использование — как списки, только вместо индексов — произвольный константные объекты
  • Нету секций, понятное дело
• Элементы хранятся в порядке добавления
• Операция объединения и другие

Зачем нужны?

• «Картотека», «Cловарь» и т. п.

• Счетчики и прочая статистика вида имя: данные

• «Разреженные матрицы» — конечно, медленно, лучше освоить NumPy

• …

• В самом питоне — locals() и globals()

Использование в цикле:

• .keys(), .values(), items()

  • при попытке превратить словарь в последовательность (множественное связывание, цикл for, вообще везде) — подставляется именно .keys()

…

Множества

Множества — по сути просто такие наборы ключей от словарей.

• Задание: {1, 3, 5, 7, 9}, set(последовательность)

  • Возможен циклический коструктор (такой же, как в списках)

Элементы множества

• Только константные типы
• Уникальны

• Лежат внутри множества в неопределённом порядке

• Можно добавлять — .add() и забирать какой-то — .pop()

• Можнос проверять наличие элемент in множество

  • Это быстрая операция (в идеале — константа + сравнение на равенство двух элементов)

  • ⇒ Если нужно часть проверять наличие чего-то в списке чего-то, делайте не список множество

Теоретико-множественные операции:

• Объединение A | B

• Пересечение A & B

• Разность A - B (это же дополнение B до A)

• Симметрическая разность A ^ B

   1 >>> A, B = {1, 2, 3, 4}, set(range(3,7))
   2 >>> A | B
   3 {1, 2, 3, 4, 5, 6}
   4 >>> A & B
   5 {3, 4}
   6 >>> A - B
   7 {1, 2}
   8 >>> A ^ B
   9 {1, 2, 5, 6}
  10 >>>
  11 

Д/З

Напоминаю, что для вывода последовательности через пробел можно воспользоваться конструкцией print(*последовательность) — для начала попробуйте сами в командной строке, если ещё не.

0. Прочитать и прощёлкать про множества и словари

   • На pythontutor про словари

   • На pythontutor про множества

   • в учебнике

1. EJudge: MostPopular 'Самые популярные'

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

   Input:

   dAh Dit dah dIT dAH Dit GIgly diGLy biglY GiGly bOOm quack OH quack

   Output:

   2

2. EJudge: PairCounter 'Количество пар'

   Ввести строку и вывести сколько различных пар букв (без учёта регистра) можно в ней найти. Буквы проверять с помощью .isalpha()

   Input:

   аwба%Ба б7

   Output:

   3

3. EJudge: PublicFriend 'Знаком со всеми'

   Вводятся в столбик пары натуральных чисел через запятую. Каждая пара M, N обозначает взаимное знакомство людей под номерами M и N. Ввод заканчивается парой 0, 0 (не учитывается, и вообще человек N считается незнакомым с человеком N ). Вывести через пробел в порядке возрастания номера тех, кто знаком со всеми остальными, или пустую строку, если таких нет.

   Input:

   7, 9
   1, 7
   9, 2
   9, 2
   9, 7
   2, 9
   9, 2
   2, 9
   7, 1
   9, 2
   9, 2
   2, 1
   7, 2
   7, 9
   7, 1
   7, 1
   0, 0

   Output:

   2 7

4. EJudge: FarGalaxy 'В далёкой галактике'

   Ввести построчно четвёрки вида «число число число слово», где первые три числа — это координаты галактики по имени «слово» (некоторые галактики могут называться одинаково, но координаты у всех разные). Последняя строка ввода не содержит пробелов и не учитывается. Вывести в алфавитном порядке имена любых двух наиболее удалённых друг от друга галактик. Считается, что одинаковых расстояний в списке нет.

   Input:

   35.764 -797.636 -770.320 almost
   88.213 -61.688 778.457 gene
   -322.270 -248.555 -812.730 trend
   721.262 630.355 968.287 dow
   -895.519 -970.173 97.282 non
   -561.036 -350.840 -723.149 disco
   -151.546 -900.962 -658.862 bidder
   -716.197 478.576 -695.843 hawaii
   -744.664 -173.034 -11.211 sad
   -999.968 990.467 650.551 erik
   .

   Output:

   almost erik