⇤ ← Версия 1 от 2020-10-13 12:48:17
49
Комментарий:
|
6716
|
Удаления помечены так. | Добавления помечены так. |
Строка 2: | Строка 2: |
'''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 велико, но ∃ ''однозначная'' хеш-функция — та же структура, только из хешей * Когда хеш-функция неоднозначна (всегда), возможны ''коллизии'' * ⇒ хранить сам элемент для проверки, равны или элементы, если равны хеши. * Обрабатывать коллизии и хранить несколько элементов с одинаковыми хешами (поиск по которым будет уже линеен по количеству коллизий) 1. Либо хранить »ведро» (bucket) таких элементов 1. Перехешировать: например, взять следующий слот, но лучше — куда-нибудь далеко (`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()` {{{#!python Traceback (most recent call last): File "<stdin>", line 1, in <module> NameError: name 'QQ' is not defined >>> globals() {'__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'>} >>> globals()["QQ"]=100500 100500 >>> globals() {'__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} }}} * Именные параметры функции {{{#!python >>> def fun(*argp, **argn): ... print(argp, argn) ... >>> fun(1,2,3,a=4,b=5) (1, 2, 3) {'a': 4, 'b': 5} >>> def fun(a=1, b=2): ... print(a,b) ... >>> d = dict(a="QQ", b="PP") >>> fun(**d) QQ PP >>> d = {"a":"QQ", "b":"QKRQ"} >>> fun(**d) QQ QKRQ }}} * [[https://docs.python.org/3/whatsnew/3.8.html#positional-only-parameters|Ещё вкусности]] ('''если успеем''') * [[py3doc:collections.html#collections.Counter]]a и [[py3doc:collections.html#collections.defaultdict]] * Мелкий изврат: `def tree(): return defaultdict(tree)` ([[https://gist.github.com/hrldcpr/2012250|тут]]) == Д/З == 1.#0 Прочитать про словари [[py3tut:datastructures.html#dictionaries|в учебнике]] и [[py3doc:stdtypes.html#typesmapping|в документации]] |
Словари и их применение
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) (тут)
Д/З
Прочитать про словари в учебнике и в документации