Множества и словари

TODO насыпать очевидных примеров.

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

Коротко про функцию хеширования:

• Она должна быть однозначной и переводить область определения в актуально меньшую область значений
• Все остальные свойства — взаимооднозначность, равномерность, невосстановимость и т. п. — необязательны, зависят от применения, и не всегда достижимы.

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

Почему не id()?

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

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

⇒ Специальная функция hash() — числовой хеш от константного объекта

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

  • соответствует методу .__hash__()

• если хеши не равны, объекты тоже не равны

  • обратное, в целом, неверно

Множества

• Задаются перечислением или сборкой в { }

• Поддерживают теоретико-множественные операции "| & ^ -"

Множества в 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 

Множества — модифицируемые объекты, но есть и константные: frozenset

Словари

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

• (до Python3.6 — множество ключей + ссылка на хранимый объект)

• (современный Python) хеш-список (без дыр) + журнал индексов

  • основная идея

  • Операция добавления легче операции удаления (кому нужно удалять из словаря?)

  • Сохраняет порядок добавления элементов

Использование

• dict — как массив с константными элементами вместо индекса

• Задание и обращение к элементу
• Циклический конструктор
• Работа со словарём

• keys(), values(), items()

  • цикл по словарю

• [] vs .get() vs .setdefault()

• .update() и прочие методы

• Относительно новое — | и |=

Словари внутри 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}
  

Передача пространства имён как параметра

• eval() — интерпретация и вычисление выражения

• exec() — интерпретация и выполнение куска кода

• И туда, и туда можно передать словарь для того, что это выражение/код увидит в качестве globals() и locals()

     1 >>> eval("A+B", None, {"B":234})
     2 357
     3 >>> eval("A+B", {"A": 12, "B": 78, "C": -1})
     4 90
     5 >>> A=100500
     6 >>> eval("A+B", {"A": 12, "B": 78, "C": -1})
     7 90
     8 >>> eval("A+B", None, {"A": 12, "B": 78, "C": -1})
     9 90
    10 >>> eval("A+B", None, {"B": 78, "C": -1})
    11 100578
    12 >>> eval("A+B-C+D-E", dict(zip("ABCDE", range(10, 16))))
    13 8
    14 
  

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

Позиционные параметры — кортеж, именные — словарь.

•    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
    16 
  

• Ещё немного занудства про параметры функций: значения по умолчанию ≠ именные параметры

Модуль collections

• deque

• namedtuple

• ChainMap

• Counter

• defaultdict

  • Мелкий изврат: def tree(): return defaultdict(tree) (тут)

• …

Д/З

0. Прочитать и прощёлкать

   • про множества в учебнике и в документации

   • про словари в учебнике и в документации

   • документацию к collections

1. EJudge: PairNumber 'Количество пар'

   Вводится текст, состоящий из «слов» (последовлательностей непробельных символов), разделённых последовательностями пробельных символов. Последня строка пустая. Посчитать и вывести, сколько различных последовательных пар слов (без учёта порядка) встречается в тексте.

   Input:

   qwe rty asd
   rty qwe asd
   wat qwe wat

   Output:

   5

2. EJudge: ThreeSquares 'Три квадрата'

   Ввести произвольную последовательность (не обязательно кортеж) натуральных чисел, не превышающих 200000. Вывести, сколько среди них различных чисел, являющихся суммой трёх квадратов натуральных чисел.

   • Пояснение. Входная последовательность должна обрабатываться так: seq = set(eval(input()))

   Input:

   3, 4, 2, 9, 1, 5, 6, 7, 8, 3, 6

   Output:

   3

3. EJudge: FarGalaxy 'В далёкой галактике'

   Ввести построчно четвёрки вида «число число число слово», где первые три числа — это координаты галактики по имени «слово» (некоторые галактики могут называться одинаково, но координаты у всех разные). Последняя строка ввода не содержит пробелов и не учитывается. Вывести в алфавитном порядке имена любых двух наиболее удалённых друг от друга галактик. Считается, что одинаковых расстояний в списке нет.

   Input:

   35.764 -797.636 -770.320 almost
   88.213 -61.688 778.457 gene
   -322.270 -248.555 -812.730 trend
   721.262 630.355 968.287 dow
   -895.519 -970.173 97.282 non
   -561.036 -350.840 -723.149 disco
   -151.546 -900.962 -658.862 bidder
   -716.197 478.576 -695.843 hawaii
   -744.664 -173.034 -11.211 sad
   -999.968 990.467 650.551 erik
   .

   Output:

   almost erik

4. EJudge: PokeMon 'Покемоны'

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

   Input:

   0 / Misdreavus
   Svjatoslav Devjatkov / 3
   2 / Yamask
   Vsevid Mladenov / 1
   1 / Keldeo
   0 / Keldeo
   1 / Misdreavus
   2 / Scatterbug
   0 / Crawdaunt
   2 / Keldeo
   1 / Vanillite
   Svjatoslav Devjatkov / 0
   2 / Gardevoir
   Neljub Mstislavin / 2
   2 / Crawdaunt
   0 / Yamask
   3 / Reshiram

   Output:

   Neljub Mstislavin
   Svjatoslav Devjatkov