Различия между версиями 5 и 6
Версия 5 от 2020-10-13 15:35:09
Размер: 7577
Редактор: FrBrGeorge
Комментарий:
Версия 6 от 2020-10-13 20:47:35
Размер: 9329
Редактор: FrBrGeorge
Комментарий:
Удаления помечены так. Добавления помечены так.
Строка 136: Строка 136:
'''TODO'''
 1. Покемоны. Участники некоторой карточной игры владеют несколькими колодами, из которых они составляют свой уникальный игровой набор. Каждая колода имеет номер; колоды с одинаковыми номерами содержат совпадающие наборы карт. Ввести строки вида "`имя игрока / номер колоды`" или "`номер колоды / название карты`" (последняя строка пустая). Вывести в алфавитном порядке имена игроков, которые могут составить игровой набор из наибольшего числа ''различных'' карт.
 1. Словарь Толстого. Ввести число N, а за ним построчно некоторый текст. Выделить из текста слова, и вывести Top-N по частоте встречаемости слов, длиной не меньше N. Например, в Top-2 список входят все слова, которые встречаются чаще всех, и все слова, которые встречаются реже этих, но чаще всех остальных (обратите внимание на то, что `Counter.most_common()` ведёт себя иначе). Не слишком интересная задачка, но весьма поучительная, если её натравить на «Анну Каренину», например. Толстой зануда.
 1. '''TODO''' про random

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

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

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

TODO

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

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

  3. TODO про random

LecturesCMC/PythonIntro2020/06_DictCollection (последним исправлял пользователь FrBrGeorge 2023-10-19 14:36:21)