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

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

Множества и 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. Прочитать про словари в учебнике и в документации

TODO

  1. 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)

  2. Покемоны. Участники некоторой карточной игры владеют несколькими колодами, из которых они составляют свой уникальный игровой набор. Каждая колода имеет номер; колоды с одинаковыми номерами содержат совпадающие наборы карт. Ввести строки вида "имя игрока / номер колоды" или "номер колоды / название карты" (последняя строка пустая). Вывести в алфавитном порядке имена игроков, которые могут составить игровой набор из наибольшего числа различных карт.

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