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

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

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

  • Python: это всё «атрибуты»
• Операции — это методы

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

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

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

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

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

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

Цикл for

• Общий вид:

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

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

  • break, continue

  • else:

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

• Более подробно — в лекции про итераторы. Если коротко: протокол последовательности гарантирует, что из неё можно изготовить объект-итератор, и именно этот объект и подставляется в правую часть for.

Кстати,

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

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

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

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

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

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

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

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

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

• in и not in

• индексирование, +от конца

• поэлементное лексикографическое сравнение

• секционирование:
  • отсутствие ошибок при выходе за границы
  • шаг

  • умолчания (+чем A[:] отличается от A?)

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

  • тип slice

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

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

• Подстрока строки — строка, так что "!@#"[0][0][0][-1][0][-1]… — сработает и выдаст "!"

• ⇒ Хотя строки и хранимая последовательность, её «элементы» вычисляются

Рассмотрим в отдельной лекции.

Списки — модифицируемые последовательности

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

• .__setitem__(число)

• .__setitem__(slice)

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

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

• циклическая сборка [выражение 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)
    

• Список как динамическая таблица (массив ссылок на элементы; размер ссылки в Python всегда одинаковый)

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

  • Реализация динамического массива с геометрическим масштабированием

    • Выделяем N элементов массива

    • Если массив переполняется, удваиваем его размер и копируем все элементы на новое место

    • Если массив опустошается на K% (т. н. «нижний урез»; в Python — на 3/4, кажется), ополовиниваем размер и копируем элементы
  • Оценка сложности:

    • Масштабирование случается не чаще одного на N операций (при постоянном добавлении или постоянном удалении, иначе — реже)

    • Сложность масштабирования (и одной из N операций) — O(N)

    • ⇒ Наихудшая средняя сложность операций с концом списка — 2*O(1) ≈ O(1)

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

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

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

• Работа += на списках

• Другие методы списка

Колоды:

• Востребованный «не последний элемент», искать который не нужно — первый.

  • ⇒ list неэффективен как очередь

• «Колода» / deque (двойная очередь? «колочередь»?)
  • эффективное добавление и в начало, и в конец

  • скорее всего, реализована как кольцевой буфер с геометрическим масштабированием

  • from collectiond import deque

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

• «Матрица» как список списков
  • Равенство размеров всех элементов списка?

• (есть array, NumPy и т. д)

Соиспользование связанных объектов

Отсутствие «подковёрного» копирования

• например, это совсем не матрица: [[0] * N] * M — почему? ☺

• a.copy(), a[:] и copy.deepcopy()

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

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

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

  • range(stop) / range(start, stop[, step])

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

• enumerate

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

Д/З

Напоминалка:

• Если перейти по ссылке, откроется более полная формулировка задания с советами и подсказками
• Подсказки-спойлеры изначально не видны, они открываются, если нажать в шапке страницы меню «комментарии». Обычно в спойлерах излагается алгоритм решения — всё-таки у нас тут не олимпиада ☺

• Любителям «парковки на слух»: всего попыток в турнире 200, а задач примерно 40 — шлите решение, только если уже оттестировали его и уверены, что оно правильное!

Собственно задание:

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

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

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

1. EJudge: CountSort 'Сортировка подсчётом'

   Вводится последовательность пар натуральных чисел, не превышающих 100, последняя строка ввода — пустая. Вывести её в лексикографически отсортированном по возрастанию виде. Дополнительные условия:

   • из составных типов данных можно пользоваться только списками и кортежами (для вывода — строками),
   • целиком последовательность в памяти хранить нельзя!
   Input:

   2, 100
   12, 4
   2, 2
   5, 8
   2, 100
   33, 33
   12, 4

   Output:

   2, 2
   2, 100
   2, 100
   5, 8
   12, 4
   12, 4
   33, 33

2. EJudge: DiagonalDigits 'Цифры по диагонали'

   Ввести целые M и N (0 ⩽ M, N ⩽ 1000), вывести последовательность 0 1 2 3 4 5 6 7 8 9 0 1 2 3 … в виде прямоугольной матрицы N×M, заполненной из верхнего левого угла по следующему правилу:

   • На каждом шаге заполняется очередная диагональ матрицы с одинаковой суммой координат
   • Диагонали заполняются поочерёдно сверху вниз и снизу вверх (таким образом формируется непрерывный «путь» из верхнего левого угла в правый нижний)
   Input:

   6, 5

   Output:

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

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

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

   Input:

   ###.....#.
   ###.##..#.
   ....##....
   ....##..#.
   ..........
   ..........
   ####..####
   ......####
   ......####

   Output:

   6

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

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

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

   Input:

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

   Output:

   213