Последовательности и цикл 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:

• примеры со строками и кортежами
• более подробно — в лекции про интераторы

Кстати,

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

  • расширенное множественное присваивание вида «A₀, A₁, …, *А_k, …, A_N = последовательность_из_N+m_элементов»

• Функции all() и any() принимают в качестве параметра последовательность

• …одни повсюду!

Последовательности

Операции над последовательностями

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

Константные последовательности на примере кортежа

• Умножение на число и сложение

• in

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

• как на самом деле работает [] — .__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(выражение)
    

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

  • Фильтрующая клауза: [выражение1 for имена in последовательность if выражение2]

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

• Операции над модифицируемыми последовательностями

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

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

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

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

Колоды:

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

• from collectiond import deque

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

Имитация многомерных структур данных

• списки списков: проблема внутренних размеров

Вычислимые последовательности

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

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

  • «Классический» for i in range(N):

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

Д/З

0. Прочитать и прощёлкать тьюториал (и про цикл for)

   • Операции над последовательностями

   • Операции над модифицируемыми последовательностями

1. EJudge: UniInterval 'Объединение отрезков'

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

   Input:

   (66, 91), (152, 230), (21, 81), (323, 342), (158, 211), (286, 332), (294, 330), (18, 58), (183, 236)

   Output:

   213

2. EJudge: SpiralDigits 'Цифры по спирали'

   Ввести целые M и N, вывести последовательность 0 1 2 3 4 5 6 7 8 9 0 1 2 3 … в виде спирально (по часовой стрелке, из верхнего левого угла) заполненной таблицы N×M (N строк, M столбцов). Не забываем про то, что M и N могут быть чётными, нечётными и неизвестно, какое больше.

   Input:

   6,5

   Output:

   0 1 2 3 4 5
   7 8 9 0 1 6
   6 7 8 9 2 7
   5 6 5 4 3 8
   4 3 2 1 0 9

3. При подготовке последнего теста использовался графический редактор GIMP и формат XPM

   EJudge: FindRect 'Морской бой'

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

   Input:

   ------------
   .###.....#..
   .###.##..#..
   .....##.....
   .....##..#..
   ............
   ............
   .####..####.
   .......####.
   .......####.
   ------------

   Output:

   6