Различия между версиями 15 и 16
Версия 15 от 2020-10-16 02:10:27
Размер: 9527
Редактор: FrBrGeorge
Комментарий:
Версия 16 от 2020-10-17 15:54:29
Размер: 9541
Редактор: FrBrGeorge
Комментарий:
Удаления помечены так. Добавления помечены так.
Строка 160: Строка 160:
'''TODO'''
1. Покемоны. Участники некоторой карточной игры владеют несколькими колодами, из которых они составляют свой уникальный игровой набор. Каждая колода имеет номер; колоды с одинаковыми номерами содержат совпадающие наборы карт. Ввести строки вида "`имя игрока / номер колоды`" или "`номер колоды / название карты`" (последняя строка пустая). Вывести в алфавитном порядке имена игроков, которые могут составить игровой набор из наибольшего числа ''различных'' карт.
 1. <<EJCMC(148, PokeMon, Покемоны)>>
Участники некоторой карточной игры владеют несколькими колодами, из которых они составляют свой уникальный игровой набор. Каждая колода имеет номер; колоды с одинаковыми номерами содержат совпадающие наборы карт. Ввести строки вида "`имя игрока / номер колоды`" или "`номер колоды / название карты`" (последняя строка пустая). Вывести в алфавитном порядке имена игроков, которые могут составить игровой набор из наибольшего числа ''различных'' карт.

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

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

Множества и hash()

  • id() — уникальность объекта, ничего не знает про равенство

  • сравнение двух объектов может быть тяжёлой операцией
  • hash() — числовой хеш от константного объекта

    • например, frozenset() :)

    • создаётся вместе с объектом
      • для изменяемого объекта (например, списка) смысла не имеет
    • если хеши не равны, объекты тоже не равны

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

Словари

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

  • просто list() (ключ — 0, 1, …)

  • (до Python3.6) — множество ключей + ссылка на хранимый объект

  • (современный Python) хеш-таблица + журнал

    • Сохраняет порядок добавления элементов
    • Более компактное и быстрое преставление
    • Более чувствительно к удалениям (кому нужно удалять из словаря?)

  • dict — как массив с константными элементами вместо индекса

  • Задание и обращение к элементу
  • Циклческий констуктор
  • Работа со словарём
  • keys(), values(), items()

    • итератор из словаря

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

  • globals()/locals()

       1 >>> QQ
       2 Traceback (most recent call last):
       3   File "<stdin>", line 1, in <module>
       4 NameError: name 'QQ' is not defined
       5 >>> globals()
       6 {'__name__': '__main__', '__doc__': None, '__package__': None, '__loader__': <_frozen_importlib_external.SourceFileLoader object at 0x7f434c1b4190>, '__spec__': None, '__annotations__': {}, '__builtins__': <module 'builtins' (built-in)>, '__cached__': None, 'rlcompleter': <module 'rlcompleter' from '/usr/lib64/python3.7/rlcompleter.py'>}
       7 >>> globals()["QQ"]=100500
       8 >>> QQ
       9 100500
      10 >>> globals()
      11 {'__name__': '__main__', '__doc__': None, '__package__': None, '__loader__': <_frozen_importlib_external.SourceFileLoader object at 0x7f434c1b4190>, '__spec__': None, '__annotations__': {}, '__builtins__': <module 'builtins' (built-in)>, '__cached__': None, 'rlcompleter': <module 'rlcompleter' from '/usr/lib64/python3.7/rlcompleter.py'>, 'QQ': 100500}
    
  • Именные параметры функции
       1 >>> def fun(*argp, **argn):
       2 ...     print(argp, argn)
       3 ...
       4 >>> fun(1,2,3,a=4,b=5)
       5 (1, 2, 3) {'a': 4, 'b': 5}
       6 
       7 >>> def fun(a=1, b=2):
       8 ...   print(a,b)
       9 ...
      10 >>> d = dict(a="QQ", b="PP")
      11 >>> fun(**d)
      12 QQ PP
      13 >>> d = {"a":"QQ", "b":"QKRQ"}
      14 >>> fun(**d)
      15 QQ QKRQ
    
  • Ещё вкусности

