Словари и их применение

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

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

Модуль collections

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

Аппаратная случайность: os.getrandom

Работа с датчиком случайный чисел: random

Д/З

  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: AnnaKar 'Словарь Толстого'

    Ввести два натуральных числа через запятую: N и W, а за ними построчно некоторый текст. Последняя строка — пустая. Выделить из текста слова (последовательности символов, для которых isalpha() истинно), преобразовать их в нижний регистр, и вывести Top-N по частоте встречаемости слов длиной не меньше W. Например, в Top-2 список входят все слова, которые встречаются чаще всех, и все слова, которые встречаются реже этих, но чаще всех остальных (обратите внимание на то, что Counter.most_common() ведёт себя иначе). Ключи сортировки вывода: сначала длина, потом слово. Если различных количеств встречаемых слов не больше N (например, все слова в тексте встречаются по разу), в Top-N входят все слова.

    Input:

    3,4
    cerebral atrophy, n:
            The phenomena which occurs as brain cells become weak and sick, and
    impair the brain's performance.  An abundance of these "bad" cells can cause
    symptoms related to senility, apathy, depression, and overall poor academic
    performance.  A certain small number of brain cells will deteriorate due to
    everday activity, but large amounts are weakened by intense mental effort
    and the assimilation of difficult concepts.  Many college students become
    victims of this dread disorder due to poor habits such as overstudying.
    -
    cerebral darwinism, n:
            The theory that the effects of cerebral atrophy can be reversed
    through the purging action of heavy alcohol consumption.  Large amounts of
    alcohol cause many brain cells to perish due to oxygen deprivation.  Through
    the process of natural selection, the weak and sick brain cells will die
    first, leaving only the healthy cells.  This wonderful process leaves the
    imbiber with a healthier, more vibrant brain, and increases mental capacity.
    Thus, the devastating effects of cerebral atrophy are reversed, and academic
    performance actually increases beyond previous levels.
    Output:

    3: atrophy
    3: performance
    4: cerebral
    6: brain
    6: cells
    • Не слишком интересная задачка, но весьма поучительная, если её натравить на «Анну Каренину», например, с параметрами 11,5. Толстой зануда.

  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

LecturesCMC/PythonIntro2020/06_DictCollection (last edited 2020-10-17 13:03:51 by FrBrGeorge)