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

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

Множества и 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. Прочитать про словари в учебнике и в документации

TODO

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

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

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