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

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

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

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

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

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

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

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

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

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

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

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

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

• - Невосстановимость — не требуется

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

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

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

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

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

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

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

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

Множества

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

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

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

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

       1 from math import log2
       2 sz, s = {}, set()
       3 for i in range(1, 204800):
       4     s.add(str(i) * 5)
       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

• 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: EvalFormulae 'Вычисление формулы'

   Написать функцию evalform(formula, *args), принимающую переменное количество параметров. Обязателен только первый параметр — это строка с некоторой формулой. В формуле могут встречаться переменные. Имена переменных состоят из одной или нескольких букв. Остальные параметры — это значения этих переменных, если их перечислить в алфавитном порядке. Функция должна возвращать результат вычисления формулы. Проверять правильность или обрабатывать исключения не надо.

   • UPD: в данной задаче любые буквы означают переменные, то есть не используются операции Python, задаваемые буквами (типа «in», «and» и т. п.)

   print(evalform("b*2 + a*3 + b//3 + c", 11, 3, 2))

   Input:

   print(evalform("b*2 + a*3 + b//3 + c", 11, 3, 2))

   Output:

   42

2. 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

3. EJudge: SetJuggler 'Манипуляция множествами'

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

   • print множества — вывести в отсортированном виде через пробел все элементы множеств

   • search множества where строка to имя — найти все элементы множеств, содержащие строку, и сформировать из них множество имя

   • search множества for множества_поиска to имя — найти все элементы множеств, которые содержатся также и в каком-нибудь из множеств_поиска, и сформировать из них множество имя

   Input:

   Ходя на практические кризисы потенциалов, едящее вдали от тени абстракций 
   божество организации знакомилось в религии армии, содействуя сему 
   и ночному оппортунизму. Дифференцирует бесполезного Мазовецкого 
   с периодом, усмехаясь над эволюционными определениями, Рейган утренних 
   абсолютных воскресений. Организация означала характеры ребенком, 
   ходя за исполнителей с лекцией, но не желала между первоначальным 
   воинствующим поражением и элементарным объектом образовываться качествами. 
   Эта и надоедливая шапка извращается исполнителем, но не хочет над 
   комплексным воскресеньем без сред преобразиться четвергом без практики. 
   Способствуя мышам с полем, материализм является государственным 
   четвергом. Собака формулирует натуральную и недоношенную ложку индивиду 
   без структур; она осмыслила университет критическими и утренними 
   качествами, гамадрилами догматизмов нося студенческого Мазовецкого. 
   Абстрагировали над целями с именами индивиды, сказанные о колхознице 
   и являвшиеся этим и идеалистическим университетом. Пьяное условие 
   с теорией смеет между подозрительными материалами среды материальной 
   разработкой без оппортунизма осуществлять единства искусственных 
   стипендий. Формулировал пьяный объект потенциалу познанный поэтический 
   Эзоп с елью и формулировал реформизмы закону, позвонив архаичному 
   процессу. Воскресенья мыслят философией, шумя в студенческой и специфической 
   
   search ALL where фи to ФИ
   print ФИ
   search ALL where ил to ИЛ
   print ИЛ
   search ФИ,ИЛ where о to ФИЛО
   print ФИЛО
   search ФИЛО for ИЛ to НЕФИЛ
   print НЕФИЛ

   Output:

   специфической философией,
   гамадрилами знакомилось осмыслила философией,
   знакомилось осмыслила специфической философией,
   знакомилось осмыслила философией,

4. EJudge: DungeonMap 'Карта подземелья'

   Вводится карта проходимых в обе стороны тоннелей подземлья в виде строк, содержащих разделённые пробелом названия двух пещер, которые соединяет соответствующий тоннель. Две последние строки не содержат пробелов — это название входа в подземелье и название выхода. Вывести "YES", если из входа можно попасть в выход, и "NO" в противном случае. Пары могут повторяться или содержать одинаковые слова.

   Input:

   markers jumping
   jumping guinea
   skiing pre
   markers gauge
   skiing mpeg
   solar jackson
   skiing solar
   guinea gauge
   mpeg honor
   pre honor
   guinea gauge
   pre mpeg
   markers guinea
   markers gauge
   honor mpeg
   markers jumping
   skiing
   jumping

   Output:

   NO

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