Словари и их применение
Внимание: подробный рассказ про хеш-функции и хеш-таблицы см. в записях предыдущих лет.
Множества и hash()
id() — уникальность объекта, ничего не знает про равенство
- сравнение двух объектов может быть тяжёлой операцией
hash() — числовой хеш от константного объекта
например, frozenset()
- создаётся вместе с объектом
- для изменяемого объекта (например, списка) смысла не имеет
- если хеши не равны, объекты тоже не равны
Множества в Python реализованы как хеш-таблицы:
- размер таблицы приблизительно пропорционален количеству элементов (изменение размера как в списках)
- повторное хеширование при коллизии
константный поиск в среднем (+линейное масштабирование)
Элементы множества неупорядочены (в действительности, почти упорядочены по хешам, с учётом перехеширования и масштабирования):
Словари
Задача: хранить произвольные объекты, каждый из которых взаимно однозначно соответствует хорошо хешируемому ключу.
просто list() (ключ — 0, 1, …)
(до Python3.6) — множество ключей + ссылка на хранимый объект
(современный Python) хеш-таблица + журнал
- Сохраняет порядок добавления элементов
- Более компактное и быстрое преставление
Более чувствительно к удалениям (кому нужно удалять из словаря?)
dict — как массив с константными элементами вместо индекса
- Задание и обращение к элементу
- Циклческий констуктор
- Работа со словарём
keys(), values(), items()
- итератор из словаря
Словари внутри 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}
- Именные параметры функции
Модуль collections
Мелкий изврат: def tree(): return defaultdict(tree) (тут)
- …
Использование random
Аппаратная случайность: os.getrandom
Работа с датчиком случайный чисел: random
random() (и неравномерные распрекделния), randrange(), `randnt()
Управление датчиком: seed(), getstate()
- Воспроизводимость псевдослучайной последовательности
1 >>> seed(100500) 2 >>> [randrange(10) for i in range(20)] 3 [8, 6, 2, 0, 2, 3, 8, 8, 8, 1, 7, 8, 1, 3, 4, 0, 3, 4, 4, 0] 4 >>> [randrange(10) for i in range(20)] 5 [5, 7, 4, 3, 0, 9, 4, 3, 2, 2, 1, 8, 4, 3, 2, 5, 5, 2, 5, 2] 6 >>> [randrange(10) for i in range(20)] 7 [6, 6, 6, 4, 9, 6, 9, 0, 6, 4, 4, 6, 1, 0, 8, 3, 7, 8, 6, 7] 8 >>> seed(100500) 9 >>> [randrange(10) for i in range(20)] 10 [8, 6, 2, 0, 2, 3, 8, 8, 8, 1, 7, 8, 1, 3, 4, 0, 3, 4, 4, 0] 11 >>> [randrange(10) for i in range(20)] 12 [5, 7, 4, 3, 0, 9, 4, 3, 2, 2, 1, 8, 4, 3, 2, 5, 5, 2, 5, 2] 13 >>> [randrange(10) for i in range(20)] 14 [6, 6, 6, 4, 9, 6, 9, 0, 6, 4, 4, 6, 1, 0, 8, 3, 7, 8, 6, 7] 15 >>> [randrange(10) for i in range(20)] 16 [0, 2, 3, 6, 2, 1, 6, 3, 5, 8, 5, 6, 5, 7, 3, 1, 0, 6, 3, 5] 17
- Воспроизводимость псевдослучайной последовательности
choice(), shuffle()
sample() (без повторений)
choices() — с заданными весами
1 >>> choices(range(10,100), [1]*90, k=20) # равные веса 2 [94, 50, 52, 78, 38, 95, 22, 18, 24, 32, 25, 92, 48, 42, 62, 49, 97, 95, 55, 59] 3 >>> choices(range(10,100), range(90,0,-1), k=20) # малые числа тяжелее 4 [20, 18, 45, 85, 45, 41, 30, 72, 58, 18, 20, 43, 20, 10, 44, 21, 22, 64, 25, 39] 5 >>> choices(range(10,100), cum_weights=range(90), k=20) # равные кумулятивные веса 6 [28, 94, 61, 21, 48, 43, 13, 53, 49, 31, 94, 99, 84, 39, 13, 52, 43, 11, 98, 79] 7 >>> choices(range(10), cum_weights=[c for c in range(15) if c%3], k=20) 8 [6, 2, 4, 2, 8, 6, 8, 3, 6, 8, 9, 8, 8, 1, 6, 2, 2, 0, 4, 9] 9 >>> from collections import Counter 10 >>> S = choices(range(10), cum_weights=[c for c in range(15) if c%3], k=1000) 11 >>> Counter(S) # 2,4,6,8 — в два раза чаще остальных 12 Counter({6: 165, 4: 152, 2: 145, 8: 127, 9: 83, 0: 70, 7: 69, 1: 68, 3: 66, 5: 55}) 13
Д/З
Прочитать про словари в учебнике и в документации