Словари и их применение

Внимание: подробный рассказ про хеш-функции и хеш-таблицы см. в записях предыдущих лет.

Множества и hash()

• id() — уникальность объекта, ничего не знает про равенство

• сравнение двух объектов может быть тяжёлой операцией

• hash() — числовой хеш от константного объекта

  • например, frozenset()

  • создаётся вместе с объектом
    • для изменяемого объекта (например, списка) смысла не имеет
  • если хеши не равны, объекты тоже не равны

Множества в Python реализованы как хеш-таблицы:

• размер таблицы приблизительно пропорционален количеству элементов (изменение размера как в списках)
• повторное хеширование при коллизии

• константный поиск в среднем (+линейное масштабирование)

Элементы множества неупорядочены (в действительности, почти упорядочены по хешам, с учётом перехеширования и масштабирования):

   1 >>> s = {str(i) for i in range(10,30)}
   2 >>> s
   3 {'18', '19', '25', '29', '23', '27', '16', '11', '17', '20', '15', '28', '14', '24', '26', '13', '22', '10', '12', '21'}
   4 >>> [hash(c)%128 for c in s]
   5 [8, 10, 11, 10, 25, 32, 39, 40, 39, 64, 72, 76, 95, 100, 106, 110, 115, 122, 125, 127]
   6 

Словари

Задача: хранить произвольные объекты, каждый из которых взаимно однозначно соответствует хорошо хешируемому ключу.

• просто 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}
  

• Именные параметры функции

     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
  

• Ещё вкусности

Модуль collections

• deque

• namedtuple

• Counter

• defaultdict

  • Мелкий изврат: 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() (без повторений)

     1 >>> sample(range(10,100), 10)
     2 [95, 28, 54, 93, 40, 97, 63, 26, 69, 91]
     3 >>> sample(range(10,100), 10)
     4 [57, 81, 73, 54, 95, 93, 42, 37, 80, 21]
     5 
  

• 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 
  

Д/З

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

1. EJudge: RandSquare 'Точка в квадрате'

   Написать функцию randsquare(A, B), принимающую на вход две пары вещественных чисел — координаты диагонали квадрата на плоскости. Функция должна возвращать случайную точку, принадлежащую этому квадрату (ожидаются точки из любого места квадрата, например, с его границы, хотя вероятность этого события будем считать нулевой).

   Input:

   # Это ошибочный тест!
   for i in range(100000):
       x, y = randsquare((0,-10.01), (0,10.01))
       if x**2+y**2 > 100:
           print(f"Error: {x}:{y}")

   Output:

   Error: -0.002220480791093505:-10.002541596486285
   Error: 0.0008220827409817354:-10.005657011321619
   Error: -0.0019093494480841855:10.007641260813324

   Написать функцию randsquare(A, B), принимающую на вход две пары вещественных чисел — координаты диагонали квадрата на плоскости. Функция должна возвращать случайную точку, принадлежащую внутренней области этого квадрата (не границе).

TODO

1. Покемоны. Участники некоторой карточной игры владеют несколькими колодами, из которых они составляют свой уникальный игровой набор. Каждая колода имеет номер; колоды с одинаковыми номерами содержат совпадающие наборы карт. Ввести строки вида "имя игрока / номер колоды" или "номер колоды / название карты" (последняя строка пустая). Вывести в алфавитном порядке имена игроков, которые могут составить игровой набор из наибольшего числа различных карт.

2. Словарь Толстого. Ввести число N, а за ним построчно некоторый текст. Последняя строка — пустая. Выделить из текста слова, и вывести Top-N по частоте встречаемости слов, длиной не меньше N. Например, в Top-2 список входят все слова, которые встречаются чаще всех, и все слова, которые встречаются реже этих, но чаще всех остальных (обратите внимание на то, что Counter.most_common() ведёт себя иначе). Не слишком интересная задачка, но весьма поучительная, если её натравить на «Анну Каренину», например. Толстой зануда.