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

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

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

id() — уникальность объекта, ничего не знает про равенство
сравнение двух объектов может быть тяжёлой операцией
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

Словари

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

(до 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}

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

   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

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

Модуль collections

deque
namedtuple
Counter
defaultdict
- Мелкий изврат: def tree(): return defaultdict(tree) (тут)
…

Д/З

Прочитать и прощёлкать
- про множества в учебнике и в документации
- про словари в учебнике и в документации
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
```
- генратор тестовых даных (вам понадобится google-10000-english.txt)
EJudge: ThreeSquares 'Три квадрата'
Ввести произвольную последовательность (не обязательно кортеж) натуральных чисел, не превышающих 200000. Вывести, сколько среди них различных чисел, являющихся суммой трёх квадратов натуральных чисел.
- Пояснение. Входная последовательность должна обрабатываться так: seq = set(eval(input()))
Input:
```
3, 4, 2, 9, 1, 5, 6, 7, 8, 3, 6
```
Output:
```
3
```
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
```
- генратор тестовых даных (вам понадобится google-10000-english.txt)

EJudge: AnnaTolstoy 'Анна Толстой'

В первой строке программа вводит натуральное число N⩾3. Во всех последующих — роман Л. Н. Толстого «Анна Каренина» (именно из этого файла). Написать программу, которая составляет случайный текст длинной в N слов таким образом, чтобы любые три стоящие рядом «слова» встречались в этом же сочетании в романе.

«Словами» считаются:
- любые последовательности непробельных символов (например, тире между словами)
- Красная строка (перевод строки и четыре пробела) в начале абзаца (например, в прямой речи)
Все остальные непробельные символа считаются «буквами»: например слово со знаком препинания или кавычкой не равно просто слову.
Например, вот тут 9 слов (два тире, одна красная строка и шесть слов со знаками и без):
- - Мы думали, с вами, - сказала она.
Обратите внимание на то, что текст ответа в примере не является эталонным (т. е. сравнивать с ним никто не будет), в тестах проверяется только соответствие вашего ответа условиям задачи.

Input:

200
Лев Николаевич Толстой. Анна Каренина
                                                 Мне отмщение, и аз воздам
     Все счастливые семьи похожи друг на друга,  каждая  несчастливая  семья
несчастлива по-своему.
…

Output:

    Поняв чувства барина, Корней попросил приказчика прийти в другой она держала их наготове и, глядя в его комнате.
    - Костя будет очень рада. А то не могла иметь; и я его браню? Мне до него дело. Главные качества Степана Аркадьича, как круглый сыр, поднялся стальной бугор из-под тонкого сукна сюртука.
    - Еще слово: во всяком человеке искал отношения к земле мальчик в русском платье обгонял ее. Она катилась не совсем хорошо, - сказала Лидия Ивановна, как бы кристаллизация общества, определяющая каждому его члену определенное и предназначенное им место.
    Место это он знает народ, и часто беседовал с мужиками, что он высказал все; то, что называла той любовью. И ясность, с которою ты не уважаешь...
    - Расскажите нам что-нибудь забавное, но не смел думать об этом так легко. И она шире открыла глаза, желая этим смягчить для нее все ее слова,
    - Ах!- вскрикнул он, узнав брата, и Левин мог бы отказаться. А тебе доставляет удовольствие смотреть на небо.
    Уже пред самым отъездом приехал опоздавший Степан Аркадьич, заехав к ней, - сказал гувернер. - Я заехал еще привезть тебе денег, так как не выручить! Этот нажмет, да свое выберет. Он хрестьянина не пожалеет. А дядя Фоканыч (так

LecturesCMC/PythonIntro2021/06_SetsDicts (последним исправлял пользователь FrBrGeorge 2022-10-11 12:45:08)