Множества и словари

Хеширование

• Определение: (f(x)=y: {y} << {x})

• Возможные свойства и их применение:
  • равномерное покрытие ОЗ — хеш-таблицы
  • вероятная однозначность на небольшом подмножестве ОО — идентификация

  • невосстановимость x из y — шифрование

  • разброс (в т. ч. для почти похожих x) — много где

• hash()

  • только константные объекты
• Понятие об идеальной хеш-таблице, поиск в ней
• Разрешение коллизий ключей в хеш-таблице: «вёдра» vs повторное хеширование

Множества

• (это хеш-таблицы, как они есть)
  • поправочка: для индексирования используется свёртка хеша по модулю
• Конструктор (в т. ч. циклический)
• операции и методы
• использование
  • …

  • +frozenset

Словари

Хешируется ключ, а хранится произвольный объект ⇒ ассоциативный массив, хеш ключа в качестве индекса объекта

Устройство современных (Python3.6+) словарей (описано здесь):

• Ссылки на объекты хранятся отдельно в «плотной» таблице в порядке добавления
• В разреженой хеш-таблице хранятся индексы в этом массиве
  • ⇒ Да, ещё один уровень косвенности
  • Зато ячейка хеш-таблицы может быть меньше (пока элементов мало — хоть байт)

Свойства:

• Конструктор словаря (+циклический)
• методы

• использование: трансляция, счётчики, кеш (см. пример в учебнике, если успеем, посмотрим)

• Именные параметры функций
• вся правда о пространствах имён

Д/З

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

1. EJudge: PopularWord 'Самое популярное слово'

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

   Input:

   Sed tempus ipsum quis eros tempus lacinia Cras finibus lorem ut lacinia egestas nunc nibh iaculis est convallis tincidunt
   mi mi sed nisl Sed porttitor aliquam elit ullamcorper tincidunt arcu euismod quis Mauris congue elit suscipit leo varius
   facilisis Cras et arcu sodales laoreet est vitae pharetra orci Integer eget nulla dictum aliquet justo semper molestie neque
   Maecenas bibendum lacus tincidunt auctor varius purus felis ullamcorper dui et laoreet ligula ex et risus Donec eget
   fringilla nibh Cras congue tincidunt accumsan Maecenas euismod eleifend elit ut rhoncus tortor sodales a Cras egestas
   finibus lorem non tempor tincidunt aera

   Output:

   tincidunt

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

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

   Input:

   0, 3
   1, 0
   3, 2
   3, 2
   3, 0
   2, 3
   3, 2
   2, 3
   0, 1
   3, 2
   3, 2
   2, 1
   0, 2
   0, 3
   0, 1
   0, 1
   0, 0

   Output:

   0 2

На сегодня заданий больше нет, в следующий раз будет много