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

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

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

Словари

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

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

Словари внутри Python

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

TODO Пример?

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

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

Модуль collections

Д/З

  1. Прочитать и прощёлкать
  2. (это задача не на словари ☺)

    • EJudge: RandSquare 'Точка в квадрате'

      Написать функцию randsquare(A, B), принимающую на вход две пары вещественных чисел — координаты диагонали квадрата на плоскости. Функция должна возвращать случайную точку, принадлежащую этому квадрату (ожидаются точки из любого места квадрата, например, с его границы, хотя вероятность этого события будем считать нулевой). «Случайность» в тестах определяется как достаточно равномерное распределение точек по всей поверхности квадрата.

      Input: 

      # Это ошибочный тест!
for i in range(100000):
    x, y = randsquare((0,-10.01), (0,10.01))
    if x**2+y**2 > 100:
        print(f"Error: {x}:{y}")
      Output: 

      Error: -0.002220480791093505:-10.002541596486285
Error: 0.0008220827409817354:-10.005657011321619
Error: -0.0019093494480841855:10.007641260813324
      Вот код, который рисует красивую картинку на эту тему ☺: 
         1 def showgr(Dots, Corners, Name="Dots"):
   2     import numpy as np
   3     import matplotlib.pyplot as plt
   4 
   5     X, Y = zip(*Dots)
   6     fig, ax = plt.subplots(num=Name)
   7     ax.set_aspect(1)
   8     ax.scatter(X, Y)
   9     ax.fill(*Corners, fill=False)
  10     plt.show()
  11 
  12 def show(A, B, num=1000):
  13     dots = [randsquare(A, B) for i in range(num)]
  14     R = [ (A[0], (B[0]+A[0])/2-(B[1]-A[1])/2, B[0], (B[0]+A[0])/2+(B[1]-A[1])/2),
  15           (A[1], (B[1]+A[1])/2+(B[0]-A[0])/2, B[1], (B[1]+A[1])/2-(B[0]-A[0])/2)]
  16     showgr(dots, R)
  17 
  18 show((6,7), (2,12), 5000)

  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: 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

  5. EJudge: LevKarenina 'Лев Каренина'

    В первой строке ввода находится четыре символа: знак препинания в конце предыдущего предложения p, первая буква слова в начале предложения b, первая буква последнего слова в предложении g и знак препинания в конце предложения e. Все остальные строки, кроме последней, непустые, и содержат строки некоторого текста. Текст состоит из слов (последовательностей любых непробельных символов) и разделителей (последовательностей пробельных символов). Считается, что «предложение» — это то, что заканчивается на p или e. Вывести в предлагаемой форме

    • самое популярное слово

      • начинающееся на b,

      • & в начале предложений,

      • & перед которыми стояло p

    • и самое популярное слово

      • начинающееся на g,

      • & в конце предложений,

      • & заканчивающихся на e

    • а также количество вхождений таких критериев.

    Если какой-то из этих критериев нельзя удовлетворить, вывести «...» и 0. Если критерию удовлетворяет несколько слов, вывести то, что встретилось в заданном контексте раньше.

    Input: 

    .Sf!
 Syringes expanses syringes syringes fordo! Fenceless fills
syringes fills fills syringes. Salves sis fordo sis salves fordo
fenceless salves expanses? Fills syringes. Syringes syringes
salves sis salves salves fills! Expanses fordo fenceless.
Salves expanses expanses salves fills! Sis sis fills fills!
    Syringes sis syringes syringes expanses. Fills fenceless
fordo syringes salves! Fenceless fordo fenceless syringes sis 
expanses salves fordo. Syringes sis salves syringes syringes
salves expanses! Expanses fordo expanses salves expanses fills
syringes fills syringes salves fenceless. Fenceless fills
salves? Fenceless sis expanses syringes expanses fenceless
fenceless sis fenceless syringes sis expanses! Fenceless
syringes syringes sis. Sis fate!
    Output: 

    Salves 2 - fills! 3

LecturesCMC/PythonIntro2022/06_SetsDicts (последним исправлял пользователь FrBrGeorge 2022-10-17 16:11:52)