49
Комментарий:
|
9728
|
Удаления помечены так. | Добавления помечены так. |
Строка 2: | Строка 2: |
Внимание: подробный рассказ про хеш-функции и хеш-таблицы см. в записях предыдущих лет. == Множества и hash() == * `id()` — уникальность объекта, ничего не знает про ''равенство'' * сравнение двух объектов может быть тяжёлой операцией * `hash()` — числовой хеш от ''константного'' объекта * например, `frozenset()` :) * создаётся вместе с объектом * для изменяемого объекта (например, списка) смысла не имеет * если хеши не равны, объекты тоже не равны Множества в Python реализованы как хеш-''таблицы'': * размер таблицы приблизительно пропорционален количеству элементов (изменение размера как в списках) * повторное хеширование при коллизии * ''константный'' поиск в среднем (+линейное масштабирование) Элементы множества ''неупорядочены'' (в действительности, ''почти'' упорядочены по хешам, с учётом перехеширования и масштабирования): {{{#!highlight pycon >>> s = {str(i) for i in range(10,30)} >>> s {'18', '19', '25', '29', '23', '27', '16', '11', '17', '20', '15', '28', '14', '24', '26', '13', '22', '10', '12', '21'} >>> [hash(c)%128 for c in s] [8, 10, 11, 10, 25, 32, 39, 40, 39, 64, 72, 76, 95, 100, 106, 110, 115, 122, 125, 127] }}} == Словари == Задача: хранить ''произвольные'' объекты, каждый из которых ''взаимно однозначно'' соответствует хорошо хешируемому ключу. * просто `list()` (ключ — 0, 1, …) * (до Python3.6) — ''множество'' ключей + ссылка на хранимый объект * ([[https://docs.python.org/3/whatsnew/3.6.html#whatsnew36-compactdict|современный Python]]) хеш-таблица + журнал * Сохраняет порядок добавления элементов * Более компактное и быстрое преставление * Более чувствительно к удалениям (кому нужно ''удалять из словаря''?) * `dict` — как массив с константными элементами вместо индекса * Задание и обращение к элементу * Циклческий констуктор * Работа со словарём * `keys()`, `values()`, `items()` * итератор из словаря Словари внутри 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|Ещё вкусности]] == Модуль collections == * [[py3doc:collections.html#collections.deque|deque]] * [[py3doc:collections.html#collections.namedtuple|namedtuple]] * [[py3doc:collections.html#collections.Counter|Counter]] * [[py3doc:collections.html#collections.defaultdict|defaultdict]] * Мелкий изврат: `def tree(): return defaultdict(tree)` ([[https://gist.github.com/hrldcpr/2012250|тут]]) * … == Использование random == Аппаратная случайность: [[py3doc:os.getrandom]] Работа с датчиком случайный чисел: [[py3doc:random]] * `random()` (и неравномерные распрекделния), `randrange()`, `randnt() * Управление датчиком: `seed()`, `getstate()` * Воспроизводимость псевдослучайной последовательности {{{#!highlight pycon >>> seed(100500) >>> [randrange(10) for i in range(20)] [8, 6, 2, 0, 2, 3, 8, 8, 8, 1, 7, 8, 1, 3, 4, 0, 3, 4, 4, 0] >>> [randrange(10) for i in range(20)] [5, 7, 4, 3, 0, 9, 4, 3, 2, 2, 1, 8, 4, 3, 2, 5, 5, 2, 5, 2] >>> [randrange(10) for i in range(20)] [6, 6, 6, 4, 9, 6, 9, 0, 6, 4, 4, 6, 1, 0, 8, 3, 7, 8, 6, 7] >>> seed(100500) >>> [randrange(10) for i in range(20)] [8, 6, 2, 0, 2, 3, 8, 8, 8, 1, 7, 8, 1, 3, 4, 0, 3, 4, 4, 0] >>> [randrange(10) for i in range(20)] [5, 7, 4, 3, 0, 9, 4, 3, 2, 2, 1, 8, 4, 3, 2, 5, 5, 2, 5, 2] >>> [randrange(10) for i in range(20)] [6, 6, 6, 4, 9, 6, 9, 0, 6, 4, 4, 6, 1, 0, 8, 3, 7, 8, 6, 7] >>> [randrange(10) for i in range(20)] [0, 2, 3, 6, 2, 1, 6, 3, 5, 8, 5, 6, 5, 7, 3, 1, 0, 6, 3, 5] }}} * `choice()`, `shuffle()` * `sample()` (без повторений) {{{#!highlight pycon >>> sample(range(10,100), 10) [95, 28, 54, 93, 40, 97, 63, 26, 69, 91] >>> sample(range(10,100), 10) [57, 81, 73, 54, 95, 93, 42, 37, 80, 21] }}} * `choices()` — с заданными весами {{{#!highlight pycon >>> choices(range(10,100), [1]*90, k=20) # равные веса [94, 50, 52, 78, 38, 95, 22, 18, 24, 32, 25, 92, 48, 42, 62, 49, 97, 95, 55, 59] >>> choices(range(10,100), range(90,0,-1), k=20) # малые числа тяжелее [20, 18, 45, 85, 45, 41, 30, 72, 58, 18, 20, 43, 20, 10, 44, 21, 22, 64, 25, 39] >>> choices(range(10,100), cum_weights=range(90), k=20) # равные кумулятивные веса [28, 94, 61, 21, 48, 43, 13, 53, 49, 31, 94, 99, 84, 39, 13, 52, 43, 11, 98, 79] >>> choices(range(10), cum_weights=[c for c in range(15) if c%3], k=20) [6, 2, 4, 2, 8, 6, 8, 3, 6, 8, 9, 8, 8, 1, 6, 2, 2, 0, 4, 9] >>> from collections import Counter >>> S = choices(range(10), cum_weights=[c for c in range(15) if c%3], k=1000) >>> Counter(S) # 2,4,6,8 — в два раза чаще остальных Counter({6: 165, 4: 152, 2: 145, 8: 127, 9: 83, 0: 70, 7: 69, 1: 68, 3: 66, 5: 55}) }}} == Д/З == 1.#0 Прочитать про словари [[py3tut:datastructures.html#dictionaries|в учебнике]] и [[py3doc:stdtypes.html#typesmapping|в документации]] '''TODO''' 1. Покемоны. Участники некоторой карточной игры владеют несколькими колодами, из которых они составляют свой уникальный игровой набор. Каждая колода имеет номер; колоды с одинаковыми номерами содержат совпадающие наборы карт. Ввести строки вида "`имя игрока / номер колоды`" или "`номер колоды / название карты`" (последняя строка пустая). Вывести в алфавитном порядке имена игроков, которые могут составить игровой набор из наибольшего числа ''различных'' карт. 1. Словарь Толстого. Ввести число N, а за ним построчно некоторый текст. Выделить из текста слова, и вывести Top-N по частоте встречаемости слов, длиной не меньше N. Например, в Top-2 список входят все слова, которые встречаются чаще всех, и все слова, которые встречаются реже этих, но чаще всех остальных (обратите внимание на то, что `Counter.most_common()` ведёт себя иначе). Не слишком интересная задачка, но весьма поучительная, если её натравить на «Анну Каренину», например. Толстой зануда. 1. Написать ''функцию'' `randsquare(A, B)`, принимающую на вход две пары вещественных чисел — координаты диагонали квадрата на плоскости. Функция должна возвращать случайную точку, принадлежащую внутренней области этого квадрата (не границе). |
Словари и их применение
Внимание: подробный рассказ про хеш-функции и хеш-таблицы см. в записях предыдущих лет.
Множества и 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
Д/З
Прочитать про словари в учебнике и в документации
TODO
Покемоны. Участники некоторой карточной игры владеют несколькими колодами, из которых они составляют свой уникальный игровой набор. Каждая колода имеет номер; колоды с одинаковыми номерами содержат совпадающие наборы карт. Ввести строки вида "имя игрока / номер колоды" или "номер колоды / название карты" (последняя строка пустая). Вывести в алфавитном порядке имена игроков, которые могут составить игровой набор из наибольшего числа различных карт.
Словарь Толстого. Ввести число N, а за ним построчно некоторый текст. Выделить из текста слова, и вывести Top-N по частоте встречаемости слов, длиной не меньше N. Например, в Top-2 список входят все слова, которые встречаются чаще всех, и все слова, которые встречаются реже этих, но чаще всех остальных (обратите внимание на то, что Counter.most_common() ведёт себя иначе). Не слишком интересная задачка, но весьма поучительная, если её натравить на «Анну Каренину», например. Толстой зануда.
Написать функцию randsquare(A, B), принимающую на вход две пары вещественных чисел — координаты диагонали квадрата на плоскости. Функция должна возвращать случайную точку, принадлежащую внутренней области этого квадрата (не границе).