Хеширование, множества и словари
Разбор Д/З
Повторение: строки
- как последовательности (+особенности)
- строковые методы
- байтовые строки и кодировки
Хеширование
Определение: (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
3, 4, 2, 9, 1, 5, 6, 7, 8, 3, 6
3
EJudge: MostPopular 'Самые популярные'
Ввести строку, состоящую из разделённых пробелами последовательностей маленьких и больших латинских букв. Вывести, сколько различных слов (без учёта регистра) встречается в этой строке чаще всего.
dAh Dit dah dIT dAH Dit GIgly diGLy biglY GiGly bOOm quack OH quack
2
EJudge: DungeonMap 'Карта подземелья'
Вводится карта проходимых в обе стороны тоннелей подземлья в виде строк, содержащих разделённые пробелом названия двух пещер, которые соединяет соответствующий тоннель. Две последние строки не содержат пробелов — это название входа в подземелье и название выхода. Вывести "YES", если из входа можно попасть в выход, и "NO" в противном случае. Пары могут повторяться или содержать одинаковые слова.
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
NO
TODO
- разбор задачи