Хеширование, множества и словари

Разбор Д/З

Повторение: строки

• как последовательности (+особенности)
• строковые методы
• байтовые строки и кодировки

Хеширование

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

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

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

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

• hash()

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

Множества

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

  • +frozenset

Словари

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

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

  • почему нет frozendict?

• Устройство современных (Python3.6+) словарей (описано здесь): прямая таблица объектов + хеш-таблица индексов + пометка на удаление вместо удаления + переупаковка

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

Д/З

• Почитать

  • Про хеширование в документации, и далее по ссылкам

    • требуемые свойства метода .__hash__()

    • отмена рандомизации хеша с помощью переменной окружения PYTHONHASHSEED

  • Про множества в учебнике и в документации

  • Про словари в учебнике и в документации

• Разобраться с кодом, имитирующим хеш-таблицы

  • Задать вопросы, если что непонятно

• EJudge: ThreeSquares 'Три квадрата'

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

  • Пояснение. Поскольку входная последовательность обрабатывается eval(), она может быть, например, такой: (1+i%10 for i in range(100000)), в этом случае ответ — тоже 3

  Input:

  3, 4, 2, 9, 1, 5, 6, 7, 8, 3, 6

  Output:

  3

  • ВНИМАНИЕ! В тестах по задаче до 2017-11-09 содержалась ошибка!

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

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

  Input:

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

  Output:

  2

• EJudge: DungeonMap 'Карта подземелья'

  Вводится карта проходимых в обе стороны тоннелей подземлья в виде строк, содержащих разделённые пробелом названия двух пещер, которые соединяет соответствующий тоннель. Две последние строки не содержат пробелов — это название входа в подземелье и название выхода. Вывести "YES", если из входа можно попасть в выход, и "NO" в противном случае. Пары могут повторяться или содержать одинаковые слова.

  Input:

  markers jumping
  jumping guinea
  skiing pre
  markers gauge
  skiing mpeg
  solar jackson
  skiing solar
  guinea gauge
  mpeg honor
  pre honor
  guinea gauge
  pre mpeg
  markers guinea
  markers gauge
  honor mpeg
  markers jumping
  skiing
  jumping

  Output:

  NO

  • генратор тестовых даных (вам понадобится google-10000-english.txt)

• 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

  • генратор тестовых даных (вам понадобится google-10000-english.txt)