Последовательности, множества и цикл for

Операции над объектами как совокупность методов

• Поля объектов, пространство имён, dir(), поля-методы и поля-поля

• Операции — это методы

  • int.__add__(100500,42) или даже (100500).__add__(42) как 100500+42

  • "строка".__len__() как len("строка")

  • и т. п.
• Понятие протокола

  • Пример: числовой протокол (на Си), на Python

  • Строгая типизация (__mul__() vs __rmul__()) и т. п.

  • Последовательность — это свойство объекта (нужные методы), т. е. тоже протокол

Цикл for

• Общий вид:

     1 for имена in последовательность:
     2     тело
  

  • имена, а не только имя — распаковка, если элемент последовательности — тоже последовательность

  • break, continue и else:

• примеры со строками и кортежами

Кстати,

• В конструкции множественного связывания имена = последовательность последовательность любая

Индексируемые/неиндексируемые последовательности

Имеют метод последовательность.__getitem__(что-то), что означает последовательность[что-то]

Кортеж:

• индексирование, +от конца
• секционирование, шаг, умолчания, отсутствие границ

• как на самом деле работает [] — .__getitem__()

  • тип slice

• .__getitem__(кортеж) — не работает, а в других типах может)

Cтрока (введение):

• Подстрока строки — строка

Модифицируемые

Списки

Имеют метод .__setitem__()

• .setitem(число)

• .setitem(slice)

  • вариант с шагом

• циклическая cборка [выражение for имена in последовательность]

  • Что работает так:

       1   _=[]
       2   for имена in последовательность:
       3       _.append(выражение)
    

  • и даже [выражение for имена1 in последовательность1 for имена2 in последовательность2 …]:

       1   _=[]
       2   for имена1 in последовательность1:
       3       for имена2 in последовательность2:
       4           . . .
       5               _.append(выражение)
    

    то есть является декартовым произведением
• Методы списков

• Список как динамический массив, сложность модификации его начала (n) и конца (1)

  • список как стек, .append(), .pop()

  • сравнение с linked lists; есть ли разница в эффективности?
    • единственная выгода linked list — это константная сложность вставки/удаления произвольного элемента

    • но алгоритмов, требующих вставки/удаления произвольного элемента без предварительного поиска, кажется (?) нет, а поиск в обоих случаях линейный

Деки:

• Ответ на предыдущий вопрос — очередь

• from collectiond import deque

• добавление в начало и в конец

Множества

Имеют метод .__add__()

• Реализация множеств как хеш-таблиц, линейный в среднем поиск

• => хеширование только константных объектов!

• Задание множества: { элемент1, элемент2, …}

  • Пустое множество — set(), (а {} — вообще не множество)

• Теоретико-множественные операции
• множество — это последовательность
• замороженные множества

Вычислимые последовательности (введение, можем не успеть)

Значения не хранятся, а вычисляются .__getitem__()-ом

• range (индексируемая!)

• enumerate()

• reversed() (а это — нет)

  • ещё есть sorted(), но оно возвращает список

• …

Д/З

0. Прочитать и прощёлкать тьюториал (и про цикл for) TODO Тесты к задачам пока не готовы, появятся вечером.

1. EJudge: HiddenText 'Скрытое послание'

   Ввести две строки и проверить, содержится ли вторая в первой, с учётом того, что символы второй строки могут находиться в первой на некотором равном расстоянии друг от друга. Вывести YES или NO.

   Input:

   q-We-Rt-Yu-Iweozzz
   WRYI

   Output:

   YES

2. EJudge: MaxPrime 'Ближайшее простое'

   Ввести натуральное 1000000000000>N>1 и вывести максимальное простое число, не превосходящее N.

   Input:

   12345

   Output:

   12343

3. EJudge: PairCubes 'Пары кубов'

   Ввести натуральное число и проверить, представимо ли оно в виде суммы кубов двух натуральных чисел. Вывести YES или NO. Придумать алгоритм поэффективнее.

   Input:

   32232195

   Output:

   YES

4. EJudge: HandShakes 'Теория рукопожатий'

   Вводить построчно разделённые запятыми последовательности натуральных чисел (кортежи), окончание ввода — пустая строка. Числа в строке — идентификаторы людей, которые познакомились (или уже были знакомы) на некоторой вечеринке. Верно ли, что от любого из перечисленных людей можно построить цепочку знакомств к любому другому? Иными словами, если считать каждую пару x,y ребром неориентированного графа, является ли этот граф связным? Вывести YES или NO.

   Input:

   11,2,3
   7,8,9,
   36,10
   4,2
   5,7,
   11,3,4,
   9,5

   Output:

   NO