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

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

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

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

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

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

Хеш объекта в python используется в первую очередь для предварительного сравнения

• + Достаточно высокая скорость вычисления (иначе можно сами объекты сравнивать)

• + Фиксированный размер

• ± Актуальное неравенство для «почти похожих»: например, для чисел из диапазона, совпадающих с точностью до символа строк и т. п.

• ? «Актуальная взаимнооднозначность» — минимизация коллизий — желательно, но необязательно

• - Разброс для почти похожих объектов — не требуется (hash(123456))

• - Невосстановимость — не требуется (hex(hash(1.5)), hex(hash(14.125))

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

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

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

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

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

• Пространство: целое 64 бита

Почему id() — плохая хеш-функция?

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

• id() переиспользуется

Множества

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

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

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

• вычисляется хеш объекта
• вычисляется индекс объекта — остаток от деления хеша на размер таблицы (обычно — 2ⁿ)
• повторное хеширование при коллизии
• размер таблицы приблизительно пропорционален количеству элементов
  • + геометрическое масштабирование при заполнении на определённый объём (примерно на ⅔)

       1 from math import log2
       2 sz, s = {}, set()
       3 for i in range(1, 409600):
       4     s.add(str(i))
       5     sz[s.__sizeof__()] = len(s)
       6 for key, val in list(sz.items())[2:-1]:
       7     print(f"{key:10.1f}: {val:7} ({round(log2(key))}:{key/(val *16):.4f})")
    

    • Чуть более сложный множитель

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

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

   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 3.15+ — frozendict

• Показательная история с pep-0416 → pep-0814

Словари внутри 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: PopularWord 'Самое популярное слово'

   Ввести построчно текст, состоящий из пробелов, переводов строки и латинских букв, и заканчивающийся пустой строкой. Вывести слово, которое чаще других встречается в тексте, если оно такое одно, и ---, если таких слов несколько.

   Input:

   Sed tempus ipsum quis eros tempus lacinia Cras finibus lorem ut lacinia egestas nunc nibh iaculis est convallis tincidunt
   mi mi sed nisl Sed porttitor aliquam elit ullamcorper tincidunt arcu euismod quis Mauris congue elit suscipit leo varius
   facilisis Cras et arcu sodales laoreet est vitae pharetra orci Integer eget nulla dictum aliquet justo semper molestie neque
   Maecenas bibendum lacus tincidunt auctor varius purus felis ullamcorper dui et laoreet ligula ex et risus Donec eget
   fringilla nibh Cras congue tincidunt accumsan Maecenas euismod eleifend elit ut rhoncus tortor sodales a Cras egestas
   finibus lorem non tempor tincidunt aera

   Output:

   tincidunt

   • генратор тестовых даных

2. EJudge: MumboJumbo 'Мумбо-Юмбо'

   Ввод представляет собой строки из букв латинского алфавита (последняя строка — пустая). Это письмена на языках двух племён: Mumbo и Jumbo. Слова из двух языков идут попеременно: на строках с чётным номером — из одного языка, на строках с нечётным — из другого (какого — неизвестно). Языки Mumbo и Jumbo имеют одинаковые гласные и разные согласные, причём согласных в языке Mumbo больше, чем в Jumbo. Все слова начинаются на гласную. Определить и вывести, какому языку — Mumbo или Jumbo — принадлежит первое слово, если известно, что в данном корпусе текстов:

   1. Использованы все начальные гласные (буква, на которую не начинается ни одно слово — согласная)
   2. Использованы все согласные
   Input:

   obmdobo
   oututo
   odbann
   ufututu
   omdan
   uputupf
   adabo
   utupopot
   obomna
   utpouo
   amdm

   Output:

   Mumbo

3. EJudge: PublicFriend 'Знаком со всеми'

   Вводятся в столбик пары неотрицательных целых чисел через запятую. Каждая пара M, N обозначает взаимное знакомство людей под номерами M и N. Ввод заканчивается парой 0, 0 (не учитывается, и вообще человек N считается незнакомым с человеком N ). Вывести через пробел в порядке возрастания номера тех, кто знаком со всеми остальными, или пустую строку, если таких нет.

   Input:

   7, 9
   1, 7
   9, 2
   9, 2
   9, 7
   2, 9
   9, 2
   2, 9
   7, 1
   9, 2
   9, 2
   2, 1
   7, 2
   7, 9
   7, 1
   7, 1
   0, 0

   Output:

   2 7

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

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

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

   Input:

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

   Output:

   3