Словари и множества; измерение времени выполнения кода

• Разбор Д/З
• Словари (ассоциативные массивы):
  • Задание (явно, конструктором, итерацией по парам)
  • Время доступа
  • Примеры использования

• Команды time и sleep

  • отличие пользовательского времени от календарного

  • os.times()

• Модуль time

  • .time() и .clock()

  • sleep()

• (если успеем) Разбор более сложной задачи на динамическое программирование (например, задача о покупке билетов)

• (если успеем) Множества
  • Теоретико-множественные операции

Домашнее задание

1. Прочитать в учебнике про множества и словари

2. Исследовательское задание. Придумать (или аоспроизвести) методику, позволяющую тестировать скорость чтения объектов из контейнера (словаря,списка и кортежа) и скорость записи объектов в словарь и список. Измерить с помощью time.clock(), что быстрее.

   0. Пример методики:

      • В качестве индексов словаря используем целые числа в диапазоне от 0 до N, так что обращение к словарю не отличается от обращения к списку/кортежу, и можно написать общие функции тестирования

      • Вычисляем разницу clock() перед и после вызова тестирующей функции, делим на N и получаем скорость работы операции «в попугаях»

      • Чтение: предварительно заполняем контейнер, затем просто читаем все элементы подряд

      • Запись: в случае словаря отдельно проверить запись в пустой словарь, отдельно — в заполненный, т. е. когда при A[k]=b создаётся элемент словаря, или же он уже есть.

3. (PopularWord) Популярное слово

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

   Input:

   Sed tempus ipsum quis eros tempus lacinia Cras finibus lorem ut lacinia egestas nunc nibh iaculis est convallis tincidunt mi mi sed nisl Sed porttitor aliquam elit ullamcorper tincidunt arcu euismod quis Mauris congue elit suscipit leo varius facilisis Cras et arcu sodales laoreet est vitae pharetra orci Integer eget nulla dictum aliquet justo semper molestie neque Maecenas bibendum lacus tincidunt auctor varius purus felis ullamcorper dui et laoreet ligula ex et risus Donec eget fringilla nibh Cras congue tincidunt accumsan Maecenas euismod eleifend elit ut rhoncus tortor sodales a Cras egestas finibus lorem non tempor tincidunt aera

   Output:

   tincidunt

4. (CountSort) Сортировка подчсётом

   Ввести в столбик объекты Python, являющиеся (по условию!) кортежами из натуральных чисел, не превышающих 4. Последний объект состоит из нулей. Вывести их в отсортированном по возрастанию виде (правила стандартные, например 4, 4, 4, 4, 4, 4, 4, 4, 4, 3 > 4, 4, 4, 4, 4, 4, 4, 4, 3, 4 > 4, 4, 4, 4, 4, 4, 4, 4, 3, 2)

   Input:

   3, 3, 3, 3, 3, 1, 2, 1, 3, 2
   3, 3, 1, 4, 2, 4, 4, 3, 3, 4
   3, 3, 1, 4, 2, 4, 4, 3, 3, 4
   3, 3, 1, 4, 2, 4, 4, 3, 3, 4
   4, 1, 4, 2, 3, 2, 4, 2, 1, 3
   2, 3, 1, 2, 4, 1, 4, 4, 3, 3
   4, 1, 4, 2, 3, 2, 4, 2, 1, 3
   3, 3, 1, 4, 2, 4, 4, 3, 3, 4
   3, 4, 2, 4, 1, 3, 4, 3, 1, 4
   3, 3, 1, 4, 2, 4, 4, 3, 3, 4
   0, 0, 0, 0, 0, 0, 0, 0, 0, 0

   Output:

   0, 0, 0, 0, 0, 0, 0, 0, 0, 0
   2, 3, 1, 2, 4, 1, 4, 4, 3, 3
   3, 3, 1, 4, 2, 4, 4, 3, 3, 4
   3, 3, 1, 4, 2, 4, 4, 3, 3, 4
   3, 3, 1, 4, 2, 4, 4, 3, 3, 4
   3, 3, 1, 4, 2, 4, 4, 3, 3, 4
   3, 3, 1, 4, 2, 4, 4, 3, 3, 4
   3, 3, 3, 3, 3, 1, 2, 1, 3, 2
   3, 4, 2, 4, 1, 3, 4, 3, 1, 4
   4, 1, 4, 2, 3, 2, 4, 2, 1, 3
   4, 1, 4, 2, 3, 2, 4, 2, 1, 3

5. (упрощение задачи ВМиК/2012)

   (ConstructIt) Сборка агрегата по инструкции

   Первая строка ввода — правило сборки агрегата вида «название_агрегата деталь1 деталь2 …», в ней сказано, из каких деталей можно собрать агрегат. Последующие строки ввода — либо аналогичные правила сборки деталей вида «деталь1 деталь2 …», либо состоят из одного слова «деталь» — в знак того, что такие детали есть на складе. Каждая деталь собирается не более, чем единственным способом. Последняя строка пустая. Вывести YES, если из деталей на складе можно собрать агрегат, и NO, если нельзя.

   Input:

   Choo qw er ty ui
   qw er ty
   ty
   er ty ui
   ui

   Output:

   YES

Условные обозначения

• — тема по Linux

• ­— тема повышенной сложности

• — теоретическое задание

• — тема для самостоятельного изучения

CategoryClass CategoryVmsh