Различия между версиями 9 и 10
Версия 9 от 2017-11-06 14:14:33
Размер: 3532
Редактор: FrBrGeorge
Комментарий:
Версия 10 от 2017-11-06 20:06:30
Размер: 3699
Редактор: FrBrGeorge
Комментарий:
Удаления помечены так. Добавления помечены так.
Строка 41: Строка 41:
  * Про хеширование [[py3doc:functions.html#hash|в документации]], и далее п ссылкам   * Про хеширование [[py3doc:functions.html#hash|в документации]], и далее по ссылкам
Строка 51: Строка 51:
  * [[attachment:DungeonMap_gen.py|генратор тестовых даных]]
Строка 52: Строка 53:
  * [[attachment:FarGalaxy_gen.py|генратор тестовых даных]]

Хеширование, множества и словари

Разбор Д/З

Повторение: строки

  • как последовательности (+особенности)
  • строковые методы
  • байтовые строки и кодировки

Хеширование

  • Определение: (f(x)=y: {y} << {x})

  • Возможные свойства и их применение:
    • равномерное покрытие ОЗ — хеш-таблицы
    • вероятная однозначность на небольшом подмножестве ОО — идентификация
    • невосстановимость x из y — шифрование

    • разброс (в т. ч. для почти похожих x) — много где

  • hash()

    • только константные объекты
  • Понятие об идеальной хеш-таблице, поиск в ней
  • Разрешение коллизий ключей в хеш-таблице: «вёдра» vs повторное хеширование

Множества

  • (это хеш-таблиы, как они есть)
  • Конструктор (в т. ч. циклический)
  • операции и методы
  • использование
    • +frozenset

Словари

Хешируется ключ, а хранится произвольный объект ⇒ ассоциативный массив, хеш ключа в качестве индекса объекта

  • Конструктор словаря (+циклический)
  • методы
  • использование
    • почему нет frozendict?

  • Устройство современных (Python3.6+) словарей (описано здесь): прямая таблица объектов + хеш-таблица индексов + пометка на удаление вместо удаления + переупаковка

  • (если успеем) вся правда о пространствах имён
  • (если успеем) именные параметры функций

Д/З

  • Почитать
  • Разобраться с кодом, имитирующим хеш-таблицы

    • Задать вопросы, если что непонятно
  • EJudge: ThreeSquares 'Три квадрата'

    Ввести произвольную последовательность (не обязательно кортеж) натуральных чисел, не превышающих 1000000. Вывести, сколько среди них различных чисел, являющихся суммой трёх квадратов.

    • Пояснение. Поскольку входная последовательность обрабатывается eval(), она может быть, например, такой: (1+i%10 for i in range(100000)), в этом случае ответ — тоже 3 :)

    Input:

    3, 4, 2, 9, 1, 5, 6, 7, 8, 3, 6
    Output:

    3
  • EJudge: MostPopular 'Самые популярные'

    Ввести строку, состоящую из разделённых пробелами последовательностей маленьких и больших латинских букв. Вывести, сколько различных слов (без учёта регистра) встречается в этой строке чаще всего.

    Input:

    dAh Dit dah dIT dAH Dit GIgly diGLy biglY GiGly bOOm quack OH quack
    Output:

    2
  • EJudge: DungeonMap 'Карта подземелья'

    Вводится карта проходимых в обе стороны тоннелей подземлья в виде строк, содержащих разделённые пробелом названия двух пещер, которые соединяет соответствующий тоннель. Две последние строки не содержат пробелов — это название входа в подземелье и название выхода. Вывести "YES", если из входа можно попасть в выход, и "NO" в противном случае. Пары могут повторяться или содержать одинаковые слова.

    Input:

    markers jumping
    jumping guinea
    skiing pre
    markers gauge
    skiing mpeg
    solar jackson
    skiing solar
    guinea gauge
    mpeg honor
    pre honor
    guinea gauge
    pre mpeg
    markers guinea
    markers gauge
    honor mpeg
    markers jumping
    skiing
    jumping
    Output:

    NO
  • EJudge: FarGalaxy 'В далёкой галактике'

    Ввести построчно четвёрки вида «число число число слово», где первые три числа — это координаты галактики по имени «слово» (некоторые галактики могут называться одинаково, но координаты у всех разные). Последняя строка ввода не содержит пробелов и не учитывается. Вывести в алфавитном порядке имена любых двух наиболее удалённых друг от друга галактик.

    Input:

    35.764 -797.636 -770.320 almost
    88.213 -61.688 778.457 gene
    -322.270 -248.555 -812.730 trend
    721.262 630.355 968.287 dow
    -895.519 -970.173 97.282 non
    -561.036 -350.840 -723.149 disco
    -151.546 -900.962 -658.862 bidder
    -716.197 478.576 -695.843 hawaii
    -744.664 -173.034 -11.211 sad
    -999.968 990.467 650.551 erik
    .
    Output:

    almost erik

LecturesCMC/PythonIntro2017/07_Dicts (последним исправлял пользователь FrBrGeorge 2017-11-09 23:19:33)