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

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

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