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

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

Множества и 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 (последним исправлял пользователь FrBrGeorge 2023-10-19 14:36:21)