Словари и их применение
TODO это план прошлогодней лекции, подправить
Hash-функция
Обязательные свойства:
- Однозначность (функция!)
- Много → мало (⇒ взаимонеоднозначность)
Дополнительные свойства зависят от свойств хешируемого множества!
- Различие для «почти похожих» параметров
Например, n//1024 — плохая функция, а n%1014 — получше
- равномерное (или другое заданное) распределение на множестве значений
- (более сильно) непредсказуемое расстояние между значениями на почти похожих операндах
например, x%65536 vs int(f"{sin(x+1):14.13f}"[-5:])
Одно равномерное, другое (несколько) непредсказуемое ( а равномерное ли?)
- Невосстановимость исходного значения/значения с коллизией из хеша (иначе как перебором области определения)
Редкость или отсутствие hash collision на определённом множестве
Замечания:
- ⇒ всегда можно подобрать множество, на котором нужное свойство не выполняется
- зная свойства множества, можно подобрать «почти идеальную» hash-функцию
Хеш-таблицы
Задача: есть множество {E} объектов: |{E}|=N , в хранилище лежат k объектов этого множества
Задача поиска значения в хранилище — O(k) в общем случае
Если N невелико и для всего множества ∃ возможность перенумеровать все элементы {E}, скорость поиска — константа: массив/list из N True/False (принадлежит ли k-й элемент хранилищу)
Если N велико, но ∃ однозначная хеш-функция — та же структура, только из хешей
Когда хеш-функция неоднозначна (всегда), возможны коллизии
- ⇒ хранить сам элемент для проверки, равны или элементы, если равны хеши.
- Обрабатывать коллизии и хранить несколько элементов с одинаковыми хешами (поиск по которым будет уже линеен по количеству коллизий)
- Либо хранить »ведро» (bucket) таких элементов
Перехешировать: например, взять следующий слот, но лучше — куда-нибудь далеко (hash(x^hash(x)) или что-нибудь такое), особенно, если свойство «разброса» в исходной функции не соблюдается (
Множества и hash()
Множества в Python реализованы именно так.
Функция hash(), её отличие от id()
- Только неизменяемые объекты (почему)
например, frozenset()
Элементы множества неупорядочены
Словари
Задача: хранить произвольные объекты, каждый из которых взаимно однозначно соответствует хорошо хешируемому ключу.
просто list() (ключ — 0, 1, …)
dict — как массив с константными элементами вместо индекса
- Задание и обращение к элементу
- Циклческий констуктор
Элементы словаря упорядочены по времени добавления
- Работа со словарём
keys(), values(), items()
- итератор из словаря
До Python3.6 словари были неупорядочены — как множества; сейчас способ более хитрый (см. https://docs.python.org/3/whatsnew/3.6.html#whatsnew36-compactdict и далее по ссылкам)
Словари внутри 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}
- Именные параметры функции
(если успеем)
Мелкий изврат: def tree(): return defaultdict(tree) (тут)
Д/З
Прочитать про словари в учебнике и в документации