Различия между версиями 1 и 2
Версия 1 от 2020-10-13 12:48:17
Размер: 49
Редактор: FrBrGeorge
Комментарий:
Версия 2 от 2020-10-13 12:52:09
Размер: 6716
Редактор: FrBrGeorge
Комментарий:
Удаления помечены так. Добавления помечены так.
Строка 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
>>> QQ
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
>>> QQ
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 велико, но ∃ однозначная хеш-функция — та же структура, только из хешей

  • Когда хеш-функция неоднозначна (всегда), возможны коллизии

    • ⇒ хранить сам элемент для проверки, равны или элементы, если равны хеши.
    • Обрабатывать коллизии и хранить несколько элементов с одинаковыми хешами (поиск по которым будет уже линеен по количеству коллизий)
      1. Либо хранить »ведро» (bucket) таких элементов
      2. Перехешировать: например, взять следующий слот, но лучше — куда-нибудь далеко (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}
    
  • Именные параметры функции
       1 >>> def fun(*argp, **argn):
       2 ...     print(argp, argn)
       3 ...
       4 >>> fun(1,2,3,a=4,b=5)
       5 (1, 2, 3) {'a': 4, 'b': 5}
       6 
       7 >>> def fun(a=1, b=2):
       8 ...   print(a,b)
       9 ... 
      10 >>> d = dict(a="QQ", b="PP")
      11 >>> fun(**d)
      12 QQ PP
      13 >>> d = {"a":"QQ", "b":"QKRQ"}
      14 >>> fun(**d)
      15 QQ QKRQ
    
  • Ещё вкусности

(если успеем)

Д/З

  1. Прочитать про словари в учебнике и в документации

LecturesCMC/PythonIntro2020/06_DictCollection (последним исправлял пользователь FrBrGeorge 2023-10-19 14:36:21)