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

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
Counter
defaultdict
- Мелкий изврат: def tree(): return defaultdict(tree) (тут)
…

Д/З

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

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

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

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

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
```
- генратор тестовых даных
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
```

LecturesCMC/PythonIntro2023/06_SetsDicts (последним исправлял пользователь FrBrGeorge 2024-10-13 22:24:19)