Множества и словари
TODO насыпать очевидных примеров 
.
Внимание: подробный рассказ про хеш-функции и хеш-таблицы см. в записях предыдущих лет (в первую очередь 2019)
Коротко про функцию хеширования:
Она должна быть однозначной и переводить область определения в актуально меньшую область значений
- Все остальные свойства — взаимооднозначность, равномерность, невосстановимость и т. п. — необязательны, зависят от применения, и не всегда достижимы.
Множества и hash()
Хеш объекта в python используется в первую очередь для предварительного сравнения
+ Достаточно высокая скорость вычисления (иначе можно сами объекты сравнивать)
+ Фиксированный размер
± Актуальное неравенство для «почти похожих»: например, для чисел из диапазона, совпадающих с точностью до символа строк и т. п.
? «Актуальная взаимнооднозначность» — минимизация коллизий — желательно, но необязательно
- Разброс для почти похожих объектов — не требуется (hash(123456))
- Невосстановимость — не требуется
⇒ Специальная функция hash() — числовой хеш от константного объекта
- создаётся вместе с объектом
- для изменяемого объекта (например, списка) смысла не имеет
соответствует методу .__hash__()
- если хеши не равны, объекты тоже не равны
обратное, в целом, неверно
- Пространство: целое 64 бита
Почему id() — плохая хеш-функция?
id() — уникальность объекта, ничего не знает про равенство
Множества
- Задаются перечислением или сборкой в { }
- Поддерживают теоретико-множественные операции "| & ^ -"
Множества в Python реализованы как хеш-таблицы:
- вычисляется хеш объекта
- вычисляется индекс объекта — остаток от деления хеша на размер таблицы (обычно — 2ⁿ)
- повторное хеширование при коллизии
- размер таблицы приблизительно пропорционален количеству элементов
- + геометрическое масштабирование при заполнении на определённый объём (примерно на ⅓)
константный поиск в среднем (+линейное масштабирование)
Элементы множества не упорядочены (можно заметить следы упорядочивания по хешам, с учётом перехеширования и масштабирования):
Множества — модифицируемые объекты, но есть и константные: frozenset
Дополнительное свойство: хеш составного объекта разный для разных запусков интерпретатора (туда однократно подмешивается случайное значение). Иначе можно было бы подобрать такое множество, на котором операции бы имели линейную сложность.
Словари
Задача: хранить произвольные объекты, каждый из которых однозначно соответствует хорошо хешируемой константе.
(до Python3.6 — множество ключей + ссылка на хранимый объект)
(современный Python) хеш-список (без дыр) + журнал индексов
Операция добавления легче операции удаления (кому нужно удалять из словаря?)
Сохраняет порядок добавления элементов
Использование
dict — как массив с константными элементами вместо индекса
- Задание и обращение к элементу
- Циклический конструктор
- Работа со словарём
keys(), values(), items()
- цикл по словарю
[] vs .get() vs .setdefault()
.update() и прочие методы
Операции | и |=
А почему нет &?
Словари внутри Python
globals()/locals()
1 >>> QQ 2 Traceback (most recent call last): 3 File "<stdin>", line 1, in <module> 4 NameError: name 'QQ' is not defined 5 >>> globals() 6 {'__name__': '__main__', '__doc__': None, '__package__': None, '__loader__': <_frozen_importlib_external.SourceFileLoader object at 0x7f434c1b4190>, '__spec__': None, '__annotations__': {}, '__builtins__': <module 'builtins' (built-in)>, '__cached__': None, 'rlcompleter': <module 'rlcompleter' from '/usr/lib64/python3.7/rlcompleter.py'>} 7 >>> globals()["QQ"]=100500 8 >>> QQ 9 100500 10 >>> globals() 11 {'__name__': '__main__', '__doc__': None, '__package__': None, '__loader__': <_frozen_importlib_external.SourceFileLoader object at 0x7f434c1b4190>, '__spec__': None, '__annotations__': {}, '__builtins__': <module 'builtins' (built-in)>, '__cached__': None, 'rlcompleter': <module 'rlcompleter' from '/usr/lib64/python3.7/rlcompleter.py'>, 'QQ': 100500}
Передача пространства имён как параметра
eval() — интерпретация и вычисление выражения
exec() — интерпретация и выполнение куска кода
И туда, и туда можно передать словарь для того, что это выражение/код увидит в качестве globals() и locals()
1 >>> eval("A+B", None, {"B":234}) 2 357 3 >>> eval("A+B", {"A": 12, "B": 78, "C": -1}) 4 90 5 >>> A=100500 6 >>> eval("A+B", {"A": 12, "B": 78, "C": -1}) 7 90 8 >>> eval("A+B", None, {"A": 12, "B": 78, "C": -1}) 9 90 10 >>> eval("A+B", None, {"B": 78, "C": -1}) 11 100578 12 >>> eval("A+B-C+D-E", dict(zip("ABCDE", range(10, 16)))) 13 8 14
Именные параметры функции
Позиционные параметры — кортеж, именные — словарь.
Ещё немного занудства про параметры функций: значения по умолчанию ≠ именные параметры
Модуль collections
Мелкий изврат: def tree(): return defaultdict(tree) (тут)
- …
Д/З
- Прочитать и прощёлкать
про множества в учебнике и в документации
про словари в учебнике и в документации
документацию к collections
EJudge: SetJuggler 'Манипуляция множествами'
Input:Написать программу-интерпретатор языка манипуляции множествами. На вход подаются слова, разделённые пробелами и переводами строк (слово — последовательность непробельных символов), затем — пустая строка, затем — программа на языке управления множествами, ввод заканчивается пустой строкой. Программа формирует множества и сохраняет их под заданными именами. В начале работы задано единственное множество с именем ALL. Операторы языка работают как с элементами одного множества, так и с элементами нескольких. В этом случае имена перечисляются через запятую без пробелов.
print множества — вывести в отсортированном виде через пробел все элементы множеств
search множества where строка to имя — найти все элементы множеств, содержащие строку, и сформировать из них множество имя
search множества for множества_поиска to имя — найти все элементы множеств, которые содержатся также и в каком-нибудь из множеств_поиска, и сформировать из них множество имя
Output:Ходя на практические кризисы потенциалов, едящее вдали от тени абстракций божество организации знакомилось в религии армии, содействуя сему и ночному оппортунизму. Дифференцирует бесполезного Мазовецкого с периодом, усмехаясь над эволюционными определениями, Рейган утренних абсолютных воскресений. Организация означала характеры ребенком, ходя за исполнителей с лекцией, но не желала между первоначальным воинствующим поражением и элементарным объектом образовываться качествами. Эта и надоедливая шапка извращается исполнителем, но не хочет над комплексным воскресеньем без сред преобразиться четвергом без практики. Способствуя мышам с полем, материализм является государственным четвергом. Собака формулирует натуральную и недоношенную ложку индивиду без структур; она осмыслила университет критическими и утренними качествами, гамадрилами догматизмов нося студенческого Мазовецкого. Абстрагировали над целями с именами индивиды, сказанные о колхознице и являвшиеся этим и идеалистическим университетом. Пьяное условие с теорией смеет между подозрительными материалами среды материальной разработкой без оппортунизма осуществлять единства искусственных стипендий. Формулировал пьяный объект потенциалу познанный поэтический Эзоп с елью и формулировал реформизмы закону, позвонив архаичному процессу. Воскресенья мыслят философией, шумя в студенческой и специфической search ALL where фи to ФИ print ФИ search ALL where ил to ИЛ print ИЛ search ФИ,ИЛ where о to ФИЛО print ФИЛО search ФИЛО for ИЛ to НЕФИЛ print НЕФИЛ
специфической философией, гамадрилами знакомилось осмыслила философией, знакомилось осмыслила специфической философией, знакомилось осмыслила философией,