Модуль collections

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

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

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

  • random() (и неравномерные распрекделния), randrange(), `randnt()

  • Управление датчиком: seed(), getstate()

    • Воспроизводимость псевдослучайной последовательности
         1 >>> seed(100500)
         2 >>> [randrange(10) for i in range(20)]
         3 [8, 6, 2, 0, 2, 3, 8, 8, 8, 1, 7, 8, 1, 3, 4, 0, 3, 4, 4, 0]
         4 >>> [randrange(10) for i in range(20)]
         5 [5, 7, 4, 3, 0, 9, 4, 3, 2, 2, 1, 8, 4, 3, 2, 5, 5, 2, 5, 2]
         6 >>> [randrange(10) for i in range(20)]
         7 [6, 6, 6, 4, 9, 6, 9, 0, 6, 4, 4, 6, 1, 0, 8, 3, 7, 8, 6, 7]
         8 >>> seed(100500)
         9 >>> [randrange(10) for i in range(20)]
        10 [8, 6, 2, 0, 2, 3, 8, 8, 8, 1, 7, 8, 1, 3, 4, 0, 3, 4, 4, 0]
        11 >>> [randrange(10) for i in range(20)]
        12 [5, 7, 4, 3, 0, 9, 4, 3, 2, 2, 1, 8, 4, 3, 2, 5, 5, 2, 5, 2]
        13 >>> [randrange(10) for i in range(20)]
        14 [6, 6, 6, 4, 9, 6, 9, 0, 6, 4, 4, 6, 1, 0, 8, 3, 7, 8, 6, 7]
        15 >>> [randrange(10) for i in range(20)]
        16 [0, 2, 3, 6, 2, 1, 6, 3, 5, 8, 5, 6, 5, 7, 3, 1, 0, 6, 3, 5]
        17 
      
  • choice(), shuffle()

  • sample() (без повторений)

       1 >>> sample(range(10,100), 10)
       2 [95, 28, 54, 93, 40, 97, 63, 26, 69, 91]
       3 >>> sample(range(10,100), 10)
       4 [57, 81, 73, 54, 95, 93, 42, 37, 80, 21]
       5 
    
  • choices() — с заданными весами

       1 >>> choices(range(10,100), [1]*90, k=20) # равные веса
       2 [94, 50, 52, 78, 38, 95, 22, 18, 24, 32, 25, 92, 48, 42, 62, 49, 97, 95, 55, 59]
       3 >>> choices(range(10,100), range(90,0,-1), k=20) # малые числа тяжелее
       4 [20, 18, 45, 85, 45, 41, 30, 72, 58, 18, 20, 43, 20, 10, 44, 21, 22, 64, 25, 39]
       5 >>> choices(range(10,100), cum_weights=range(90), k=20) # равные кумулятивные веса
       6 [28, 94, 61, 21, 48, 43, 13, 53, 49, 31, 94, 99, 84, 39, 13, 52, 43, 11, 98, 79]
       7 >>> choices(range(10), cum_weights=[c for c in range(15) if c%3], k=20)
       8 [6, 2, 4, 2, 8, 6, 8, 3, 6, 8, 9, 8, 8, 1, 6, 2, 2, 0, 4, 9]
       9 >>> from collections import Counter
      10 >>> S = choices(range(10), cum_weights=[c for c in range(15) if c%3], k=1000)
      11 >>> Counter(S) # 2,4,6,8 — в два раза чаще остальных
      12 Counter({6: 165, 4: 152, 2: 145, 8: 127, 9: 83, 0: 70, 7: 69, 1: 68, 3: 66, 5: 55})
      13 
    

Д/З

  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)